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-1cf7e2d-m [2018-03-29 20:49:05,324 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-03-29 20:49:05,325 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-03-29 20:49:05,338 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-03-29 20:49:05,339 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-03-29 20:49:05,339 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-03-29 20:49:05,340 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-03-29 20:49:05,342 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-03-29 20:49:05,344 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-03-29 20:49:05,345 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-03-29 20:49:05,345 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-03-29 20:49:05,346 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-03-29 20:49:05,347 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-03-29 20:49:05,348 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-03-29 20:49:05,349 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-03-29 20:49:05,351 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-03-29 20:49:05,353 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-03-29 20:49:05,355 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-03-29 20:49:05,356 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-03-29 20:49:05,357 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-03-29 20:49:05,359 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-03-29 20:49:05,360 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-03-29 20:49:05,360 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-03-29 20:49:05,361 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-03-29 20:49:05,362 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-03-29 20:49:05,363 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-03-29 20:49:05,363 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-03-29 20:49:05,364 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-03-29 20:49:05,365 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-03-29 20:49:05,365 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-03-29 20:49:05,366 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-03-29 20:49:05,366 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-29 20:49:05,389 INFO L110 SettingsManager]: Loading preferences was successful [2018-03-29 20:49:05,389 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-03-29 20:49:05,389 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-03-29 20:49:05,390 INFO L133 SettingsManager]: * ultimate.logging.details=de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation=DEBUG; [2018-03-29 20:49:05,390 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-03-29 20:49:05,390 INFO L133 SettingsManager]: * to procedures, called more than once=true [2018-03-29 20:49:05,391 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-03-29 20:49:05,391 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=VPDomain [2018-03-29 20:49:05,391 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-03-29 20:49:05,391 INFO L131 SettingsManager]: Preferences of LTL2Aut differ from their defaults: [2018-03-29 20:49:05,391 INFO L133 SettingsManager]: * Property to check=[] a a: x > 42 [2018-03-29 20:49:05,391 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-03-29 20:49:05,391 INFO L133 SettingsManager]: * sizeof long=4 [2018-03-29 20:49:05,392 INFO L133 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2018-03-29 20:49:05,392 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-03-29 20:49:05,392 INFO L133 SettingsManager]: * sizeof POINTER=4 [2018-03-29 20:49:05,392 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-03-29 20:49:05,392 INFO L133 SettingsManager]: * Check for the main procedure if all allocated memory was freed=true [2018-03-29 20:49:05,392 INFO L133 SettingsManager]: * SV-COMP memtrack compatibility mode=true [2018-03-29 20:49:05,392 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-03-29 20:49:05,393 INFO L133 SettingsManager]: * sizeof long double=12 [2018-03-29 20:49:05,393 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-03-29 20:49:05,393 INFO L133 SettingsManager]: * Size of a code block=SingleStatement [2018-03-29 20:49:05,393 INFO L133 SettingsManager]: * Add additional assume for each assert=false [2018-03-29 20:49:05,393 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-03-29 20:49:05,393 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-03-29 20:49:05,394 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-03-29 20:49:05,394 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-03-29 20:49:05,394 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-03-29 20:49:05,394 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-03-29 20:49:05,394 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-03-29 20:49:05,394 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-03-29 20:49:05,394 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-03-29 20:49:05,395 INFO L131 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2018-03-29 20:49:05,395 INFO L133 SettingsManager]: * TransformationType=HEAP_SEPARATOR [2018-03-29 20:49:05,395 INFO L131 SettingsManager]: Preferences of Boogie Printer differ from their defaults: [2018-03-29 20:49:05,396 INFO L133 SettingsManager]: * Dump path:=C:\Users\alex\AppData\Local\Temp\ [2018-03-29 20:49:05,429 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-03-29 20:49:05,440 INFO L266 ainManager$Toolchain]: [Toolchain 1]: Parser(s) successfully (re)initialized [2018-03-29 20:49:05,443 INFO L222 ainManager$Toolchain]: [Toolchain 1]: Toolchain data selected. [2018-03-29 20:49:05,444 INFO L271 PluginConnector]: Initializing CDTParser... [2018-03-29 20:49:05,444 INFO L276 PluginConnector]: CDTParser initialized [2018-03-29 20:49:05,445 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-29 20:49:05,746 INFO L225 CDTParser]: Created temporary CDT project at /storage/ultimate/releaseScripts/default/UAutomizer-linux/data/FLAGee23f5f3b [2018-03-29 20:49:05,871 INFO L287 CDTParser]: IsIndexed: true [2018-03-29 20:49:05,872 INFO L288 CDTParser]: Found 1 translation units. [2018-03-29 20:49:05,872 INFO L168 CDTParser]: Scanning sanfoundry_24_false-valid-deref.i [2018-03-29 20:49:05,873 INFO L210 ultiparseSymbolTable]: Include resolver: [2018-03-29 20:49:05,873 INFO L215 ultiparseSymbolTable]: [2018-03-29 20:49:05,873 INFO L218 ultiparseSymbolTable]: Function table: [2018-03-29 20:49:05,873 INFO L221 ultiparseSymbolTable]: Function definition of __U_MULTI_fsanfoundry____false_valid_deref_i__printOdd ('printOdd') in sanfoundry_24_false-valid-deref.i [2018-03-29 20:49:05,873 INFO L221 ultiparseSymbolTable]: Function definition of null ('main') in sanfoundry_24_false-valid-deref.i [2018-03-29 20:49:05,873 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-29 20:49:05,874 INFO L221 ultiparseSymbolTable]: Function definition of __U_MULTI_fsanfoundry____false_valid_deref_i__printEven ('printEven') in sanfoundry_24_false-valid-deref.i [2018-03-29 20:49:05,874 INFO L227 ultiparseSymbolTable]: Global variable table: [2018-03-29 20:49:05,874 INFO L233 ultiparseSymbolTable]: [2018-03-29 20:49:05,888 INFO L330 CDTParser]: Deleted temporary CDT project at /storage/ultimate/releaseScripts/default/UAutomizer-linux/data/FLAGee23f5f3b [2018-03-29 20:49:05,893 INFO L304 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-03-29 20:49:05,897 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2018-03-29 20:49:05,898 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-03-29 20:49:05,898 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-03-29 20:49:05,904 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-03-29 20:49:05,905 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 29.03 08:49:05" (1/1) ... [2018-03-29 20:49:05,907 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@e5f11f9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.03 08:49:05, skipping insertion in model container [2018-03-29 20:49:05,907 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 29.03 08:49:05" (1/1) ... [2018-03-29 20:49:05,920 INFO L167 Dispatcher]: Using SV-COMP mode [2018-03-29 20:49:05,931 INFO L167 Dispatcher]: Using SV-COMP mode [2018-03-29 20:49:06,069 INFO L175 PostProcessor]: Settings: Checked method=main [2018-03-29 20:49:06,086 INFO L175 PostProcessor]: Settings: Checked method=main [2018-03-29 20:49:06,089 INFO L100 SccComputation]: Graph consists of 0 InCaSumBalls and 8 non ball SCCs. Number of states in SCCs 8. [2018-03-29 20:49:06,096 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.03 08:49:06 WrapperNode [2018-03-29 20:49:06,096 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-03-29 20:49:06,097 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-03-29 20:49:06,097 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-03-29 20:49:06,097 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-03-29 20:49:06,108 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.03 08:49:06" (1/1) ... [2018-03-29 20:49:06,108 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.03 08:49:06" (1/1) ... [2018-03-29 20:49:06,113 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.03 08:49:06" (1/1) ... [2018-03-29 20:49:06,114 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.03 08:49:06" (1/1) ... [2018-03-29 20:49:06,116 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.03 08:49:06" (1/1) ... [2018-03-29 20:49:06,120 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.03 08:49:06" (1/1) ... [2018-03-29 20:49:06,122 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.03 08:49:06" (1/1) ... [2018-03-29 20:49:06,123 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-03-29 20:49:06,124 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-03-29 20:49:06,124 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-03-29 20:49:06,124 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-03-29 20:49:06,125 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.03 08:49:06" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-03-29 20:49:06,190 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-03-29 20:49:06,190 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-03-29 20:49:06,190 INFO L136 BoogieDeclarations]: Found implementation of procedure __U_MULTI_fsanfoundry____false_valid_deref_i____VERIFIER_assert [2018-03-29 20:49:06,190 INFO L136 BoogieDeclarations]: Found implementation of procedure __U_MULTI_fsanfoundry____false_valid_deref_i__printEven [2018-03-29 20:49:06,190 INFO L136 BoogieDeclarations]: Found implementation of procedure __U_MULTI_fsanfoundry____false_valid_deref_i__printOdd [2018-03-29 20:49:06,191 INFO L136 BoogieDeclarations]: Found implementation of procedure main [2018-03-29 20:49:06,191 INFO L128 BoogieDeclarations]: Found specification of procedure __VERIFIER_error [2018-03-29 20:49:06,191 INFO L128 BoogieDeclarations]: Found specification of procedure __U_MULTI_fsanfoundry____false_valid_deref_i____VERIFIER_assert [2018-03-29 20:49:06,191 INFO L128 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2018-03-29 20:49:06,191 INFO L128 BoogieDeclarations]: Found specification of procedure __U_MULTI_fsanfoundry____false_valid_deref_i__printEven [2018-03-29 20:49:06,191 INFO L128 BoogieDeclarations]: Found specification of procedure __U_MULTI_fsanfoundry____false_valid_deref_i__printOdd [2018-03-29 20:49:06,192 INFO L128 BoogieDeclarations]: Found specification of procedure main [2018-03-29 20:49:06,192 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-03-29 20:49:06,192 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-03-29 20:49:06,407 INFO L259 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-03-29 20:49:06,407 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 29.03 08:49:06 BoogieIcfgContainer [2018-03-29 20:49:06,407 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-03-29 20:49:06,408 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-03-29 20:49:06,408 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-03-29 20:49:06,410 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-03-29 20:49:06,410 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 29.03 08:49:05" (1/3) ... [2018-03-29 20:49:06,411 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@41769dfe and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 29.03 08:49:06, skipping insertion in model container [2018-03-29 20:49:06,411 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.03 08:49:06" (2/3) ... [2018-03-29 20:49:06,411 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@41769dfe and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 29.03 08:49:06, skipping insertion in model container [2018-03-29 20:49:06,411 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 29.03 08:49:06" (3/3) ... [2018-03-29 20:49:06,413 INFO L107 eAbstractionObserver]: Analyzing ICFG sanfoundry_24_false-valid-deref.i [2018-03-29 20:49:06,422 INFO L131 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-03-29 20:49:06,427 INFO L143 ceAbstractionStarter]: Appying trace abstraction to program that has 4 error locations. [2018-03-29 20:49:06,467 INFO L128 ementStrategyFactory]: Using default assertion order modulation [2018-03-29 20:49:06,468 INFO L369 AbstractCegarLoop]: Interprodecural is true [2018-03-29 20:49:06,468 INFO L370 AbstractCegarLoop]: Hoare is true [2018-03-29 20:49:06,469 INFO L371 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-03-29 20:49:06,469 INFO L372 AbstractCegarLoop]: Backedges is TWOTRACK [2018-03-29 20:49:06,469 INFO L373 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-03-29 20:49:06,469 INFO L374 AbstractCegarLoop]: Difference is false [2018-03-29 20:49:06,469 INFO L375 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-03-29 20:49:06,469 INFO L380 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-03-29 20:49:06,470 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-03-29 20:49:06,485 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states. [2018-03-29 20:49:06,489 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2018-03-29 20:49:06,490 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 20:49:06,490 INFO L355 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-29 20:49:06,490 INFO L408 AbstractCegarLoop]: === Iteration 1 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 20:49:06,496 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-29 20:49:06,508 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 20:49:06,525 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 20:49:06,531 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 20:49:06,556 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-29 20:49:06,556 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 20:49:06,586 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-29 20:49:06,608 INFO L320 seRefinementStrategy]: Constructing automaton from 2 perfect and 0 imperfect interpolant sequences. [2018-03-29 20:49:06,608 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2, 2] imperfect sequences [] total 3 [2018-03-29 20:49:06,610 INFO L442 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-03-29 20:49:06,619 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-03-29 20:49:06,620 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-03-29 20:49:06,622 INFO L87 Difference]: Start difference. First operand 51 states. Second operand 4 states. [2018-03-29 20:49:06,753 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 20:49:06,753 INFO L93 Difference]: Finished difference Result 112 states and 144 transitions. [2018-03-29 20:49:06,754 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-03-29 20:49:06,755 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 13 [2018-03-29 20:49:06,755 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 20:49:06,763 INFO L225 Difference]: With dead ends: 112 [2018-03-29 20:49:06,763 INFO L226 Difference]: Without dead ends: 62 [2018-03-29 20:49:06,767 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-29 20:49:06,781 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 62 states. [2018-03-29 20:49:06,806 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 62 to 55. [2018-03-29 20:49:06,807 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 55 states. [2018-03-29 20:49:06,809 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 62 transitions. [2018-03-29 20:49:06,811 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 62 transitions. Word has length 13 [2018-03-29 20:49:06,811 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 20:49:06,812 INFO L459 AbstractCegarLoop]: Abstraction has 55 states and 62 transitions. [2018-03-29 20:49:06,812 INFO L460 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-03-29 20:49:06,812 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 62 transitions. [2018-03-29 20:49:06,814 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2018-03-29 20:49:06,814 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 20:49:06,814 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-29 20:49:06,814 INFO L408 AbstractCegarLoop]: === Iteration 2 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 20:49:06,815 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-29 20:49:06,827 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 20:49:06,836 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 20:49:06,839 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 20:49:06,861 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-29 20:49:06,861 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 20:49:06,915 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-29 20:49:06,949 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 20:49:06,950 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 7 [2018-03-29 20:49:06,951 INFO L442 AbstractCegarLoop]: Interpolant automaton has 8 states [2018-03-29 20:49:06,952 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2018-03-29 20:49:06,952 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2018-03-29 20:49:06,952 INFO L87 Difference]: Start difference. First operand 55 states and 62 transitions. Second operand 8 states. [2018-03-29 20:49:07,144 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 20:49:07,144 INFO L93 Difference]: Finished difference Result 84 states and 101 transitions. [2018-03-29 20:49:07,144 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-03-29 20:49:07,144 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 20 [2018-03-29 20:49:07,145 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 20:49:07,147 INFO L225 Difference]: With dead ends: 84 [2018-03-29 20:49:07,147 INFO L226 Difference]: Without dead ends: 82 [2018-03-29 20:49:07,148 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-29 20:49:07,149 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 82 states. [2018-03-29 20:49:07,158 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 82 to 73. [2018-03-29 20:49:07,159 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 73 states. [2018-03-29 20:49:07,161 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 73 states to 73 states and 86 transitions. [2018-03-29 20:49:07,161 INFO L78 Accepts]: Start accepts. Automaton has 73 states and 86 transitions. Word has length 20 [2018-03-29 20:49:07,161 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 20:49:07,161 INFO L459 AbstractCegarLoop]: Abstraction has 73 states and 86 transitions. [2018-03-29 20:49:07,162 INFO L460 AbstractCegarLoop]: Interpolant automaton has 8 states. [2018-03-29 20:49:07,162 INFO L276 IsEmpty]: Start isEmpty. Operand 73 states and 86 transitions. [2018-03-29 20:49:07,163 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2018-03-29 20:49:07,163 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 20:49:07,163 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-29 20:49:07,163 INFO L408 AbstractCegarLoop]: === Iteration 3 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 20:49:07,163 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-29 20:49:07,172 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 20:49:07,181 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 20:49:07,184 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 20:49:07,212 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-29 20:49:07,212 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 20:49:07,236 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-29 20:49:07,269 INFO L320 seRefinementStrategy]: Constructing automaton from 2 perfect and 0 imperfect interpolant sequences. [2018-03-29 20:49:07,269 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5, 5] imperfect sequences [] total 6 [2018-03-29 20:49:07,270 INFO L442 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-03-29 20:49:07,270 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-03-29 20:49:07,270 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2018-03-29 20:49:07,271 INFO L87 Difference]: Start difference. First operand 73 states and 86 transitions. Second operand 6 states. [2018-03-29 20:49:07,382 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 20:49:07,383 INFO L93 Difference]: Finished difference Result 101 states and 117 transitions. [2018-03-29 20:49:07,383 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-03-29 20:49:07,383 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 23 [2018-03-29 20:49:07,384 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 20:49:07,386 INFO L225 Difference]: With dead ends: 101 [2018-03-29 20:49:07,386 INFO L226 Difference]: Without dead ends: 76 [2018-03-29 20:49:07,387 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-29 20:49:07,387 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 76 states. [2018-03-29 20:49:07,394 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 76 to 73. [2018-03-29 20:49:07,394 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 73 states. [2018-03-29 20:49:07,396 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 73 states to 73 states and 85 transitions. [2018-03-29 20:49:07,396 INFO L78 Accepts]: Start accepts. Automaton has 73 states and 85 transitions. Word has length 23 [2018-03-29 20:49:07,396 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 20:49:07,397 INFO L459 AbstractCegarLoop]: Abstraction has 73 states and 85 transitions. [2018-03-29 20:49:07,397 INFO L460 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-03-29 20:49:07,397 INFO L276 IsEmpty]: Start isEmpty. Operand 73 states and 85 transitions. [2018-03-29 20:49:07,398 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2018-03-29 20:49:07,398 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 20:49:07,399 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-29 20:49:07,399 INFO L408 AbstractCegarLoop]: === Iteration 4 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 20:49:07,399 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-29 20:49:07,408 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 20:49:07,419 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 20:49:07,421 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 20:49:07,480 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-29 20:49:07,480 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 20:49:07,541 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-29 20:49:07,570 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 20:49:07,570 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 12 [2018-03-29 20:49:07,571 INFO L442 AbstractCegarLoop]: Interpolant automaton has 12 states [2018-03-29 20:49:07,571 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2018-03-29 20:49:07,571 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=31, Invalid=101, Unknown=0, NotChecked=0, Total=132 [2018-03-29 20:49:07,572 INFO L87 Difference]: Start difference. First operand 73 states and 85 transitions. Second operand 12 states. [2018-03-29 20:49:07,864 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 20:49:07,864 INFO L93 Difference]: Finished difference Result 107 states and 123 transitions. [2018-03-29 20:49:07,865 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-03-29 20:49:07,865 INFO L78 Accepts]: Start accepts. Automaton has 12 states. Word has length 30 [2018-03-29 20:49:07,865 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 20:49:07,866 INFO L225 Difference]: With dead ends: 107 [2018-03-29 20:49:07,866 INFO L226 Difference]: Without dead ends: 76 [2018-03-29 20:49:07,867 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 65 GetRequests, 45 SyntacticMatches, 4 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 46 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=73, Invalid=233, Unknown=0, NotChecked=0, Total=306 [2018-03-29 20:49:07,867 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 76 states. [2018-03-29 20:49:07,874 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 76 to 73. [2018-03-29 20:49:07,875 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 73 states. [2018-03-29 20:49:07,876 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 73 states to 73 states and 84 transitions. [2018-03-29 20:49:07,876 INFO L78 Accepts]: Start accepts. Automaton has 73 states and 84 transitions. Word has length 30 [2018-03-29 20:49:07,876 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 20:49:07,876 INFO L459 AbstractCegarLoop]: Abstraction has 73 states and 84 transitions. [2018-03-29 20:49:07,877 INFO L460 AbstractCegarLoop]: Interpolant automaton has 12 states. [2018-03-29 20:49:07,877 INFO L276 IsEmpty]: Start isEmpty. Operand 73 states and 84 transitions. [2018-03-29 20:49:07,878 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2018-03-29 20:49:07,878 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 20:49:07,878 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-29 20:49:07,878 INFO L408 AbstractCegarLoop]: === Iteration 5 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 20:49:07,879 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-29 20:49:07,887 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 20:49:07,895 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 20:49:07,897 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 20:49:08,016 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-29 20:49:08,016 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 20:49:08,123 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-29 20:49:08,157 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 20:49:08,157 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 15 [2018-03-29 20:49:08,158 INFO L442 AbstractCegarLoop]: Interpolant automaton has 16 states [2018-03-29 20:49:08,158 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2018-03-29 20:49:08,158 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=54, Invalid=186, Unknown=0, NotChecked=0, Total=240 [2018-03-29 20:49:08,159 INFO L87 Difference]: Start difference. First operand 73 states and 84 transitions. Second operand 16 states. [2018-03-29 20:49:08,617 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 20:49:08,618 INFO L93 Difference]: Finished difference Result 122 states and 153 transitions. [2018-03-29 20:49:08,618 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2018-03-29 20:49:08,618 INFO L78 Accepts]: Start accepts. Automaton has 16 states. Word has length 34 [2018-03-29 20:49:08,619 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 20:49:08,619 INFO L225 Difference]: With dead ends: 122 [2018-03-29 20:49:08,619 INFO L226 Difference]: Without dead ends: 120 [2018-03-29 20:49:08,620 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-29 20:49:08,621 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 120 states. [2018-03-29 20:49:08,629 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 120 to 109. [2018-03-29 20:49:08,630 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 109 states. [2018-03-29 20:49:08,632 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 109 states to 109 states and 132 transitions. [2018-03-29 20:49:08,633 INFO L78 Accepts]: Start accepts. Automaton has 109 states and 132 transitions. Word has length 34 [2018-03-29 20:49:08,633 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 20:49:08,633 INFO L459 AbstractCegarLoop]: Abstraction has 109 states and 132 transitions. [2018-03-29 20:49:08,633 INFO L460 AbstractCegarLoop]: Interpolant automaton has 16 states. [2018-03-29 20:49:08,633 INFO L276 IsEmpty]: Start isEmpty. Operand 109 states and 132 transitions. [2018-03-29 20:49:08,634 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2018-03-29 20:49:08,634 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 20:49:08,634 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-29 20:49:08,634 INFO L408 AbstractCegarLoop]: === Iteration 6 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 20:49:08,635 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-29 20:49:08,647 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 20:49:08,656 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 20:49:08,658 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 20:49:08,674 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-29 20:49:08,675 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 20:49:08,709 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-29 20:49:08,734 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 20:49:08,734 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 7 [2018-03-29 20:49:08,734 INFO L442 AbstractCegarLoop]: Interpolant automaton has 8 states [2018-03-29 20:49:08,734 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2018-03-29 20:49:08,735 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2018-03-29 20:49:08,735 INFO L87 Difference]: Start difference. First operand 109 states and 132 transitions. Second operand 8 states. [2018-03-29 20:49:08,815 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 20:49:08,815 INFO L93 Difference]: Finished difference Result 132 states and 162 transitions. [2018-03-29 20:49:08,815 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-03-29 20:49:08,816 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 37 [2018-03-29 20:49:08,816 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 20:49:08,817 INFO L225 Difference]: With dead ends: 132 [2018-03-29 20:49:08,817 INFO L226 Difference]: Without dead ends: 130 [2018-03-29 20:49:08,818 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-29 20:49:08,818 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 130 states. [2018-03-29 20:49:08,828 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 130 to 127. [2018-03-29 20:49:08,828 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 127 states. [2018-03-29 20:49:08,830 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 127 states to 127 states and 154 transitions. [2018-03-29 20:49:08,830 INFO L78 Accepts]: Start accepts. Automaton has 127 states and 154 transitions. Word has length 37 [2018-03-29 20:49:08,830 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 20:49:08,830 INFO L459 AbstractCegarLoop]: Abstraction has 127 states and 154 transitions. [2018-03-29 20:49:08,831 INFO L460 AbstractCegarLoop]: Interpolant automaton has 8 states. [2018-03-29 20:49:08,831 INFO L276 IsEmpty]: Start isEmpty. Operand 127 states and 154 transitions. [2018-03-29 20:49:08,833 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2018-03-29 20:49:08,833 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 20:49:08,833 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-29 20:49:08,833 INFO L408 AbstractCegarLoop]: === Iteration 7 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 20:49:08,834 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-29 20:49:08,840 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 20:49:08,851 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 20:49:08,853 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 20:49:08,923 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-29 20:49:08,923 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 20:49:08,984 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-29 20:49:09,005 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 20:49:09,005 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 18 [2018-03-29 20:49:09,006 INFO L442 AbstractCegarLoop]: Interpolant automaton has 18 states [2018-03-29 20:49:09,006 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2018-03-29 20:49:09,006 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=59, Invalid=247, Unknown=0, NotChecked=0, Total=306 [2018-03-29 20:49:09,006 INFO L87 Difference]: Start difference. First operand 127 states and 154 transitions. Second operand 18 states. [2018-03-29 20:49:09,222 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 20:49:09,223 INFO L93 Difference]: Finished difference Result 170 states and 203 transitions. [2018-03-29 20:49:09,223 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2018-03-29 20:49:09,223 INFO L78 Accepts]: Start accepts. Automaton has 18 states. Word has length 51 [2018-03-29 20:49:09,224 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 20:49:09,225 INFO L225 Difference]: With dead ends: 170 [2018-03-29 20:49:09,225 INFO L226 Difference]: Without dead ends: 127 [2018-03-29 20:49:09,226 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-29 20:49:09,226 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 127 states. [2018-03-29 20:49:09,235 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 127 to 127. [2018-03-29 20:49:09,235 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 127 states. [2018-03-29 20:49:09,236 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 127 states to 127 states and 153 transitions. [2018-03-29 20:49:09,237 INFO L78 Accepts]: Start accepts. Automaton has 127 states and 153 transitions. Word has length 51 [2018-03-29 20:49:09,237 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 20:49:09,237 INFO L459 AbstractCegarLoop]: Abstraction has 127 states and 153 transitions. [2018-03-29 20:49:09,237 INFO L460 AbstractCegarLoop]: Interpolant automaton has 18 states. [2018-03-29 20:49:09,237 INFO L276 IsEmpty]: Start isEmpty. Operand 127 states and 153 transitions. [2018-03-29 20:49:09,239 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2018-03-29 20:49:09,239 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 20:49:09,240 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-29 20:49:09,240 INFO L408 AbstractCegarLoop]: === Iteration 8 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 20:49:09,240 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-29 20:49:09,254 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 20:49:09,268 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 20:49:09,272 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 20:49:09,408 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-29 20:49:09,408 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 20:49:09,518 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-29 20:49:09,538 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 20:49:09,539 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 17] total 24 [2018-03-29 20:49:09,539 INFO L442 AbstractCegarLoop]: Interpolant automaton has 24 states [2018-03-29 20:49:09,539 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2018-03-29 20:49:09,539 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=95, Invalid=457, Unknown=0, NotChecked=0, Total=552 [2018-03-29 20:49:09,540 INFO L87 Difference]: Start difference. First operand 127 states and 153 transitions. Second operand 24 states. [2018-03-29 20:49:09,835 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 20:49:09,836 INFO L93 Difference]: Finished difference Result 176 states and 209 transitions. [2018-03-29 20:49:09,836 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2018-03-29 20:49:09,836 INFO L78 Accepts]: Start accepts. Automaton has 24 states. Word has length 58 [2018-03-29 20:49:09,836 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 20:49:09,837 INFO L225 Difference]: With dead ends: 176 [2018-03-29 20:49:09,837 INFO L226 Difference]: Without dead ends: 127 [2018-03-29 20:49:09,838 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-29 20:49:09,839 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 127 states. [2018-03-29 20:49:09,846 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 127 to 127. [2018-03-29 20:49:09,847 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 127 states. [2018-03-29 20:49:09,848 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 127 states to 127 states and 152 transitions. [2018-03-29 20:49:09,848 INFO L78 Accepts]: Start accepts. Automaton has 127 states and 152 transitions. Word has length 58 [2018-03-29 20:49:09,849 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 20:49:09,849 INFO L459 AbstractCegarLoop]: Abstraction has 127 states and 152 transitions. [2018-03-29 20:49:09,849 INFO L460 AbstractCegarLoop]: Interpolant automaton has 24 states. [2018-03-29 20:49:09,849 INFO L276 IsEmpty]: Start isEmpty. Operand 127 states and 152 transitions. [2018-03-29 20:49:09,851 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 63 [2018-03-29 20:49:09,851 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 20:49:09,851 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-29 20:49:09,851 INFO L408 AbstractCegarLoop]: === Iteration 9 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 20:49:09,851 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-29 20:49:09,859 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 20:49:09,871 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 20:49:09,874 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 20:49:09,984 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-29 20:49:09,984 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 20:49:10,223 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-29 20:49:10,243 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 20:49:10,244 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 31 [2018-03-29 20:49:10,244 INFO L442 AbstractCegarLoop]: Interpolant automaton has 32 states [2018-03-29 20:49:10,244 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2018-03-29 20:49:10,244 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=174, Invalid=818, Unknown=0, NotChecked=0, Total=992 [2018-03-29 20:49:10,244 INFO L87 Difference]: Start difference. First operand 127 states and 152 transitions. Second operand 32 states. [2018-03-29 20:49:11,488 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 20:49:11,488 INFO L93 Difference]: Finished difference Result 215 states and 279 transitions. [2018-03-29 20:49:11,488 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 45 states. [2018-03-29 20:49:11,488 INFO L78 Accepts]: Start accepts. Automaton has 32 states. Word has length 62 [2018-03-29 20:49:11,489 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 20:49:11,491 INFO L225 Difference]: With dead ends: 215 [2018-03-29 20:49:11,491 INFO L226 Difference]: Without dead ends: 213 [2018-03-29 20:49:11,492 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 157 GetRequests, 93 SyntacticMatches, 0 SemanticMatches, 64 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 716 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=1096, Invalid=3194, Unknown=0, NotChecked=0, Total=4290 [2018-03-29 20:49:11,493 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 213 states. [2018-03-29 20:49:11,503 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 213 to 199. [2018-03-29 20:49:11,503 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 199 states. [2018-03-29 20:49:11,504 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 199 states to 199 states and 248 transitions. [2018-03-29 20:49:11,504 INFO L78 Accepts]: Start accepts. Automaton has 199 states and 248 transitions. Word has length 62 [2018-03-29 20:49:11,505 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 20:49:11,505 INFO L459 AbstractCegarLoop]: Abstraction has 199 states and 248 transitions. [2018-03-29 20:49:11,505 INFO L460 AbstractCegarLoop]: Interpolant automaton has 32 states. [2018-03-29 20:49:11,505 INFO L276 IsEmpty]: Start isEmpty. Operand 199 states and 248 transitions. [2018-03-29 20:49:11,506 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 66 [2018-03-29 20:49:11,506 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 20:49:11,506 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-29 20:49:11,506 INFO L408 AbstractCegarLoop]: === Iteration 10 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 20:49:11,506 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-29 20:49:11,514 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 20:49:11,527 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 20:49:11,530 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 20:49:11,568 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-29 20:49:11,568 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 20:49:11,649 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-29 20:49:11,679 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 20:49:11,679 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 15 [2018-03-29 20:49:11,680 INFO L442 AbstractCegarLoop]: Interpolant automaton has 16 states [2018-03-29 20:49:11,680 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2018-03-29 20:49:11,680 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=54, Invalid=186, Unknown=0, NotChecked=0, Total=240 [2018-03-29 20:49:11,680 INFO L87 Difference]: Start difference. First operand 199 states and 248 transitions. Second operand 16 states. [2018-03-29 20:49:11,968 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 20:49:11,968 INFO L93 Difference]: Finished difference Result 240 states and 304 transitions. [2018-03-29 20:49:11,969 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2018-03-29 20:49:11,969 INFO L78 Accepts]: Start accepts. Automaton has 16 states. Word has length 65 [2018-03-29 20:49:11,969 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 20:49:11,970 INFO L225 Difference]: With dead ends: 240 [2018-03-29 20:49:11,971 INFO L226 Difference]: Without dead ends: 238 [2018-03-29 20:49:11,971 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-29 20:49:11,972 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 238 states. [2018-03-29 20:49:11,981 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 238 to 235. [2018-03-29 20:49:11,982 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 235 states. [2018-03-29 20:49:11,983 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 235 states to 235 states and 292 transitions. [2018-03-29 20:49:11,983 INFO L78 Accepts]: Start accepts. Automaton has 235 states and 292 transitions. Word has length 65 [2018-03-29 20:49:11,984 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 20:49:11,984 INFO L459 AbstractCegarLoop]: Abstraction has 235 states and 292 transitions. [2018-03-29 20:49:11,984 INFO L460 AbstractCegarLoop]: Interpolant automaton has 16 states. [2018-03-29 20:49:11,984 INFO L276 IsEmpty]: Start isEmpty. Operand 235 states and 292 transitions. [2018-03-29 20:49:11,985 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 94 [2018-03-29 20:49:11,985 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 20:49:11,985 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-29 20:49:11,985 INFO L408 AbstractCegarLoop]: === Iteration 11 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 20:49:11,985 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-29 20:49:11,991 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 20:49:12,004 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 20:49:12,006 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 20:49:12,146 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-29 20:49:12,146 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 20:49:12,384 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-29 20:49:12,406 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 20:49:12,406 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 21] total 30 [2018-03-29 20:49:12,406 INFO L442 AbstractCegarLoop]: Interpolant automaton has 30 states [2018-03-29 20:49:12,406 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2018-03-29 20:49:12,407 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=139, Invalid=731, Unknown=0, NotChecked=0, Total=870 [2018-03-29 20:49:12,407 INFO L87 Difference]: Start difference. First operand 235 states and 292 transitions. Second operand 30 states. [2018-03-29 20:49:12,884 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 20:49:12,884 INFO L93 Difference]: Finished difference Result 314 states and 385 transitions. [2018-03-29 20:49:12,884 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2018-03-29 20:49:12,884 INFO L78 Accepts]: Start accepts. Automaton has 30 states. Word has length 93 [2018-03-29 20:49:12,885 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 20:49:12,886 INFO L225 Difference]: With dead ends: 314 [2018-03-29 20:49:12,887 INFO L226 Difference]: Without dead ends: 235 [2018-03-29 20:49:12,888 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-29 20:49:12,889 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 235 states. [2018-03-29 20:49:12,898 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 235 to 235. [2018-03-29 20:49:12,899 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 235 states. [2018-03-29 20:49:12,900 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 235 states to 235 states and 291 transitions. [2018-03-29 20:49:12,901 INFO L78 Accepts]: Start accepts. Automaton has 235 states and 291 transitions. Word has length 93 [2018-03-29 20:49:12,901 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 20:49:12,901 INFO L459 AbstractCegarLoop]: Abstraction has 235 states and 291 transitions. [2018-03-29 20:49:12,901 INFO L460 AbstractCegarLoop]: Interpolant automaton has 30 states. [2018-03-29 20:49:12,901 INFO L276 IsEmpty]: Start isEmpty. Operand 235 states and 291 transitions. [2018-03-29 20:49:12,903 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 101 [2018-03-29 20:49:12,903 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 20:49:12,903 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-29 20:49:12,903 INFO L408 AbstractCegarLoop]: === Iteration 12 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 20:49:12,903 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-29 20:49:12,913 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 20:49:12,929 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 20:49:12,932 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 20:49:13,136 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-29 20:49:13,136 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 20:49:13,315 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-29 20:49:13,335 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 20:49:13,336 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [25, 25] total 36 [2018-03-29 20:49:13,336 INFO L442 AbstractCegarLoop]: Interpolant automaton has 36 states [2018-03-29 20:49:13,336 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 36 interpolants. [2018-03-29 20:49:13,336 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=191, Invalid=1069, Unknown=0, NotChecked=0, Total=1260 [2018-03-29 20:49:13,337 INFO L87 Difference]: Start difference. First operand 235 states and 291 transitions. Second operand 36 states. [2018-03-29 20:49:13,843 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 20:49:13,843 INFO L93 Difference]: Finished difference Result 314 states and 384 transitions. [2018-03-29 20:49:13,843 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 40 states. [2018-03-29 20:49:13,843 INFO L78 Accepts]: Start accepts. Automaton has 36 states. Word has length 100 [2018-03-29 20:49:13,844 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 20:49:13,845 INFO L225 Difference]: With dead ends: 314 [2018-03-29 20:49:13,845 INFO L226 Difference]: Without dead ends: 235 [2018-03-29 20:49:13,846 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-29 20:49:13,846 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 235 states. [2018-03-29 20:49:13,856 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 235 to 235. [2018-03-29 20:49:13,856 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 235 states. [2018-03-29 20:49:13,858 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 235 states to 235 states and 290 transitions. [2018-03-29 20:49:13,858 INFO L78 Accepts]: Start accepts. Automaton has 235 states and 290 transitions. Word has length 100 [2018-03-29 20:49:13,858 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 20:49:13,858 INFO L459 AbstractCegarLoop]: Abstraction has 235 states and 290 transitions. [2018-03-29 20:49:13,858 INFO L460 AbstractCegarLoop]: Interpolant automaton has 36 states. [2018-03-29 20:49:13,858 INFO L276 IsEmpty]: Start isEmpty. Operand 235 states and 290 transitions. [2018-03-29 20:49:13,860 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 108 [2018-03-29 20:49:13,860 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 20:49:13,860 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-29 20:49:13,860 INFO L408 AbstractCegarLoop]: === Iteration 13 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 20:49:13,860 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-29 20:49:13,870 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 20:49:13,885 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 20:49:13,889 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 20:49:14,194 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-29 20:49:14,194 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 20:49:14,432 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-29 20:49:14,453 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 20:49:14,454 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [29, 29] total 42 [2018-03-29 20:49:14,454 INFO L442 AbstractCegarLoop]: Interpolant automaton has 42 states [2018-03-29 20:49:14,454 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 42 interpolants. [2018-03-29 20:49:14,455 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=251, Invalid=1471, Unknown=0, NotChecked=0, Total=1722 [2018-03-29 20:49:14,455 INFO L87 Difference]: Start difference. First operand 235 states and 290 transitions. Second operand 42 states. [2018-03-29 20:49:15,229 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 20:49:15,229 INFO L93 Difference]: Finished difference Result 314 states and 383 transitions. [2018-03-29 20:49:15,229 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 47 states. [2018-03-29 20:49:15,229 INFO L78 Accepts]: Start accepts. Automaton has 42 states. Word has length 107 [2018-03-29 20:49:15,230 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 20:49:15,231 INFO L225 Difference]: With dead ends: 314 [2018-03-29 20:49:15,231 INFO L226 Difference]: Without dead ends: 235 [2018-03-29 20:49:15,233 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 244 GetRequests, 159 SyntacticMatches, 14 SemanticMatches, 71 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1386 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=818, Invalid=4438, Unknown=0, NotChecked=0, Total=5256 [2018-03-29 20:49:15,234 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 235 states. [2018-03-29 20:49:15,243 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 235 to 235. [2018-03-29 20:49:15,243 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 235 states. [2018-03-29 20:49:15,245 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 235 states to 235 states and 289 transitions. [2018-03-29 20:49:15,245 INFO L78 Accepts]: Start accepts. Automaton has 235 states and 289 transitions. Word has length 107 [2018-03-29 20:49:15,246 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 20:49:15,246 INFO L459 AbstractCegarLoop]: Abstraction has 235 states and 289 transitions. [2018-03-29 20:49:15,246 INFO L460 AbstractCegarLoop]: Interpolant automaton has 42 states. [2018-03-29 20:49:15,246 INFO L276 IsEmpty]: Start isEmpty. Operand 235 states and 289 transitions. [2018-03-29 20:49:15,248 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 115 [2018-03-29 20:49:15,248 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 20:49:15,248 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-29 20:49:15,248 INFO L408 AbstractCegarLoop]: === Iteration 14 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 20:49:15,248 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-29 20:49:15,257 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 20:49:15,276 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 20:49:15,279 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 20:49:15,580 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-29 20:49:15,580 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 20:49:15,904 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-29 20:49:15,925 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 20:49:15,925 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [33, 33] total 48 [2018-03-29 20:49:15,925 INFO L442 AbstractCegarLoop]: Interpolant automaton has 48 states [2018-03-29 20:49:15,925 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 48 interpolants. [2018-03-29 20:49:15,926 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=319, Invalid=1937, Unknown=0, NotChecked=0, Total=2256 [2018-03-29 20:49:15,926 INFO L87 Difference]: Start difference. First operand 235 states and 289 transitions. Second operand 48 states. [2018-03-29 20:49:16,672 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 20:49:16,672 INFO L93 Difference]: Finished difference Result 320 states and 389 transitions. [2018-03-29 20:49:16,672 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 54 states. [2018-03-29 20:49:16,672 INFO L78 Accepts]: Start accepts. Automaton has 48 states. Word has length 114 [2018-03-29 20:49:16,673 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 20:49:16,674 INFO L225 Difference]: With dead ends: 320 [2018-03-29 20:49:16,674 INFO L226 Difference]: Without dead ends: 235 [2018-03-29 20:49:16,676 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 263 GetRequests, 165 SyntacticMatches, 16 SemanticMatches, 82 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1873 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=1060, Invalid=5912, Unknown=0, NotChecked=0, Total=6972 [2018-03-29 20:49:16,676 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 235 states. [2018-03-29 20:49:16,685 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 235 to 235. [2018-03-29 20:49:16,685 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 235 states. [2018-03-29 20:49:16,687 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 235 states to 235 states and 288 transitions. [2018-03-29 20:49:16,687 INFO L78 Accepts]: Start accepts. Automaton has 235 states and 288 transitions. Word has length 114 [2018-03-29 20:49:16,687 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 20:49:16,688 INFO L459 AbstractCegarLoop]: Abstraction has 235 states and 288 transitions. [2018-03-29 20:49:16,688 INFO L460 AbstractCegarLoop]: Interpolant automaton has 48 states. [2018-03-29 20:49:16,688 INFO L276 IsEmpty]: Start isEmpty. Operand 235 states and 288 transitions. [2018-03-29 20:49:16,689 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 119 [2018-03-29 20:49:16,690 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 20:49:16,690 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-29 20:49:16,690 INFO L408 AbstractCegarLoop]: === Iteration 15 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 20:49:16,690 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-29 20:49:16,697 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 20:49:16,713 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 20:49:16,716 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 20:49:17,125 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-29 20:49:17,126 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 20:49:18,300 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-29 20:49:18,322 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 20:49:18,332 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [32, 32] total 63 [2018-03-29 20:49:18,333 INFO L442 AbstractCegarLoop]: Interpolant automaton has 64 states [2018-03-29 20:49:18,333 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 64 interpolants. [2018-03-29 20:49:18,334 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=606, Invalid=3426, Unknown=0, NotChecked=0, Total=4032 [2018-03-29 20:49:18,334 INFO L87 Difference]: Start difference. First operand 235 states and 288 transitions. Second operand 64 states. [2018-03-29 20:49:23,803 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 20:49:23,803 INFO L93 Difference]: Finished difference Result 407 states and 539 transitions. [2018-03-29 20:49:23,803 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 93 states. [2018-03-29 20:49:23,803 INFO L78 Accepts]: Start accepts. Automaton has 64 states. Word has length 118 [2018-03-29 20:49:23,804 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 20:49:23,805 INFO L225 Difference]: With dead ends: 407 [2018-03-29 20:49:23,805 INFO L226 Difference]: Without dead ends: 405 [2018-03-29 20:49:23,809 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 309 GetRequests, 173 SyntacticMatches, 0 SemanticMatches, 136 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3452 ImplicationChecksByTransitivity, 5.2s TimeCoverageRelationStatistics Valid=4624, Invalid=14282, Unknown=0, NotChecked=0, Total=18906 [2018-03-29 20:49:23,810 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 405 states. [2018-03-29 20:49:23,820 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 405 to 379. [2018-03-29 20:49:23,821 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 379 states. [2018-03-29 20:49:23,823 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 379 states to 379 states and 480 transitions. [2018-03-29 20:49:23,823 INFO L78 Accepts]: Start accepts. Automaton has 379 states and 480 transitions. Word has length 118 [2018-03-29 20:49:23,823 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 20:49:23,823 INFO L459 AbstractCegarLoop]: Abstraction has 379 states and 480 transitions. [2018-03-29 20:49:23,823 INFO L460 AbstractCegarLoop]: Interpolant automaton has 64 states. [2018-03-29 20:49:23,824 INFO L276 IsEmpty]: Start isEmpty. Operand 379 states and 480 transitions. [2018-03-29 20:49:23,825 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 122 [2018-03-29 20:49:23,825 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 20:49:23,825 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-29 20:49:23,825 INFO L408 AbstractCegarLoop]: === Iteration 16 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 20:49:23,825 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-29 20:49:23,844 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 20:49:23,868 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 20:49:23,872 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 20:49:23,970 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-29 20:49:23,971 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 20:49:24,216 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-29 20:49:24,236 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 20:49:24,237 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 31 [2018-03-29 20:49:24,237 INFO L442 AbstractCegarLoop]: Interpolant automaton has 32 states [2018-03-29 20:49:24,237 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2018-03-29 20:49:24,238 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=174, Invalid=818, Unknown=0, NotChecked=0, Total=992 [2018-03-29 20:49:24,238 INFO L87 Difference]: Start difference. First operand 379 states and 480 transitions. Second operand 32 states. [2018-03-29 20:49:25,431 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 20:49:25,431 INFO L93 Difference]: Finished difference Result 456 states and 588 transitions. [2018-03-29 20:49:25,431 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 45 states. [2018-03-29 20:49:25,431 INFO L78 Accepts]: Start accepts. Automaton has 32 states. Word has length 121 [2018-03-29 20:49:25,431 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 20:49:25,433 INFO L225 Difference]: With dead ends: 456 [2018-03-29 20:49:25,433 INFO L226 Difference]: Without dead ends: 454 [2018-03-29 20:49:25,434 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 275 GetRequests, 211 SyntacticMatches, 0 SemanticMatches, 64 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 716 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=1096, Invalid=3194, Unknown=0, NotChecked=0, Total=4290 [2018-03-29 20:49:25,435 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 454 states. [2018-03-29 20:49:25,447 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 454 to 451. [2018-03-29 20:49:25,447 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 451 states. [2018-03-29 20:49:25,449 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 451 states to 451 states and 568 transitions. [2018-03-29 20:49:25,449 INFO L78 Accepts]: Start accepts. Automaton has 451 states and 568 transitions. Word has length 121 [2018-03-29 20:49:25,449 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 20:49:25,449 INFO L459 AbstractCegarLoop]: Abstraction has 451 states and 568 transitions. [2018-03-29 20:49:25,450 INFO L460 AbstractCegarLoop]: Interpolant automaton has 32 states. [2018-03-29 20:49:25,450 INFO L276 IsEmpty]: Start isEmpty. Operand 451 states and 568 transitions. [2018-03-29 20:49:25,451 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 178 [2018-03-29 20:49:25,451 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 20:49:25,451 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-29 20:49:25,452 INFO L408 AbstractCegarLoop]: === Iteration 17 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 20:49:25,452 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-29 20:49:25,464 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 20:49:25,490 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 20:49:25,494 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 20:49:25,863 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-29 20:49:25,863 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 20:49:26,219 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-29 20:49:26,239 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 20:49:26,240 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [37, 37] total 54 [2018-03-29 20:49:26,240 INFO L442 AbstractCegarLoop]: Interpolant automaton has 54 states [2018-03-29 20:49:26,240 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 54 interpolants. [2018-03-29 20:49:26,241 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=395, Invalid=2467, Unknown=0, NotChecked=0, Total=2862 [2018-03-29 20:49:26,241 INFO L87 Difference]: Start difference. First operand 451 states and 568 transitions. Second operand 54 states. [2018-03-29 20:49:27,150 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 20:49:27,150 INFO L93 Difference]: Finished difference Result 602 states and 749 transitions. [2018-03-29 20:49:27,150 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 61 states. [2018-03-29 20:49:27,150 INFO L78 Accepts]: Start accepts. Automaton has 54 states. Word has length 177 [2018-03-29 20:49:27,151 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 20:49:27,153 INFO L225 Difference]: With dead ends: 602 [2018-03-29 20:49:27,153 INFO L226 Difference]: Without dead ends: 451 [2018-03-29 20:49:27,154 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 394 GetRequests, 283 SyntacticMatches, 18 SemanticMatches, 93 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2433 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=1333, Invalid=7597, Unknown=0, NotChecked=0, Total=8930 [2018-03-29 20:49:27,154 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 451 states. [2018-03-29 20:49:27,165 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 451 to 451. [2018-03-29 20:49:27,165 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 451 states. [2018-03-29 20:49:27,167 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 451 states to 451 states and 567 transitions. [2018-03-29 20:49:27,167 INFO L78 Accepts]: Start accepts. Automaton has 451 states and 567 transitions. Word has length 177 [2018-03-29 20:49:27,167 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 20:49:27,167 INFO L459 AbstractCegarLoop]: Abstraction has 451 states and 567 transitions. [2018-03-29 20:49:27,167 INFO L460 AbstractCegarLoop]: Interpolant automaton has 54 states. [2018-03-29 20:49:27,167 INFO L276 IsEmpty]: Start isEmpty. Operand 451 states and 567 transitions. [2018-03-29 20:49:27,169 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 185 [2018-03-29 20:49:27,169 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 20:49:27,169 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-29 20:49:27,169 INFO L408 AbstractCegarLoop]: === Iteration 18 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 20:49:27,170 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-29 20:49:27,177 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 20:49:27,206 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 20:49:27,211 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 20:49:27,594 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-29 20:49:27,595 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 20:49:28,029 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-29 20:49:28,050 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 20:49:28,050 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [41, 41] total 60 [2018-03-29 20:49:28,051 INFO L442 AbstractCegarLoop]: Interpolant automaton has 60 states [2018-03-29 20:49:28,051 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 60 interpolants. [2018-03-29 20:49:28,052 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=479, Invalid=3061, Unknown=0, NotChecked=0, Total=3540 [2018-03-29 20:49:28,052 INFO L87 Difference]: Start difference. First operand 451 states and 567 transitions. Second operand 60 states. [2018-03-29 20:49:29,243 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 20:49:29,243 INFO L93 Difference]: Finished difference Result 602 states and 748 transitions. [2018-03-29 20:49:29,277 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 68 states. [2018-03-29 20:49:29,278 INFO L78 Accepts]: Start accepts. Automaton has 60 states. Word has length 184 [2018-03-29 20:49:29,278 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 20:49:29,279 INFO L225 Difference]: With dead ends: 602 [2018-03-29 20:49:29,280 INFO L226 Difference]: Without dead ends: 451 [2018-03-29 20:49:29,281 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 413 GetRequests, 289 SyntacticMatches, 20 SemanticMatches, 104 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3066 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=1637, Invalid=9493, Unknown=0, NotChecked=0, Total=11130 [2018-03-29 20:49:29,281 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 451 states. [2018-03-29 20:49:29,294 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 451 to 451. [2018-03-29 20:49:29,294 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 451 states. [2018-03-29 20:49:29,297 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 451 states to 451 states and 566 transitions. [2018-03-29 20:49:29,297 INFO L78 Accepts]: Start accepts. Automaton has 451 states and 566 transitions. Word has length 184 [2018-03-29 20:49:29,298 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 20:49:29,298 INFO L459 AbstractCegarLoop]: Abstraction has 451 states and 566 transitions. [2018-03-29 20:49:29,298 INFO L460 AbstractCegarLoop]: Interpolant automaton has 60 states. [2018-03-29 20:49:29,298 INFO L276 IsEmpty]: Start isEmpty. Operand 451 states and 566 transitions. [2018-03-29 20:49:29,301 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 192 [2018-03-29 20:49:29,301 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 20:49:29,301 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-29 20:49:29,301 INFO L408 AbstractCegarLoop]: === Iteration 19 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 20:49:29,302 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-29 20:49:29,310 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 20:49:29,348 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 20:49:29,353 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 20:49:29,924 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-29 20:49:29,924 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 20:49:30,438 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-29 20:49:30,458 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 20:49:30,459 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [45, 45] total 66 [2018-03-29 20:49:30,459 INFO L442 AbstractCegarLoop]: Interpolant automaton has 66 states [2018-03-29 20:49:30,459 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 66 interpolants. [2018-03-29 20:49:30,460 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=571, Invalid=3719, Unknown=0, NotChecked=0, Total=4290 [2018-03-29 20:49:30,460 INFO L87 Difference]: Start difference. First operand 451 states and 566 transitions. Second operand 66 states. [2018-03-29 20:49:31,694 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 20:49:31,695 INFO L93 Difference]: Finished difference Result 602 states and 747 transitions. [2018-03-29 20:49:31,695 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 75 states. [2018-03-29 20:49:31,695 INFO L78 Accepts]: Start accepts. Automaton has 66 states. Word has length 191 [2018-03-29 20:49:31,695 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 20:49:31,697 INFO L225 Difference]: With dead ends: 602 [2018-03-29 20:49:31,697 INFO L226 Difference]: Without dead ends: 451 [2018-03-29 20:49:31,699 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-29 20:49:31,699 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 451 states. [2018-03-29 20:49:31,711 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 451 to 451. [2018-03-29 20:49:31,711 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 451 states. [2018-03-29 20:49:31,713 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 451 states to 451 states and 565 transitions. [2018-03-29 20:49:31,713 INFO L78 Accepts]: Start accepts. Automaton has 451 states and 565 transitions. Word has length 191 [2018-03-29 20:49:31,714 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 20:49:31,714 INFO L459 AbstractCegarLoop]: Abstraction has 451 states and 565 transitions. [2018-03-29 20:49:31,714 INFO L460 AbstractCegarLoop]: Interpolant automaton has 66 states. [2018-03-29 20:49:31,714 INFO L276 IsEmpty]: Start isEmpty. Operand 451 states and 565 transitions. [2018-03-29 20:49:31,716 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 199 [2018-03-29 20:49:31,716 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 20:49:31,717 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-29 20:49:31,717 INFO L408 AbstractCegarLoop]: === Iteration 20 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 20:49:31,717 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-29 20:49:31,723 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 20:49:31,749 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 20:49:31,759 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 20:49:32,284 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-29 20:49:32,284 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 20:49:32,887 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-29 20:49:32,908 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 20:49:32,908 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [49, 49] total 72 [2018-03-29 20:49:32,908 INFO L442 AbstractCegarLoop]: Interpolant automaton has 72 states [2018-03-29 20:49:32,909 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 72 interpolants. [2018-03-29 20:49:32,909 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=671, Invalid=4441, Unknown=0, NotChecked=0, Total=5112 [2018-03-29 20:49:32,909 INFO L87 Difference]: Start difference. First operand 451 states and 565 transitions. Second operand 72 states. [2018-03-29 20:49:34,433 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 20:49:34,434 INFO L93 Difference]: Finished difference Result 602 states and 746 transitions. [2018-03-29 20:49:34,434 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 82 states. [2018-03-29 20:49:34,434 INFO L78 Accepts]: Start accepts. Automaton has 72 states. Word has length 198 [2018-03-29 20:49:34,434 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 20:49:34,436 INFO L225 Difference]: With dead ends: 602 [2018-03-29 20:49:34,436 INFO L226 Difference]: Without dead ends: 451 [2018-03-29 20:49:34,438 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-29 20:49:34,438 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 451 states. [2018-03-29 20:49:34,446 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 451 to 451. [2018-03-29 20:49:34,447 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 451 states. [2018-03-29 20:49:34,448 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 451 states to 451 states and 564 transitions. [2018-03-29 20:49:34,448 INFO L78 Accepts]: Start accepts. Automaton has 451 states and 564 transitions. Word has length 198 [2018-03-29 20:49:34,448 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 20:49:34,448 INFO L459 AbstractCegarLoop]: Abstraction has 451 states and 564 transitions. [2018-03-29 20:49:34,448 INFO L460 AbstractCegarLoop]: Interpolant automaton has 72 states. [2018-03-29 20:49:34,448 INFO L276 IsEmpty]: Start isEmpty. Operand 451 states and 564 transitions. [2018-03-29 20:49:34,450 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 206 [2018-03-29 20:49:34,450 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 20:49:34,450 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-29 20:49:34,450 INFO L408 AbstractCegarLoop]: === Iteration 21 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 20:49:34,450 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-29 20:49:34,456 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 20:49:34,487 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 20:49:34,491 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 20:49:35,186 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-29 20:49:35,186 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 20:49:35,909 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-29 20:49:35,929 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 20:49:35,929 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [53, 53] total 78 [2018-03-29 20:49:35,930 INFO L442 AbstractCegarLoop]: Interpolant automaton has 78 states [2018-03-29 20:49:35,930 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 78 interpolants. [2018-03-29 20:49:35,930 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=779, Invalid=5227, Unknown=0, NotChecked=0, Total=6006 [2018-03-29 20:49:35,931 INFO L87 Difference]: Start difference. First operand 451 states and 564 transitions. Second operand 78 states. [2018-03-29 20:49:37,728 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 20:49:37,728 INFO L93 Difference]: Finished difference Result 602 states and 745 transitions. [2018-03-29 20:49:37,728 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 89 states. [2018-03-29 20:49:37,728 INFO L78 Accepts]: Start accepts. Automaton has 78 states. Word has length 205 [2018-03-29 20:49:37,729 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 20:49:37,730 INFO L225 Difference]: With dead ends: 602 [2018-03-29 20:49:37,730 INFO L226 Difference]: Without dead ends: 451 [2018-03-29 20:49:37,731 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 470 GetRequests, 307 SyntacticMatches, 26 SemanticMatches, 137 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5403 ImplicationChecksByTransitivity, 2.3s TimeCoverageRelationStatistics Valid=2735, Invalid=16447, Unknown=0, NotChecked=0, Total=19182 [2018-03-29 20:49:37,732 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 451 states. [2018-03-29 20:49:37,745 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 451 to 451. [2018-03-29 20:49:37,745 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 451 states. [2018-03-29 20:49:37,747 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 451 states to 451 states and 563 transitions. [2018-03-29 20:49:37,747 INFO L78 Accepts]: Start accepts. Automaton has 451 states and 563 transitions. Word has length 205 [2018-03-29 20:49:37,748 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 20:49:37,748 INFO L459 AbstractCegarLoop]: Abstraction has 451 states and 563 transitions. [2018-03-29 20:49:37,748 INFO L460 AbstractCegarLoop]: Interpolant automaton has 78 states. [2018-03-29 20:49:37,748 INFO L276 IsEmpty]: Start isEmpty. Operand 451 states and 563 transitions. [2018-03-29 20:49:37,750 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 213 [2018-03-29 20:49:37,750 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 20:49:37,751 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-29 20:49:37,751 INFO L408 AbstractCegarLoop]: === Iteration 22 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 20:49:37,751 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-29 20:49:37,760 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 20:49:37,797 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 20:49:37,802 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 20:49:38,519 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-29 20:49:38,519 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 20:49:39,326 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-29 20:49:39,347 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 20:49:39,347 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [57, 57] total 84 [2018-03-29 20:49:39,378 INFO L442 AbstractCegarLoop]: Interpolant automaton has 84 states [2018-03-29 20:49:39,378 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 84 interpolants. [2018-03-29 20:49:39,379 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=895, Invalid=6077, Unknown=0, NotChecked=0, Total=6972 [2018-03-29 20:49:39,379 INFO L87 Difference]: Start difference. First operand 451 states and 563 transitions. Second operand 84 states. [2018-03-29 20:49:41,228 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 20:49:41,228 INFO L93 Difference]: Finished difference Result 602 states and 744 transitions. [2018-03-29 20:49:41,228 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 96 states. [2018-03-29 20:49:41,228 INFO L78 Accepts]: Start accepts. Automaton has 84 states. Word has length 212 [2018-03-29 20:49:41,229 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 20:49:41,231 INFO L225 Difference]: With dead ends: 602 [2018-03-29 20:49:41,231 INFO L226 Difference]: Without dead ends: 451 [2018-03-29 20:49:41,233 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-29 20:49:41,233 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 451 states. [2018-03-29 20:49:41,247 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 451 to 451. [2018-03-29 20:49:41,248 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 451 states. [2018-03-29 20:49:41,250 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 451 states to 451 states and 562 transitions. [2018-03-29 20:49:41,250 INFO L78 Accepts]: Start accepts. Automaton has 451 states and 562 transitions. Word has length 212 [2018-03-29 20:49:41,250 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 20:49:41,250 INFO L459 AbstractCegarLoop]: Abstraction has 451 states and 562 transitions. [2018-03-29 20:49:41,250 INFO L460 AbstractCegarLoop]: Interpolant automaton has 84 states. [2018-03-29 20:49:41,251 INFO L276 IsEmpty]: Start isEmpty. Operand 451 states and 562 transitions. [2018-03-29 20:49:41,252 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 220 [2018-03-29 20:49:41,253 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 20:49:41,253 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-29 20:49:41,253 INFO L408 AbstractCegarLoop]: === Iteration 23 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 20:49:41,253 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-29 20:49:41,262 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 20:49:41,300 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 20:49:41,305 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 20:49:42,133 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-29 20:49:42,133 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 20:49:43,093 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-29 20:49:43,114 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 20:49:43,114 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [61, 61] total 90 [2018-03-29 20:49:43,114 INFO L442 AbstractCegarLoop]: Interpolant automaton has 90 states [2018-03-29 20:49:43,114 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 90 interpolants. [2018-03-29 20:49:43,115 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1019, Invalid=6991, Unknown=0, NotChecked=0, Total=8010 [2018-03-29 20:49:43,115 INFO L87 Difference]: Start difference. First operand 451 states and 562 transitions. Second operand 90 states. [2018-03-29 20:49:45,239 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 20:49:45,239 INFO L93 Difference]: Finished difference Result 602 states and 743 transitions. [2018-03-29 20:49:45,278 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 103 states. [2018-03-29 20:49:45,278 INFO L78 Accepts]: Start accepts. Automaton has 90 states. Word has length 219 [2018-03-29 20:49:45,279 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 20:49:45,280 INFO L225 Difference]: With dead ends: 602 [2018-03-29 20:49:45,280 INFO L226 Difference]: Without dead ends: 451 [2018-03-29 20:49:45,282 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-29 20:49:45,282 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 451 states. [2018-03-29 20:49:45,294 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 451 to 451. [2018-03-29 20:49:45,295 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 451 states. [2018-03-29 20:49:45,297 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 451 states to 451 states and 561 transitions. [2018-03-29 20:49:45,297 INFO L78 Accepts]: Start accepts. Automaton has 451 states and 561 transitions. Word has length 219 [2018-03-29 20:49:45,297 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 20:49:45,298 INFO L459 AbstractCegarLoop]: Abstraction has 451 states and 561 transitions. [2018-03-29 20:49:45,298 INFO L460 AbstractCegarLoop]: Interpolant automaton has 90 states. [2018-03-29 20:49:45,298 INFO L276 IsEmpty]: Start isEmpty. Operand 451 states and 561 transitions. [2018-03-29 20:49:45,300 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 227 [2018-03-29 20:49:45,300 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 20:49:45,300 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-29 20:49:45,300 INFO L408 AbstractCegarLoop]: === Iteration 24 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 20:49:45,301 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-29 20:49:45,309 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 20:49:45,347 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 20:49:45,352 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 20:49:46,265 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-29 20:49:46,265 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 20:49:47,334 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-29 20:49:47,355 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 20:49:47,355 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [65, 65] total 96 [2018-03-29 20:49:47,356 INFO L442 AbstractCegarLoop]: Interpolant automaton has 96 states [2018-03-29 20:49:47,356 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 96 interpolants. [2018-03-29 20:49:47,357 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1151, Invalid=7969, Unknown=0, NotChecked=0, Total=9120 [2018-03-29 20:49:47,357 INFO L87 Difference]: Start difference. First operand 451 states and 561 transitions. Second operand 96 states. [2018-03-29 20:49:49,854 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 20:49:49,854 INFO L93 Difference]: Finished difference Result 608 states and 749 transitions. [2018-03-29 20:49:49,855 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 110 states. [2018-03-29 20:49:49,855 INFO L78 Accepts]: Start accepts. Automaton has 96 states. Word has length 226 [2018-03-29 20:49:49,855 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 20:49:49,856 INFO L225 Difference]: With dead ends: 608 [2018-03-29 20:49:49,857 INFO L226 Difference]: Without dead ends: 451 [2018-03-29 20:49:49,858 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-29 20:49:49,858 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 451 states. [2018-03-29 20:49:49,866 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 451 to 451. [2018-03-29 20:49:49,866 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 451 states. [2018-03-29 20:49:49,868 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 451 states to 451 states and 560 transitions. [2018-03-29 20:49:49,868 INFO L78 Accepts]: Start accepts. Automaton has 451 states and 560 transitions. Word has length 226 [2018-03-29 20:49:49,868 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 20:49:49,868 INFO L459 AbstractCegarLoop]: Abstraction has 451 states and 560 transitions. [2018-03-29 20:49:49,868 INFO L460 AbstractCegarLoop]: Interpolant automaton has 96 states. [2018-03-29 20:49:49,868 INFO L276 IsEmpty]: Start isEmpty. Operand 451 states and 560 transitions. [2018-03-29 20:49:49,869 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 231 [2018-03-29 20:49:49,870 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 20:49:49,870 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-29 20:49:49,870 INFO L408 AbstractCegarLoop]: === Iteration 25 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 20:49:49,870 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-29 20:49:49,879 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 20:49:49,922 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 20:49:49,932 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 20:49:51,248 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-29 20:49:51,249 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 20:49:54,613 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-29 20:49:54,633 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 20:49:54,633 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [64, 64] total 127 [2018-03-29 20:49:54,634 INFO L442 AbstractCegarLoop]: Interpolant automaton has 128 states [2018-03-29 20:49:54,634 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 128 interpolants. [2018-03-29 20:49:54,635 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=2238, Invalid=14018, Unknown=0, NotChecked=0, Total=16256 [2018-03-29 20:49:54,635 INFO L87 Difference]: Start difference. First operand 451 states and 560 transitions. Second operand 128 states. [2018-03-29 20:50:00,567 WARN L151 SmtUtils]: Spent 251ms on a formula simplification. DAG size of input: 252 DAG size of output 12 [2018-03-29 20:50:01,235 WARN L151 SmtUtils]: Spent 234ms on a formula simplification. DAG size of input: 247 DAG size of output 11 [2018-03-29 20:50:01,697 WARN L151 SmtUtils]: Spent 239ms on a formula simplification. DAG size of input: 244 DAG size of output 12 [2018-03-29 20:50:02,360 WARN L151 SmtUtils]: Spent 224ms on a formula simplification. DAG size of input: 239 DAG size of output 11 [2018-03-29 20:50:02,809 WARN L151 SmtUtils]: Spent 223ms on a formula simplification. DAG size of input: 236 DAG size of output 12 [2018-03-29 20:50:03,452 WARN L151 SmtUtils]: Spent 215ms on a formula simplification. DAG size of input: 231 DAG size of output 11 [2018-03-29 20:50:03,896 WARN L151 SmtUtils]: Spent 215ms on a formula simplification. DAG size of input: 228 DAG size of output 12 [2018-03-29 20:50:04,510 WARN L151 SmtUtils]: Spent 197ms on a formula simplification. DAG size of input: 223 DAG size of output 11 [2018-03-29 20:50:04,924 WARN L151 SmtUtils]: Spent 191ms on a formula simplification. DAG size of input: 220 DAG size of output 12 [2018-03-29 20:50:05,537 WARN L151 SmtUtils]: Spent 185ms on a formula simplification. DAG size of input: 215 DAG size of output 11 [2018-03-29 20:50:05,944 WARN L151 SmtUtils]: Spent 180ms on a formula simplification. DAG size of input: 212 DAG size of output 12 [2018-03-29 20:50:06,697 WARN L151 SmtUtils]: Spent 306ms on a formula simplification. DAG size of input: 207 DAG size of output 11 [2018-03-29 20:50:07,116 WARN L151 SmtUtils]: Spent 180ms on a formula simplification. DAG size of input: 204 DAG size of output 12 [2018-03-29 20:50:07,712 WARN L151 SmtUtils]: Spent 176ms on a formula simplification. DAG size of input: 199 DAG size of output 11 [2018-03-29 20:50:08,097 WARN L151 SmtUtils]: Spent 155ms on a formula simplification. DAG size of input: 196 DAG size of output 12 [2018-03-29 20:50:08,640 WARN L151 SmtUtils]: Spent 145ms on a formula simplification. DAG size of input: 191 DAG size of output 11 [2018-03-29 20:50:09,006 WARN L151 SmtUtils]: Spent 139ms on a formula simplification. DAG size of input: 188 DAG size of output 12 [2018-03-29 20:50:09,537 WARN L151 SmtUtils]: Spent 138ms on a formula simplification. DAG size of input: 183 DAG size of output 11 [2018-03-29 20:50:09,886 WARN L151 SmtUtils]: Spent 131ms on a formula simplification. DAG size of input: 180 DAG size of output 12 [2018-03-29 20:50:10,414 WARN L151 SmtUtils]: Spent 125ms on a formula simplification. DAG size of input: 175 DAG size of output 11 [2018-03-29 20:50:10,750 WARN L151 SmtUtils]: Spent 119ms on a formula simplification. DAG size of input: 172 DAG size of output 12 [2018-03-29 20:50:11,242 WARN L151 SmtUtils]: Spent 114ms on a formula simplification. DAG size of input: 167 DAG size of output 11 [2018-03-29 20:50:11,569 WARN L151 SmtUtils]: Spent 111ms on a formula simplification. DAG size of input: 164 DAG size of output 12 [2018-03-29 20:50:12,058 WARN L151 SmtUtils]: Spent 115ms on a formula simplification. DAG size of input: 159 DAG size of output 11 [2018-03-29 20:50:12,376 WARN L151 SmtUtils]: Spent 105ms on a formula simplification. DAG size of input: 156 DAG size of output 12 [2018-03-29 20:50:12,853 WARN L151 SmtUtils]: Spent 107ms on a formula simplification. DAG size of input: 151 DAG size of output 11 [2018-03-29 20:50:22,356 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 20:50:22,356 INFO L93 Difference]: Finished difference Result 791 states and 1059 transitions. [2018-03-29 20:50:22,356 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 189 states. [2018-03-29 20:50:22,356 INFO L78 Accepts]: Start accepts. Automaton has 128 states. Word has length 230 [2018-03-29 20:50:22,357 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 20:50:22,359 INFO L225 Difference]: With dead ends: 791 [2018-03-29 20:50:22,359 INFO L226 Difference]: Without dead ends: 789 [2018-03-29 20:50:22,362 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 613 GetRequests, 333 SyntacticMatches, 0 SemanticMatches, 280 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15068 ImplicationChecksByTransitivity, 26.8s TimeCoverageRelationStatistics Valid=18976, Invalid=60266, Unknown=0, NotChecked=0, Total=79242 [2018-03-29 20:50:22,362 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 789 states. [2018-03-29 20:50:22,380 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 789 to 739. [2018-03-29 20:50:22,380 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 739 states. [2018-03-29 20:50:22,382 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 739 states to 739 states and 944 transitions. [2018-03-29 20:50:22,383 INFO L78 Accepts]: Start accepts. Automaton has 739 states and 944 transitions. Word has length 230 [2018-03-29 20:50:22,383 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 20:50:22,384 INFO L459 AbstractCegarLoop]: Abstraction has 739 states and 944 transitions. [2018-03-29 20:50:22,384 INFO L460 AbstractCegarLoop]: Interpolant automaton has 128 states. [2018-03-29 20:50:22,384 INFO L276 IsEmpty]: Start isEmpty. Operand 739 states and 944 transitions. [2018-03-29 20:50:22,386 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 234 [2018-03-29 20:50:22,387 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 20:50:22,387 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-29 20:50:22,387 INFO L408 AbstractCegarLoop]: === Iteration 26 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 20:50:22,387 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-29 20:50:22,397 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 20:50:22,444 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 20:50:22,450 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 20:50:22,796 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-29 20:50:22,796 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 20:50:23,696 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-29 20:50:23,718 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 20:50:23,718 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [32, 32] total 63 [2018-03-29 20:50:23,718 INFO L442 AbstractCegarLoop]: Interpolant automaton has 64 states [2018-03-29 20:50:23,719 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 64 interpolants. [2018-03-29 20:50:23,719 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=606, Invalid=3426, Unknown=0, NotChecked=0, Total=4032 [2018-03-29 20:50:23,719 INFO L87 Difference]: Start difference. First operand 739 states and 944 transitions. Second operand 64 states. [2018-03-29 20:50:28,805 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 20:50:28,805 INFO L93 Difference]: Finished difference Result 888 states and 1156 transitions. [2018-03-29 20:50:28,805 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 93 states. [2018-03-29 20:50:28,806 INFO L78 Accepts]: Start accepts. Automaton has 64 states. Word has length 233 [2018-03-29 20:50:28,806 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 20:50:28,808 INFO L225 Difference]: With dead ends: 888 [2018-03-29 20:50:28,808 INFO L226 Difference]: Without dead ends: 886 [2018-03-29 20:50:28,810 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 539 GetRequests, 403 SyntacticMatches, 0 SemanticMatches, 136 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3452 ImplicationChecksByTransitivity, 4.8s TimeCoverageRelationStatistics Valid=4624, Invalid=14282, Unknown=0, NotChecked=0, Total=18906 [2018-03-29 20:50:28,810 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 886 states. [2018-03-29 20:50:28,826 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 886 to 883. [2018-03-29 20:50:28,826 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-03-29 20:50:28,830 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1120 transitions. [2018-03-29 20:50:28,830 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1120 transitions. Word has length 233 [2018-03-29 20:50:28,831 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 20:50:28,831 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1120 transitions. [2018-03-29 20:50:28,831 INFO L460 AbstractCegarLoop]: Interpolant automaton has 64 states. [2018-03-29 20:50:28,831 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1120 transitions. [2018-03-29 20:50:28,835 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 346 [2018-03-29 20:50:28,835 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 20:50:28,835 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-29 20:50:28,835 INFO L408 AbstractCegarLoop]: === Iteration 27 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 20:50:28,836 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-29 20:50:28,846 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 20:50:28,900 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 20:50:28,906 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 20:50:30,177 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-29 20:50:30,177 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 20:50:31,450 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-29 20:50:31,471 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 20:50:31,472 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [69, 69] total 102 [2018-03-29 20:50:31,472 INFO L442 AbstractCegarLoop]: Interpolant automaton has 102 states [2018-03-29 20:50:31,472 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 102 interpolants. [2018-03-29 20:50:31,473 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1291, Invalid=9011, Unknown=0, NotChecked=0, Total=10302 [2018-03-29 20:50:31,473 INFO L87 Difference]: Start difference. First operand 883 states and 1120 transitions. Second operand 102 states. [2018-03-29 20:50:34,395 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 20:50:34,396 INFO L93 Difference]: Finished difference Result 1178 states and 1477 transitions. [2018-03-29 20:50:34,396 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 117 states. [2018-03-29 20:50:34,396 INFO L78 Accepts]: Start accepts. Automaton has 102 states. Word has length 345 [2018-03-29 20:50:34,397 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 20:50:34,399 INFO L225 Difference]: With dead ends: 1178 [2018-03-29 20:50:34,399 INFO L226 Difference]: Without dead ends: 883 [2018-03-29 20:50:34,401 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 770 GetRequests, 555 SyntacticMatches, 34 SemanticMatches, 181 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9541 ImplicationChecksByTransitivity, 4.1s TimeCoverageRelationStatistics Valid=4633, Invalid=28673, Unknown=0, NotChecked=0, Total=33306 [2018-03-29 20:50:34,401 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-03-29 20:50:34,413 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-03-29 20:50:34,413 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-03-29 20:50:34,416 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1119 transitions. [2018-03-29 20:50:34,416 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1119 transitions. Word has length 345 [2018-03-29 20:50:34,417 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 20:50:34,417 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1119 transitions. [2018-03-29 20:50:34,417 INFO L460 AbstractCegarLoop]: Interpolant automaton has 102 states. [2018-03-29 20:50:34,417 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1119 transitions. [2018-03-29 20:50:34,420 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 353 [2018-03-29 20:50:34,421 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 20:50:34,421 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-29 20:50:34,421 INFO L408 AbstractCegarLoop]: === Iteration 28 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 20:50:34,421 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-29 20:50:34,432 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 20:50:34,503 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 20:50:34,511 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 20:50:35,675 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-29 20:50:35,675 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 20:50:37,026 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-29 20:50:37,053 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 20:50:37,054 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [73, 73] total 108 [2018-03-29 20:50:37,054 INFO L442 AbstractCegarLoop]: Interpolant automaton has 108 states [2018-03-29 20:50:37,054 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 108 interpolants. [2018-03-29 20:50:37,055 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1439, Invalid=10117, Unknown=0, NotChecked=0, Total=11556 [2018-03-29 20:50:37,055 INFO L87 Difference]: Start difference. First operand 883 states and 1119 transitions. Second operand 108 states. [2018-03-29 20:50:40,381 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 20:50:40,381 INFO L93 Difference]: Finished difference Result 1178 states and 1476 transitions. [2018-03-29 20:50:40,381 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 124 states. [2018-03-29 20:50:40,382 INFO L78 Accepts]: Start accepts. Automaton has 108 states. Word has length 352 [2018-03-29 20:50:40,382 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 20:50:40,384 INFO L225 Difference]: With dead ends: 1178 [2018-03-29 20:50:40,385 INFO L226 Difference]: Without dead ends: 883 [2018-03-29 20:50:40,387 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 789 GetRequests, 561 SyntacticMatches, 36 SemanticMatches, 192 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10758 ImplicationChecksByTransitivity, 4.3s TimeCoverageRelationStatistics Valid=5185, Invalid=32257, Unknown=0, NotChecked=0, Total=37442 [2018-03-29 20:50:40,387 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-03-29 20:50:40,399 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-03-29 20:50:40,399 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-03-29 20:50:40,401 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1118 transitions. [2018-03-29 20:50:40,401 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1118 transitions. Word has length 352 [2018-03-29 20:50:40,402 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 20:50:40,402 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1118 transitions. [2018-03-29 20:50:40,402 INFO L460 AbstractCegarLoop]: Interpolant automaton has 108 states. [2018-03-29 20:50:40,402 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1118 transitions. [2018-03-29 20:50:40,405 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 360 [2018-03-29 20:50:40,405 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 20:50:40,406 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-29 20:50:40,406 INFO L408 AbstractCegarLoop]: === Iteration 29 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 20:50:40,406 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-29 20:50:40,425 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 20:50:40,477 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 20:50:40,482 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 20:50:41,754 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-29 20:50:41,754 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 20:50:43,288 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-29 20:50:43,309 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 20:50:43,309 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [77, 77] total 114 [2018-03-29 20:50:43,309 INFO L442 AbstractCegarLoop]: Interpolant automaton has 114 states [2018-03-29 20:50:43,310 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 114 interpolants. [2018-03-29 20:50:43,310 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1595, Invalid=11287, Unknown=0, NotChecked=0, Total=12882 [2018-03-29 20:50:43,310 INFO L87 Difference]: Start difference. First operand 883 states and 1118 transitions. Second operand 114 states. [2018-03-29 20:50:47,033 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 20:50:47,033 INFO L93 Difference]: Finished difference Result 1178 states and 1475 transitions. [2018-03-29 20:50:47,033 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 131 states. [2018-03-29 20:50:47,033 INFO L78 Accepts]: Start accepts. Automaton has 114 states. Word has length 359 [2018-03-29 20:50:47,034 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 20:50:47,036 INFO L225 Difference]: With dead ends: 1178 [2018-03-29 20:50:47,036 INFO L226 Difference]: Without dead ends: 883 [2018-03-29 20:50:47,038 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 808 GetRequests, 567 SyntacticMatches, 38 SemanticMatches, 203 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12048 ImplicationChecksByTransitivity, 4.8s TimeCoverageRelationStatistics Valid=5768, Invalid=36052, Unknown=0, NotChecked=0, Total=41820 [2018-03-29 20:50:47,039 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-03-29 20:50:47,051 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-03-29 20:50:47,051 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-03-29 20:50:47,053 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1117 transitions. [2018-03-29 20:50:47,053 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1117 transitions. Word has length 359 [2018-03-29 20:50:47,053 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 20:50:47,053 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1117 transitions. [2018-03-29 20:50:47,053 INFO L460 AbstractCegarLoop]: Interpolant automaton has 114 states. [2018-03-29 20:50:47,053 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1117 transitions. [2018-03-29 20:50:47,055 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 367 [2018-03-29 20:50:47,055 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 20:50:47,055 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-29 20:50:47,056 INFO L408 AbstractCegarLoop]: === Iteration 30 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 20:50:47,056 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-29 20:50:47,061 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 20:50:47,106 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 20:50:47,112 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 20:50:48,599 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-29 20:50:48,599 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 20:50:50,464 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-29 20:50:50,485 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 20:50:50,485 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [81, 81] total 120 [2018-03-29 20:50:50,486 INFO L442 AbstractCegarLoop]: Interpolant automaton has 120 states [2018-03-29 20:50:50,486 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 120 interpolants. [2018-03-29 20:50:50,487 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1759, Invalid=12521, Unknown=0, NotChecked=0, Total=14280 [2018-03-29 20:50:50,487 INFO L87 Difference]: Start difference. First operand 883 states and 1117 transitions. Second operand 120 states. [2018-03-29 20:50:54,626 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 20:50:54,626 INFO L93 Difference]: Finished difference Result 1178 states and 1474 transitions. [2018-03-29 20:50:54,658 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 138 states. [2018-03-29 20:50:54,658 INFO L78 Accepts]: Start accepts. Automaton has 120 states. Word has length 366 [2018-03-29 20:50:54,659 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 20:50:54,661 INFO L225 Difference]: With dead ends: 1178 [2018-03-29 20:50:54,661 INFO L226 Difference]: Without dead ends: 883 [2018-03-29 20:50:54,664 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-29 20:50:54,664 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-03-29 20:50:54,676 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-03-29 20:50:54,676 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-03-29 20:50:54,678 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1116 transitions. [2018-03-29 20:50:54,678 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1116 transitions. Word has length 366 [2018-03-29 20:50:54,678 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 20:50:54,678 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1116 transitions. [2018-03-29 20:50:54,678 INFO L460 AbstractCegarLoop]: Interpolant automaton has 120 states. [2018-03-29 20:50:54,679 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1116 transitions. [2018-03-29 20:50:54,680 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 374 [2018-03-29 20:50:54,680 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 20:50:54,680 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-29 20:50:54,681 INFO L408 AbstractCegarLoop]: === Iteration 31 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 20:50:54,681 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-29 20:50:54,686 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 20:50:54,740 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 20:50:54,745 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 20:50:56,215 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-29 20:50:56,215 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 20:50:58,070 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-29 20:50:58,091 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 20:50:58,091 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [85, 85] total 126 [2018-03-29 20:50:58,092 INFO L442 AbstractCegarLoop]: Interpolant automaton has 126 states [2018-03-29 20:50:58,092 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 126 interpolants. [2018-03-29 20:50:58,093 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1931, Invalid=13819, Unknown=0, NotChecked=0, Total=15750 [2018-03-29 20:50:58,093 INFO L87 Difference]: Start difference. First operand 883 states and 1116 transitions. Second operand 126 states. [2018-03-29 20:51:02,171 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 20:51:02,171 INFO L93 Difference]: Finished difference Result 1178 states and 1473 transitions. [2018-03-29 20:51:02,171 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 145 states. [2018-03-29 20:51:02,172 INFO L78 Accepts]: Start accepts. Automaton has 126 states. Word has length 373 [2018-03-29 20:51:02,172 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 20:51:02,174 INFO L225 Difference]: With dead ends: 1178 [2018-03-29 20:51:02,175 INFO L226 Difference]: Without dead ends: 883 [2018-03-29 20:51:02,177 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 846 GetRequests, 579 SyntacticMatches, 42 SemanticMatches, 225 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14847 ImplicationChecksByTransitivity, 5.8s TimeCoverageRelationStatistics Valid=7027, Invalid=44275, Unknown=0, NotChecked=0, Total=51302 [2018-03-29 20:51:02,178 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-03-29 20:51:02,194 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-03-29 20:51:02,194 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-03-29 20:51:02,197 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1115 transitions. [2018-03-29 20:51:02,197 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1115 transitions. Word has length 373 [2018-03-29 20:51:02,197 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 20:51:02,197 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1115 transitions. [2018-03-29 20:51:02,197 INFO L460 AbstractCegarLoop]: Interpolant automaton has 126 states. [2018-03-29 20:51:02,197 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1115 transitions. [2018-03-29 20:51:02,200 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 381 [2018-03-29 20:51:02,200 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 20:51:02,200 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-29 20:51:02,200 INFO L408 AbstractCegarLoop]: === Iteration 32 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 20:51:02,201 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-29 20:51:02,206 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 20:51:02,273 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 20:51:02,280 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 20:51:03,985 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-29 20:51:03,985 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 20:51:06,014 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-29 20:51:06,037 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 20:51:06,037 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [89, 89] total 132 [2018-03-29 20:51:06,038 INFO L442 AbstractCegarLoop]: Interpolant automaton has 132 states [2018-03-29 20:51:06,038 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 132 interpolants. [2018-03-29 20:51:06,039 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=2111, Invalid=15181, Unknown=0, NotChecked=0, Total=17292 [2018-03-29 20:51:06,039 INFO L87 Difference]: Start difference. First operand 883 states and 1115 transitions. Second operand 132 states. [2018-03-29 20:51:10,360 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 20:51:10,361 INFO L93 Difference]: Finished difference Result 1178 states and 1472 transitions. [2018-03-29 20:51:10,361 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 152 states. [2018-03-29 20:51:10,361 INFO L78 Accepts]: Start accepts. Automaton has 132 states. Word has length 380 [2018-03-29 20:51:10,361 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 20:51:10,364 INFO L225 Difference]: With dead ends: 1178 [2018-03-29 20:51:10,364 INFO L226 Difference]: Without dead ends: 883 [2018-03-29 20:51:10,368 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 865 GetRequests, 585 SyntacticMatches, 44 SemanticMatches, 236 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 16356 ImplicationChecksByTransitivity, 6.5s TimeCoverageRelationStatistics Valid=7703, Invalid=48703, Unknown=0, NotChecked=0, Total=56406 [2018-03-29 20:51:10,369 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 883 states. [2018-03-29 20:51:10,388 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 883 to 883. [2018-03-29 20:51:10,388 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-03-29 20:51:10,390 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 1114 transitions. [2018-03-29 20:51:10,391 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 1114 transitions. Word has length 380 [2018-03-29 20:51:10,391 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 20:51:10,391 INFO L459 AbstractCegarLoop]: Abstraction has 883 states and 1114 transitions. [2018-03-29 20:51:10,391 INFO L460 AbstractCegarLoop]: Interpolant automaton has 132 states. [2018-03-29 20:51:10,391 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 1114 transitions. [2018-03-29 20:51:10,394 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 388 [2018-03-29 20:51:10,394 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 20:51:10,395 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-29 20:51:10,395 INFO L408 AbstractCegarLoop]: === Iteration 33 === [mainErr3AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 20:51:10,395 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-29 20:51:10,404 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 20:51:10,466 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 20:51:10,473 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 20:51:12,362 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-29 20:51:12,362 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 20:51:14,534 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-29 20:51:14,556 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 20:51:14,556 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [93, 93] total 138 [2018-03-29 20:51:14,557 INFO L442 AbstractCegarLoop]: Interpolant automaton has 138 states [2018-03-29 20:51:14,558 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 138 interpolants. [2018-03-29 20:51:14,559 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=2299, Invalid=16607, Unknown=0, NotChecked=0, Total=18906 [2018-03-29 20:51:14,559 INFO L87 Difference]: Start difference. First operand 883 states and 1114 transitions. Second operand 138 states. Received shutdown request... [2018-03-29 20:51:16,323 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 79 states. [2018-03-29 20:51:16,324 WARN L519 AbstractCegarLoop]: Verification canceled [2018-03-29 20:51:16,327 WARN L197 ceAbstractionStarter]: Timeout [2018-03-29 20:51:16,327 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 29.03 08:51:16 BoogieIcfgContainer [2018-03-29 20:51:16,328 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-03-29 20:51:16,328 INFO L168 Benchmark]: Toolchain (without parser) took 130434.54 ms. Allocated memory was 302.0 MB in the beginning and 931.1 MB in the end (delta: 629.1 MB). Free memory was 245.5 MB in the beginning and 699.5 MB in the end (delta: -454.0 MB). Peak memory consumption was 175.1 MB. Max. memory is 5.3 GB. [2018-03-29 20:51:16,329 INFO L168 Benchmark]: CDTParser took 0.19 ms. Allocated memory is still 302.0 MB. Free memory is still 263.3 MB. There was no memory consumed. Max. memory is 5.3 GB. [2018-03-29 20:51:16,329 INFO L168 Benchmark]: CACSL2BoogieTranslator took 198.57 ms. Allocated memory is still 302.0 MB. Free memory was 243.5 MB in the beginning and 235.6 MB in the end (delta: 8.0 MB). Peak memory consumption was 8.0 MB. Max. memory is 5.3 GB. [2018-03-29 20:51:16,330 INFO L168 Benchmark]: Boogie Preprocessor took 26.96 ms. Allocated memory is still 302.0 MB. Free memory was 235.6 MB in the beginning and 233.6 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. [2018-03-29 20:51:16,330 INFO L168 Benchmark]: RCFGBuilder took 283.31 ms. Allocated memory was 302.0 MB in the beginning and 465.0 MB in the end (delta: 163.1 MB). Free memory was 233.6 MB in the beginning and 431.2 MB in the end (delta: -197.6 MB). Peak memory consumption was 21.5 MB. Max. memory is 5.3 GB. [2018-03-29 20:51:16,330 INFO L168 Benchmark]: TraceAbstraction took 129919.70 ms. Allocated memory was 465.0 MB in the beginning and 931.1 MB in the end (delta: 466.1 MB). Free memory was 431.2 MB in the beginning and 699.5 MB in the end (delta: -268.4 MB). Peak memory consumption was 197.7 MB. Max. memory is 5.3 GB. [2018-03-29 20:51:16,332 INFO L344 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.19 ms. Allocated memory is still 302.0 MB. Free memory is still 263.3 MB. There was no memory consumed. Max. memory is 5.3 GB. * CACSL2BoogieTranslator took 198.57 ms. Allocated memory is still 302.0 MB. Free memory was 243.5 MB in the beginning and 235.6 MB in the end (delta: 8.0 MB). Peak memory consumption was 8.0 MB. Max. memory is 5.3 GB. * Boogie Preprocessor took 26.96 ms. Allocated memory is still 302.0 MB. Free memory was 235.6 MB in the beginning and 233.6 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. * RCFGBuilder took 283.31 ms. Allocated memory was 302.0 MB in the beginning and 465.0 MB in the end (delta: 163.1 MB). Free memory was 233.6 MB in the beginning and 431.2 MB in the end (delta: -197.6 MB). Peak memory consumption was 21.5 MB. Max. memory is 5.3 GB. * TraceAbstraction took 129919.70 ms. Allocated memory was 465.0 MB in the beginning and 931.1 MB in the end (delta: 466.1 MB). Free memory was 431.2 MB in the beginning and 699.5 MB in the end (delta: -268.4 MB). Peak memory consumption was 197.7 MB. Max. memory is 5.3 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [Line: 26]: Timeout (TraceAbstraction) Unable to prove that array index is always in bounds (line 26). Cancelled while BasicCegarLoop was constructing difference of abstraction (883states) and interpolant automaton (currently 79 states, 138 states before enhancement), while PredicateComparison was comparing new predicate (quantifier-free) to 189 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 79 states, 138 states before enhancement), while PredicateComparison was comparing new predicate (quantifier-free) to 189 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 79 states, 138 states before enhancement), while PredicateComparison was comparing new predicate (quantifier-free) to 189 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 79 states, 138 states before enhancement), while PredicateComparison was comparing new predicate (quantifier-free) to 189 known predicates. - StatisticsResult: Ultimate Automizer benchmark data CFG has 6 procedures, 51 locations, 4 error locations. TIMEOUT Result, 129.8s OverallTime, 33 OverallIterations, 32 TraceHistogramMax, 82.9s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 3471 SDtfs, 11646 SDslu, 62998 SDs, 0 SdLazy, 61497 SolverSat, 7790 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 18.7s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 12969 GetRequests, 8819 SyntacticMatches, 552 SemanticMatches, 3597 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 160325 ImplicationChecksByTransitivity, 98.0s 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, 44.1s 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-29_20-51-16-342.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-29_20-51-16-342.csv Completed graceful shutdown