/usr/bin/java -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerC.xml -s ../../../trunk/examples/settings/default/automizer/svcomp-Reach-32bit-Automizer_Default.epf -i ../../../trunk/examples/svcomp/array-examples/standard_sentinel.i.v+cfa-reducer.c -------------------------------------------------------------------------------- This is Ultimate 0.1.24-fb55353 [2019-11-06 18:46:47,123 INFO L177 SettingsManager]: Resetting all preferences to default values... [2019-11-06 18:46:47,126 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2019-11-06 18:46:47,144 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2019-11-06 18:46:47,144 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2019-11-06 18:46:47,146 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2019-11-06 18:46:47,148 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2019-11-06 18:46:47,152 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2019-11-06 18:46:47,154 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2019-11-06 18:46:47,156 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2019-11-06 18:46:47,157 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2019-11-06 18:46:47,158 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2019-11-06 18:46:47,158 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2019-11-06 18:46:47,159 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2019-11-06 18:46:47,160 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2019-11-06 18:46:47,162 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2019-11-06 18:46:47,163 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2019-11-06 18:46:47,164 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2019-11-06 18:46:47,168 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2019-11-06 18:46:47,173 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2019-11-06 18:46:47,176 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2019-11-06 18:46:47,179 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2019-11-06 18:46:47,181 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2019-11-06 18:46:47,182 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2019-11-06 18:46:47,183 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2019-11-06 18:46:47,185 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2019-11-06 18:46:47,185 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2019-11-06 18:46:47,186 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2019-11-06 18:46:47,186 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2019-11-06 18:46:47,187 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2019-11-06 18:46:47,187 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2019-11-06 18:46:47,192 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2019-11-06 18:46:47,193 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2019-11-06 18:46:47,193 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2019-11-06 18:46:47,196 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2019-11-06 18:46:47,197 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2019-11-06 18:46:47,197 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2019-11-06 18:46:47,198 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2019-11-06 18:46:47,198 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2019-11-06 18:46:47,201 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2019-11-06 18:46:47,202 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2019-11-06 18:46:47,204 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/default/automizer/svcomp-Reach-32bit-Automizer_Default.epf [2019-11-06 18:46:47,225 INFO L113 SettingsManager]: Loading preferences was successful [2019-11-06 18:46:47,226 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2019-11-06 18:46:47,230 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2019-11-06 18:46:47,230 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2019-11-06 18:46:47,231 INFO L138 SettingsManager]: * Use SBE=true [2019-11-06 18:46:47,231 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2019-11-06 18:46:47,231 INFO L138 SettingsManager]: * sizeof long=4 [2019-11-06 18:46:47,231 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2019-11-06 18:46:47,232 INFO L138 SettingsManager]: * sizeof POINTER=4 [2019-11-06 18:46:47,232 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2019-11-06 18:46:47,233 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2019-11-06 18:46:47,233 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2019-11-06 18:46:47,233 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2019-11-06 18:46:47,234 INFO L138 SettingsManager]: * sizeof long double=12 [2019-11-06 18:46:47,234 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2019-11-06 18:46:47,234 INFO L138 SettingsManager]: * Use constant arrays=true [2019-11-06 18:46:47,235 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2019-11-06 18:46:47,235 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2019-11-06 18:46:47,235 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2019-11-06 18:46:47,235 INFO L138 SettingsManager]: * To the following directory=./dump/ [2019-11-06 18:46:47,236 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2019-11-06 18:46:47,236 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2019-11-06 18:46:47,236 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2019-11-06 18:46:47,236 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2019-11-06 18:46:47,237 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2019-11-06 18:46:47,237 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2019-11-06 18:46:47,237 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2019-11-06 18:46:47,237 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2019-11-06 18:46:47,237 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2019-11-06 18:46:47,532 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2019-11-06 18:46:47,545 INFO L258 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2019-11-06 18:46:47,548 INFO L214 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2019-11-06 18:46:47,550 INFO L271 PluginConnector]: Initializing CDTParser... [2019-11-06 18:46:47,550 INFO L275 PluginConnector]: CDTParser initialized [2019-11-06 18:46:47,551 INFO L428 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/array-examples/standard_sentinel.i.v+cfa-reducer.c [2019-11-06 18:46:47,611 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/bbedd43dd/05556a3f25b4470da81a5c39b86c157c/FLAGbcf0c9150 [2019-11-06 18:46:48,057 INFO L306 CDTParser]: Found 1 translation units. [2019-11-06 18:46:48,060 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/array-examples/standard_sentinel.i.v+cfa-reducer.c [2019-11-06 18:46:48,066 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/bbedd43dd/05556a3f25b4470da81a5c39b86c157c/FLAGbcf0c9150 [2019-11-06 18:46:48,440 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/bbedd43dd/05556a3f25b4470da81a5c39b86c157c [2019-11-06 18:46:48,449 INFO L296 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2019-11-06 18:46:48,451 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2019-11-06 18:46:48,451 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2019-11-06 18:46:48,452 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2019-11-06 18:46:48,455 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2019-11-06 18:46:48,456 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.11 06:46:48" (1/1) ... [2019-11-06 18:46:48,459 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@329037be and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 06:46:48, skipping insertion in model container [2019-11-06 18:46:48,459 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.11 06:46:48" (1/1) ... [2019-11-06 18:46:48,467 INFO L142 MainTranslator]: Starting translation in SV-COMP mode [2019-11-06 18:46:48,485 INFO L173 MainTranslator]: Built tables and reachable declarations [2019-11-06 18:46:48,651 INFO L206 PostProcessor]: Analyzing one entry point: main [2019-11-06 18:46:48,655 INFO L188 MainTranslator]: Completed pre-run [2019-11-06 18:46:48,675 INFO L206 PostProcessor]: Analyzing one entry point: main [2019-11-06 18:46:48,693 INFO L192 MainTranslator]: Completed translation [2019-11-06 18:46:48,693 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 06:46:48 WrapperNode [2019-11-06 18:46:48,693 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2019-11-06 18:46:48,694 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2019-11-06 18:46:48,694 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2019-11-06 18:46:48,694 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2019-11-06 18:46:48,785 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 06:46:48" (1/1) ... [2019-11-06 18:46:48,785 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 06:46:48" (1/1) ... [2019-11-06 18:46:48,793 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 06:46:48" (1/1) ... [2019-11-06 18:46:48,794 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 06:46:48" (1/1) ... [2019-11-06 18:46:48,807 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 06:46:48" (1/1) ... [2019-11-06 18:46:48,813 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 06:46:48" (1/1) ... [2019-11-06 18:46:48,814 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 06:46:48" (1/1) ... [2019-11-06 18:46:48,816 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2019-11-06 18:46:48,817 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2019-11-06 18:46:48,817 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2019-11-06 18:46:48,817 INFO L275 PluginConnector]: RCFGBuilder initialized [2019-11-06 18:46:48,818 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 06:46:48" (1/1) ... No working directory specified, using /storage/repos/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 [2019-11-06 18:46:48,869 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2019-11-06 18:46:48,869 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2019-11-06 18:46:48,869 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2019-11-06 18:46:48,869 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_error [2019-11-06 18:46:48,869 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2019-11-06 18:46:48,869 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2019-11-06 18:46:48,869 INFO L130 BoogieDeclarations]: Found specification of procedure main [2019-11-06 18:46:48,870 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2019-11-06 18:46:48,870 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2019-11-06 18:46:48,870 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2019-11-06 18:46:48,870 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2019-11-06 18:46:48,871 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2019-11-06 18:46:48,871 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2019-11-06 18:46:49,159 INFO L279 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2019-11-06 18:46:49,159 INFO L284 CfgBuilder]: Removed 1 assume(true) statements. [2019-11-06 18:46:49,160 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.11 06:46:49 BoogieIcfgContainer [2019-11-06 18:46:49,160 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2019-11-06 18:46:49,161 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2019-11-06 18:46:49,162 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2019-11-06 18:46:49,164 INFO L275 PluginConnector]: TraceAbstraction initialized [2019-11-06 18:46:49,164 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 06.11 06:46:48" (1/3) ... [2019-11-06 18:46:49,165 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3c07cf47 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.11 06:46:49, skipping insertion in model container [2019-11-06 18:46:49,165 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 06:46:48" (2/3) ... [2019-11-06 18:46:49,166 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3c07cf47 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.11 06:46:49, skipping insertion in model container [2019-11-06 18:46:49,166 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.11 06:46:49" (3/3) ... [2019-11-06 18:46:49,168 INFO L109 eAbstractionObserver]: Analyzing ICFG standard_sentinel.i.v+cfa-reducer.c [2019-11-06 18:46:49,177 INFO L152 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2019-11-06 18:46:49,184 INFO L164 ceAbstractionStarter]: Appying trace abstraction to program that has 1 error locations. [2019-11-06 18:46:49,196 INFO L249 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2019-11-06 18:46:49,225 INFO L373 AbstractCegarLoop]: Interprodecural is true [2019-11-06 18:46:49,226 INFO L374 AbstractCegarLoop]: Hoare is true [2019-11-06 18:46:49,226 INFO L375 AbstractCegarLoop]: Compute interpolants for FPandBP [2019-11-06 18:46:49,226 INFO L376 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2019-11-06 18:46:49,226 INFO L377 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2019-11-06 18:46:49,226 INFO L378 AbstractCegarLoop]: Difference is false [2019-11-06 18:46:49,226 INFO L379 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2019-11-06 18:46:49,227 INFO L383 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2019-11-06 18:46:49,245 INFO L276 IsEmpty]: Start isEmpty. Operand 19 states. [2019-11-06 18:46:49,249 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2019-11-06 18:46:49,250 INFO L402 BasicCegarLoop]: Found error trace [2019-11-06 18:46:49,250 INFO L410 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-06 18:46:49,252 INFO L410 AbstractCegarLoop]: === Iteration 1 === [mainErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-06 18:46:49,257 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-06 18:46:49,258 INFO L82 PathProgramCache]: Analyzing trace with hash 1429065311, now seen corresponding path program 1 times [2019-11-06 18:46:49,264 INFO L161 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-06 18:46:49,265 INFO L337 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [640891444] [2019-11-06 18:46:49,265 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-06 18:46:49,350 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:46:49,438 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:46:49,447 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-11-06 18:46:49,447 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [640891444] [2019-11-06 18:46:49,448 INFO L218 FreeRefinementEngine]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2019-11-06 18:46:49,449 INFO L231 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2019-11-06 18:46:49,449 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1554814535] [2019-11-06 18:46:49,454 INFO L442 AbstractCegarLoop]: Interpolant automaton has 3 states [2019-11-06 18:46:49,455 INFO L141 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-06 18:46:49,470 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2019-11-06 18:46:49,471 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2019-11-06 18:46:49,473 INFO L87 Difference]: Start difference. First operand 19 states. Second operand 3 states. [2019-11-06 18:46:49,559 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-06 18:46:49,559 INFO L93 Difference]: Finished difference Result 30 states and 38 transitions. [2019-11-06 18:46:49,560 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2019-11-06 18:46:49,562 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 13 [2019-11-06 18:46:49,562 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-06 18:46:49,572 INFO L225 Difference]: With dead ends: 30 [2019-11-06 18:46:49,572 INFO L226 Difference]: Without dead ends: 15 [2019-11-06 18:46:49,581 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2019-11-06 18:46:49,607 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 15 states. [2019-11-06 18:46:49,632 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 15 to 15. [2019-11-06 18:46:49,634 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 15 states. [2019-11-06 18:46:49,636 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2019-11-06 18:46:49,639 INFO L78 Accepts]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2019-11-06 18:46:49,639 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-06 18:46:49,639 INFO L462 AbstractCegarLoop]: Abstraction has 15 states and 16 transitions. [2019-11-06 18:46:49,640 INFO L463 AbstractCegarLoop]: Interpolant automaton has 3 states. [2019-11-06 18:46:49,641 INFO L276 IsEmpty]: Start isEmpty. Operand 15 states and 16 transitions. [2019-11-06 18:46:49,642 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2019-11-06 18:46:49,642 INFO L402 BasicCegarLoop]: Found error trace [2019-11-06 18:46:49,642 INFO L410 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-06 18:46:49,644 INFO L410 AbstractCegarLoop]: === Iteration 2 === [mainErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-06 18:46:49,645 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-06 18:46:49,645 INFO L82 PathProgramCache]: Analyzing trace with hash 399010521, now seen corresponding path program 1 times [2019-11-06 18:46:49,645 INFO L161 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-06 18:46:49,647 INFO L337 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [541018629] [2019-11-06 18:46:49,647 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-06 18:46:49,706 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:46:49,782 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:46:49,795 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-11-06 18:46:49,795 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [541018629] [2019-11-06 18:46:49,799 INFO L218 FreeRefinementEngine]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2019-11-06 18:46:49,799 INFO L231 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2019-11-06 18:46:49,799 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2038682612] [2019-11-06 18:46:49,801 INFO L442 AbstractCegarLoop]: Interpolant automaton has 4 states [2019-11-06 18:46:49,801 INFO L141 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-06 18:46:49,802 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2019-11-06 18:46:49,803 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2019-11-06 18:46:49,803 INFO L87 Difference]: Start difference. First operand 15 states and 16 transitions. Second operand 4 states. [2019-11-06 18:46:49,854 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-06 18:46:49,854 INFO L93 Difference]: Finished difference Result 24 states and 26 transitions. [2019-11-06 18:46:49,855 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2019-11-06 18:46:49,855 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 13 [2019-11-06 18:46:49,856 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-06 18:46:49,856 INFO L225 Difference]: With dead ends: 24 [2019-11-06 18:46:49,856 INFO L226 Difference]: Without dead ends: 17 [2019-11-06 18:46:49,858 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2019-11-06 18:46:49,858 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 17 states. [2019-11-06 18:46:49,864 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 17 to 16. [2019-11-06 18:46:49,865 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 16 states. [2019-11-06 18:46:49,866 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 16 states to 16 states and 17 transitions. [2019-11-06 18:46:49,867 INFO L78 Accepts]: Start accepts. Automaton has 16 states and 17 transitions. Word has length 13 [2019-11-06 18:46:49,867 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-06 18:46:49,867 INFO L462 AbstractCegarLoop]: Abstraction has 16 states and 17 transitions. [2019-11-06 18:46:49,867 INFO L463 AbstractCegarLoop]: Interpolant automaton has 4 states. [2019-11-06 18:46:49,868 INFO L276 IsEmpty]: Start isEmpty. Operand 16 states and 17 transitions. [2019-11-06 18:46:49,868 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2019-11-06 18:46:49,868 INFO L402 BasicCegarLoop]: Found error trace [2019-11-06 18:46:49,869 INFO L410 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-06 18:46:49,869 INFO L410 AbstractCegarLoop]: === Iteration 3 === [mainErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-06 18:46:49,869 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-06 18:46:49,870 INFO L82 PathProgramCache]: Analyzing trace with hash 1207654839, now seen corresponding path program 1 times [2019-11-06 18:46:49,871 INFO L161 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-06 18:46:49,871 INFO L337 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [86446221] [2019-11-06 18:46:49,871 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-06 18:46:49,915 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:46:50,021 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:46:50,027 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2019-11-06 18:46:50,027 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [86446221] [2019-11-06 18:46:50,028 INFO L218 FreeRefinementEngine]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2019-11-06 18:46:50,028 INFO L231 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2019-11-06 18:46:50,028 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [717766423] [2019-11-06 18:46:50,029 INFO L442 AbstractCegarLoop]: Interpolant automaton has 6 states [2019-11-06 18:46:50,029 INFO L141 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-06 18:46:50,029 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2019-11-06 18:46:50,030 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2019-11-06 18:46:50,030 INFO L87 Difference]: Start difference. First operand 16 states and 17 transitions. Second operand 6 states. [2019-11-06 18:46:50,092 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-06 18:46:50,092 INFO L93 Difference]: Finished difference Result 21 states and 22 transitions. [2019-11-06 18:46:50,093 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2019-11-06 18:46:50,093 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 15 [2019-11-06 18:46:50,093 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-06 18:46:50,094 INFO L225 Difference]: With dead ends: 21 [2019-11-06 18:46:50,094 INFO L226 Difference]: Without dead ends: 18 [2019-11-06 18:46:50,095 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2019-11-06 18:46:50,095 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 18 states. [2019-11-06 18:46:50,099 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 18 to 18. [2019-11-06 18:46:50,099 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 18 states. [2019-11-06 18:46:50,100 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 18 states to 18 states and 19 transitions. [2019-11-06 18:46:50,100 INFO L78 Accepts]: Start accepts. Automaton has 18 states and 19 transitions. Word has length 15 [2019-11-06 18:46:50,100 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-06 18:46:50,100 INFO L462 AbstractCegarLoop]: Abstraction has 18 states and 19 transitions. [2019-11-06 18:46:50,100 INFO L463 AbstractCegarLoop]: Interpolant automaton has 6 states. [2019-11-06 18:46:50,101 INFO L276 IsEmpty]: Start isEmpty. Operand 18 states and 19 transitions. [2019-11-06 18:46:50,101 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2019-11-06 18:46:50,101 INFO L402 BasicCegarLoop]: Found error trace [2019-11-06 18:46:50,102 INFO L410 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-06 18:46:50,102 INFO L410 AbstractCegarLoop]: === Iteration 4 === [mainErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-06 18:46:50,102 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-06 18:46:50,102 INFO L82 PathProgramCache]: Analyzing trace with hash 913042234, now seen corresponding path program 1 times [2019-11-06 18:46:50,103 INFO L161 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-06 18:46:50,103 INFO L337 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2122799067] [2019-11-06 18:46:50,103 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-06 18:46:50,118 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:46:50,159 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:46:50,163 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2019-11-06 18:46:50,163 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2122799067] [2019-11-06 18:46:50,164 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [346209440] [2019-11-06 18:46:50,164 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:46:50,231 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:46:50,233 INFO L256 TraceCheckSpWp]: Trace formula consists of 89 conjuncts, 3 conjunts are in the unsatisfiable core [2019-11-06 18:46:50,239 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2019-11-06 18:46:50,274 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2019-11-06 18:46:50,275 INFO L218 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-06 18:46:50,275 INFO L231 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 4] total 6 [2019-11-06 18:46:50,276 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [903875668] [2019-11-06 18:46:50,276 INFO L442 AbstractCegarLoop]: Interpolant automaton has 6 states [2019-11-06 18:46:50,277 INFO L141 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-06 18:46:50,277 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2019-11-06 18:46:50,277 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2019-11-06 18:46:50,278 INFO L87 Difference]: Start difference. First operand 18 states and 19 transitions. Second operand 6 states. [2019-11-06 18:46:50,334 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-06 18:46:50,334 INFO L93 Difference]: Finished difference Result 30 states and 32 transitions. [2019-11-06 18:46:50,335 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2019-11-06 18:46:50,335 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 17 [2019-11-06 18:46:50,335 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-06 18:46:50,336 INFO L225 Difference]: With dead ends: 30 [2019-11-06 18:46:50,336 INFO L226 Difference]: Without dead ends: 21 [2019-11-06 18:46:50,336 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 22 GetRequests, 18 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2019-11-06 18:46:50,337 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 21 states. [2019-11-06 18:46:50,340 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 21 to 20. [2019-11-06 18:46:50,340 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 20 states. [2019-11-06 18:46:50,341 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 21 transitions. [2019-11-06 18:46:50,342 INFO L78 Accepts]: Start accepts. Automaton has 20 states and 21 transitions. Word has length 17 [2019-11-06 18:46:50,342 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-06 18:46:50,342 INFO L462 AbstractCegarLoop]: Abstraction has 20 states and 21 transitions. [2019-11-06 18:46:50,342 INFO L463 AbstractCegarLoop]: Interpolant automaton has 6 states. [2019-11-06 18:46:50,342 INFO L276 IsEmpty]: Start isEmpty. Operand 20 states and 21 transitions. [2019-11-06 18:46:50,343 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2019-11-06 18:46:50,343 INFO L402 BasicCegarLoop]: Found error trace [2019-11-06 18:46:50,343 INFO L410 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-06 18:46:50,552 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:46:50,553 INFO L410 AbstractCegarLoop]: === Iteration 5 === [mainErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-06 18:46:50,553 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-06 18:46:50,554 INFO L82 PathProgramCache]: Analyzing trace with hash 598752024, now seen corresponding path program 2 times [2019-11-06 18:46:50,554 INFO L161 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-06 18:46:50,555 INFO L337 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [389627332] [2019-11-06 18:46:50,555 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-06 18:46:50,583 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:46:50,647 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:46:50,651 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2019-11-06 18:46:50,652 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [389627332] [2019-11-06 18:46:50,652 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1280958537] [2019-11-06 18:46:50,652 INFO L92 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:46:50,704 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2019-11-06 18:46:50,705 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-06 18:46:50,705 INFO L256 TraceCheckSpWp]: Trace formula consists of 95 conjuncts, 4 conjunts are in the unsatisfiable core [2019-11-06 18:46:50,708 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2019-11-06 18:46:50,724 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2019-11-06 18:46:50,725 INFO L218 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-06 18:46:50,725 INFO L231 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 5] total 7 [2019-11-06 18:46:50,725 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1347701540] [2019-11-06 18:46:50,726 INFO L442 AbstractCegarLoop]: Interpolant automaton has 7 states [2019-11-06 18:46:50,726 INFO L141 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-06 18:46:50,726 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2019-11-06 18:46:50,726 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=25, Unknown=0, NotChecked=0, Total=42 [2019-11-06 18:46:50,727 INFO L87 Difference]: Start difference. First operand 20 states and 21 transitions. Second operand 7 states. [2019-11-06 18:46:50,786 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-06 18:46:50,787 INFO L93 Difference]: Finished difference Result 32 states and 34 transitions. [2019-11-06 18:46:50,787 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2019-11-06 18:46:50,788 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 19 [2019-11-06 18:46:50,788 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-06 18:46:50,789 INFO L225 Difference]: With dead ends: 32 [2019-11-06 18:46:50,789 INFO L226 Difference]: Without dead ends: 23 [2019-11-06 18:46:50,789 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 25 GetRequests, 20 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=25, Unknown=0, NotChecked=0, Total=42 [2019-11-06 18:46:50,790 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states. [2019-11-06 18:46:50,795 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 22. [2019-11-06 18:46:50,795 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 22 states. [2019-11-06 18:46:50,799 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 22 states to 22 states and 23 transitions. [2019-11-06 18:46:50,799 INFO L78 Accepts]: Start accepts. Automaton has 22 states and 23 transitions. Word has length 19 [2019-11-06 18:46:50,799 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-06 18:46:50,800 INFO L462 AbstractCegarLoop]: Abstraction has 22 states and 23 transitions. [2019-11-06 18:46:50,800 INFO L463 AbstractCegarLoop]: Interpolant automaton has 7 states. [2019-11-06 18:46:50,800 INFO L276 IsEmpty]: Start isEmpty. Operand 22 states and 23 transitions. [2019-11-06 18:46:50,800 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2019-11-06 18:46:50,801 INFO L402 BasicCegarLoop]: Found error trace [2019-11-06 18:46:50,802 INFO L410 BasicCegarLoop]: trace histogram [3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-06 18:46:51,006 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:46:51,006 INFO L410 AbstractCegarLoop]: === Iteration 6 === [mainErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-06 18:46:51,007 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-06 18:46:51,007 INFO L82 PathProgramCache]: Analyzing trace with hash -786429066, now seen corresponding path program 3 times [2019-11-06 18:46:51,008 INFO L161 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-06 18:46:51,008 INFO L337 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [46560488] [2019-11-06 18:46:51,009 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-06 18:46:51,032 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:46:51,096 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:46:51,099 INFO L134 CoverageAnalysis]: Checked inductivity of 11 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2019-11-06 18:46:51,106 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [46560488] [2019-11-06 18:46:51,106 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [284147728] [2019-11-06 18:46:51,106 INFO L92 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:46:51,168 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2019-11-06 18:46:51,172 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-06 18:46:51,174 INFO L256 TraceCheckSpWp]: Trace formula consists of 89 conjuncts, 13 conjunts are in the unsatisfiable core [2019-11-06 18:46:51,178 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2019-11-06 18:46:51,230 INFO L375 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2019-11-06 18:46:51,230 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-06 18:46:51,238 INFO L567 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-06 18:46:51,239 INFO L496 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2019-11-06 18:46:51,239 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:22, output treesize:18 [2019-11-06 18:46:51,276 INFO L341 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2019-11-06 18:46:51,277 INFO L375 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 23 treesize of output 23 [2019-11-06 18:46:51,278 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 2 xjuncts. [2019-11-06 18:46:51,290 INFO L567 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-06 18:46:51,291 INFO L496 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2019-11-06 18:46:51,292 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 3 variables, input treesize:29, output treesize:23 [2019-11-06 18:46:51,326 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:51,369 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:51,387 INFO L134 CoverageAnalysis]: Checked inductivity of 11 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2019-11-06 18:46:51,390 INFO L218 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-06 18:46:51,390 INFO L231 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 12 [2019-11-06 18:46:51,391 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [941618651] [2019-11-06 18:46:51,391 INFO L442 AbstractCegarLoop]: Interpolant automaton has 12 states [2019-11-06 18:46:51,391 INFO L141 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-06 18:46:51,392 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2019-11-06 18:46:51,392 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=32, Invalid=100, Unknown=0, NotChecked=0, Total=132 [2019-11-06 18:46:51,392 INFO L87 Difference]: Start difference. First operand 22 states and 23 transitions. Second operand 12 states. [2019-11-06 18:46:51,534 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-06 18:46:51,535 INFO L93 Difference]: Finished difference Result 37 states and 40 transitions. [2019-11-06 18:46:51,535 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2019-11-06 18:46:51,535 INFO L78 Accepts]: Start accepts. Automaton has 12 states. Word has length 21 [2019-11-06 18:46:51,536 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-06 18:46:51,536 INFO L225 Difference]: With dead ends: 37 [2019-11-06 18:46:51,536 INFO L226 Difference]: Without dead ends: 27 [2019-11-06 18:46:51,537 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 30 GetRequests, 18 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 23 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=43, Invalid=139, Unknown=0, NotChecked=0, Total=182 [2019-11-06 18:46:51,537 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2019-11-06 18:46:51,543 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 26. [2019-11-06 18:46:51,543 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 26 states. [2019-11-06 18:46:51,544 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 27 transitions. [2019-11-06 18:46:51,545 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 27 transitions. Word has length 21 [2019-11-06 18:46:51,546 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-06 18:46:51,546 INFO L462 AbstractCegarLoop]: Abstraction has 26 states and 27 transitions. [2019-11-06 18:46:51,546 INFO L463 AbstractCegarLoop]: Interpolant automaton has 12 states. [2019-11-06 18:46:51,546 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 27 transitions. [2019-11-06 18:46:51,548 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2019-11-06 18:46:51,548 INFO L402 BasicCegarLoop]: Found error trace [2019-11-06 18:46:51,549 INFO L410 BasicCegarLoop]: trace histogram [4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-06 18:46:51,750 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 4 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:46:51,750 INFO L410 AbstractCegarLoop]: === Iteration 7 === [mainErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-06 18:46:51,750 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-06 18:46:51,750 INFO L82 PathProgramCache]: Analyzing trace with hash -547382633, now seen corresponding path program 4 times [2019-11-06 18:46:51,751 INFO L161 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-06 18:46:51,751 INFO L337 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [950516590] [2019-11-06 18:46:51,751 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-06 18:46:51,772 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:46:51,856 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:46:51,860 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 0 proven. 16 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2019-11-06 18:46:51,861 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [950516590] [2019-11-06 18:46:51,861 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [553366688] [2019-11-06 18:46:51,861 INFO L92 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:46:51,919 INFO L249 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2019-11-06 18:46:51,919 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-06 18:46:51,921 INFO L256 TraceCheckSpWp]: Trace formula consists of 112 conjuncts, 6 conjunts are in the unsatisfiable core [2019-11-06 18:46:51,922 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2019-11-06 18:46:51,941 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 0 proven. 16 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2019-11-06 18:46:51,941 INFO L218 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-06 18:46:51,942 INFO L231 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 7] total 9 [2019-11-06 18:46:51,942 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [709220218] [2019-11-06 18:46:51,943 INFO L442 AbstractCegarLoop]: Interpolant automaton has 9 states [2019-11-06 18:46:51,943 INFO L141 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-06 18:46:51,943 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2019-11-06 18:46:51,943 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=42, Unknown=0, NotChecked=0, Total=72 [2019-11-06 18:46:51,944 INFO L87 Difference]: Start difference. First operand 26 states and 27 transitions. Second operand 9 states. [2019-11-06 18:46:52,006 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-06 18:46:52,006 INFO L93 Difference]: Finished difference Result 40 states and 42 transitions. [2019-11-06 18:46:52,007 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2019-11-06 18:46:52,007 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 25 [2019-11-06 18:46:52,007 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-06 18:46:52,008 INFO L225 Difference]: With dead ends: 40 [2019-11-06 18:46:52,008 INFO L226 Difference]: Without dead ends: 29 [2019-11-06 18:46:52,009 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 33 GetRequests, 26 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=30, Invalid=42, Unknown=0, NotChecked=0, Total=72 [2019-11-06 18:46:52,011 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 29 states. [2019-11-06 18:46:52,025 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 29 to 28. [2019-11-06 18:46:52,026 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 28 states. [2019-11-06 18:46:52,026 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28 states to 28 states and 29 transitions. [2019-11-06 18:46:52,027 INFO L78 Accepts]: Start accepts. Automaton has 28 states and 29 transitions. Word has length 25 [2019-11-06 18:46:52,028 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-06 18:46:52,028 INFO L462 AbstractCegarLoop]: Abstraction has 28 states and 29 transitions. [2019-11-06 18:46:52,028 INFO L463 AbstractCegarLoop]: Interpolant automaton has 9 states. [2019-11-06 18:46:52,029 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 29 transitions. [2019-11-06 18:46:52,030 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2019-11-06 18:46:52,030 INFO L402 BasicCegarLoop]: Found error trace [2019-11-06 18:46:52,030 INFO L410 BasicCegarLoop]: trace histogram [5, 5, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-06 18:46:52,233 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:46:52,234 INFO L410 AbstractCegarLoop]: === Iteration 8 === [mainErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-06 18:46:52,234 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-06 18:46:52,235 INFO L82 PathProgramCache]: Analyzing trace with hash -96654219, now seen corresponding path program 5 times [2019-11-06 18:46:52,235 INFO L161 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-06 18:46:52,235 INFO L337 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1548444899] [2019-11-06 18:46:52,236 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-06 18:46:52,255 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:46:52,358 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:46:52,361 INFO L134 CoverageAnalysis]: Checked inductivity of 31 backedges. 0 proven. 25 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2019-11-06 18:46:52,361 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1548444899] [2019-11-06 18:46:52,361 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [912724099] [2019-11-06 18:46:52,362 INFO L92 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:46:52,417 INFO L249 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2019-11-06 18:46:52,418 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-06 18:46:52,419 INFO L256 TraceCheckSpWp]: Trace formula consists of 118 conjuncts, 7 conjunts are in the unsatisfiable core [2019-11-06 18:46:52,424 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2019-11-06 18:46:52,446 INFO L134 CoverageAnalysis]: Checked inductivity of 31 backedges. 0 proven. 25 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2019-11-06 18:46:52,446 INFO L218 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-06 18:46:52,447 INFO L231 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8] total 10 [2019-11-06 18:46:52,447 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [620690794] [2019-11-06 18:46:52,447 INFO L442 AbstractCegarLoop]: Interpolant automaton has 10 states [2019-11-06 18:46:52,447 INFO L141 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-06 18:46:52,448 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2019-11-06 18:46:52,448 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=38, Invalid=52, Unknown=0, NotChecked=0, Total=90 [2019-11-06 18:46:52,448 INFO L87 Difference]: Start difference. First operand 28 states and 29 transitions. Second operand 10 states. [2019-11-06 18:46:52,507 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-06 18:46:52,507 INFO L93 Difference]: Finished difference Result 42 states and 44 transitions. [2019-11-06 18:46:52,509 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2019-11-06 18:46:52,509 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 27 [2019-11-06 18:46:52,509 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-06 18:46:52,510 INFO L225 Difference]: With dead ends: 42 [2019-11-06 18:46:52,510 INFO L226 Difference]: Without dead ends: 31 [2019-11-06 18:46:52,510 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 36 GetRequests, 28 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=38, Invalid=52, Unknown=0, NotChecked=0, Total=90 [2019-11-06 18:46:52,511 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2019-11-06 18:46:52,517 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 30. [2019-11-06 18:46:52,518 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 30 states. [2019-11-06 18:46:52,518 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 31 transitions. [2019-11-06 18:46:52,519 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 31 transitions. Word has length 27 [2019-11-06 18:46:52,519 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-06 18:46:52,520 INFO L462 AbstractCegarLoop]: Abstraction has 30 states and 31 transitions. [2019-11-06 18:46:52,520 INFO L463 AbstractCegarLoop]: Interpolant automaton has 10 states. [2019-11-06 18:46:52,520 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 31 transitions. [2019-11-06 18:46:52,520 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2019-11-06 18:46:52,520 INFO L402 BasicCegarLoop]: Found error trace [2019-11-06 18:46:52,520 INFO L410 BasicCegarLoop]: trace histogram [6, 6, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-06 18:46:52,721 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:46:52,722 INFO L410 AbstractCegarLoop]: === Iteration 9 === [mainErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-06 18:46:52,722 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-06 18:46:52,722 INFO L82 PathProgramCache]: Analyzing trace with hash -738345261, now seen corresponding path program 6 times [2019-11-06 18:46:52,723 INFO L161 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-06 18:46:52,723 INFO L337 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [926662832] [2019-11-06 18:46:52,724 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-06 18:46:52,740 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:46:52,820 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:46:52,824 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 0 proven. 36 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2019-11-06 18:46:52,824 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [926662832] [2019-11-06 18:46:52,824 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1501117623] [2019-11-06 18:46:52,824 INFO L92 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:46:52,894 INFO L249 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 5 check-sat command(s) [2019-11-06 18:46:52,894 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-06 18:46:52,895 INFO L256 TraceCheckSpWp]: Trace formula consists of 112 conjuncts, 18 conjunts are in the unsatisfiable core [2019-11-06 18:46:52,898 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2019-11-06 18:46:52,933 INFO L375 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2019-11-06 18:46:52,933 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-06 18:46:52,943 INFO L567 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-06 18:46:52,943 INFO L496 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2019-11-06 18:46:52,943 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:22, output treesize:18 [2019-11-06 18:46:53,058 INFO L341 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2019-11-06 18:46:53,058 INFO L375 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 35 treesize of output 59 [2019-11-06 18:46:53,060 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:53,060 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:53,062 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-06 18:46:53,081 INFO L567 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-06 18:46:53,082 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:53,090 INFO L496 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: 6 dim-0 vars, and 1 xjuncts. [2019-11-06 18:46:53,091 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 4 variables, input treesize:46, output treesize:237 [2019-11-06 18:46:53,195 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:53,220 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:53,237 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2019-11-06 18:46:53,237 INFO L218 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-06 18:46:53,237 INFO L231 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 9] total 17 [2019-11-06 18:46:53,238 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1828065037] [2019-11-06 18:46:53,238 INFO L442 AbstractCegarLoop]: Interpolant automaton has 17 states [2019-11-06 18:46:53,238 INFO L141 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-06 18:46:53,238 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2019-11-06 18:46:53,239 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=63, Invalid=209, Unknown=0, NotChecked=0, Total=272 [2019-11-06 18:46:53,239 INFO L87 Difference]: Start difference. First operand 30 states and 31 transitions. Second operand 17 states. [2019-11-06 18:46:53,448 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-06 18:46:53,449 INFO L93 Difference]: Finished difference Result 47 states and 50 transitions. [2019-11-06 18:46:53,449 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2019-11-06 18:46:53,449 INFO L78 Accepts]: Start accepts. Automaton has 17 states. Word has length 29 [2019-11-06 18:46:53,449 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-06 18:46:53,450 INFO L225 Difference]: With dead ends: 47 [2019-11-06 18:46:53,450 INFO L226 Difference]: Without dead ends: 35 [2019-11-06 18:46:53,454 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 41 GetRequests, 24 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 62 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=74, Invalid=268, Unknown=0, NotChecked=0, Total=342 [2019-11-06 18:46:53,455 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35 states. [2019-11-06 18:46:53,460 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35 to 34. [2019-11-06 18:46:53,460 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 34 states. [2019-11-06 18:46:53,461 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 35 transitions. [2019-11-06 18:46:53,461 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 35 transitions. Word has length 29 [2019-11-06 18:46:53,461 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-06 18:46:53,461 INFO L462 AbstractCegarLoop]: Abstraction has 34 states and 35 transitions. [2019-11-06 18:46:53,461 INFO L463 AbstractCegarLoop]: Interpolant automaton has 17 states. [2019-11-06 18:46:53,462 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 35 transitions. [2019-11-06 18:46:53,462 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2019-11-06 18:46:53,462 INFO L402 BasicCegarLoop]: Found error trace [2019-11-06 18:46:53,463 INFO L410 BasicCegarLoop]: trace histogram [7, 7, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-06 18:46:53,666 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:46:53,666 INFO L410 AbstractCegarLoop]: === Iteration 10 === [mainErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-06 18:46:53,667 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-06 18:46:53,667 INFO L82 PathProgramCache]: Analyzing trace with hash -742544204, now seen corresponding path program 7 times [2019-11-06 18:46:53,667 INFO L161 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-06 18:46:53,667 INFO L337 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [607208067] [2019-11-06 18:46:53,667 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-06 18:46:53,683 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:46:53,768 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:46:53,773 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 0 proven. 49 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2019-11-06 18:46:53,774 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [607208067] [2019-11-06 18:46:53,774 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [199731106] [2019-11-06 18:46:53,774 INFO L92 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:46:53,831 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:46:53,832 INFO L256 TraceCheckSpWp]: Trace formula consists of 135 conjuncts, 9 conjunts are in the unsatisfiable core [2019-11-06 18:46:53,835 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2019-11-06 18:46:53,850 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 0 proven. 49 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2019-11-06 18:46:53,851 INFO L218 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-06 18:46:53,851 INFO L231 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 10] total 12 [2019-11-06 18:46:53,851 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [333347645] [2019-11-06 18:46:53,855 INFO L442 AbstractCegarLoop]: Interpolant automaton has 12 states [2019-11-06 18:46:53,855 INFO L141 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-06 18:46:53,855 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2019-11-06 18:46:53,856 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=57, Invalid=75, Unknown=0, NotChecked=0, Total=132 [2019-11-06 18:46:53,856 INFO L87 Difference]: Start difference. First operand 34 states and 35 transitions. Second operand 12 states. [2019-11-06 18:46:53,919 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-06 18:46:53,919 INFO L93 Difference]: Finished difference Result 50 states and 52 transitions. [2019-11-06 18:46:53,919 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2019-11-06 18:46:53,919 INFO L78 Accepts]: Start accepts. Automaton has 12 states. Word has length 33 [2019-11-06 18:46:53,920 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-06 18:46:53,920 INFO L225 Difference]: With dead ends: 50 [2019-11-06 18:46:53,920 INFO L226 Difference]: Without dead ends: 37 [2019-11-06 18:46:53,921 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 44 GetRequests, 34 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 19 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=57, Invalid=75, Unknown=0, NotChecked=0, Total=132 [2019-11-06 18:46:53,921 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2019-11-06 18:46:53,929 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 36. [2019-11-06 18:46:53,929 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 36 states. [2019-11-06 18:46:53,930 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 37 transitions. [2019-11-06 18:46:53,930 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 37 transitions. Word has length 33 [2019-11-06 18:46:53,931 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-06 18:46:53,932 INFO L462 AbstractCegarLoop]: Abstraction has 36 states and 37 transitions. [2019-11-06 18:46:53,932 INFO L463 AbstractCegarLoop]: Interpolant automaton has 12 states. [2019-11-06 18:46:53,932 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 37 transitions. [2019-11-06 18:46:53,933 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2019-11-06 18:46:53,933 INFO L402 BasicCegarLoop]: Found error trace [2019-11-06 18:46:53,933 INFO L410 BasicCegarLoop]: trace histogram [8, 8, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-06 18:46:54,134 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:46:54,134 INFO L410 AbstractCegarLoop]: === Iteration 11 === [mainErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-06 18:46:54,135 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-06 18:46:54,135 INFO L82 PathProgramCache]: Analyzing trace with hash 399671442, now seen corresponding path program 8 times [2019-11-06 18:46:54,135 INFO L161 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-06 18:46:54,136 INFO L337 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [87140973] [2019-11-06 18:46:54,136 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-06 18:46:54,162 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:46:54,271 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:46:54,276 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 0 proven. 64 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2019-11-06 18:46:54,276 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [87140973] [2019-11-06 18:46:54,276 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [309059812] [2019-11-06 18:46:54,277 INFO L92 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:46:54,329 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2019-11-06 18:46:54,330 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-06 18:46:54,331 INFO L256 TraceCheckSpWp]: Trace formula consists of 141 conjuncts, 10 conjunts are in the unsatisfiable core [2019-11-06 18:46:54,341 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2019-11-06 18:46:54,358 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 0 proven. 64 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2019-11-06 18:46:54,358 INFO L218 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-06 18:46:54,358 INFO L231 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11] total 13 [2019-11-06 18:46:54,359 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2026899414] [2019-11-06 18:46:54,359 INFO L442 AbstractCegarLoop]: Interpolant automaton has 13 states [2019-11-06 18:46:54,359 INFO L141 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-06 18:46:54,360 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2019-11-06 18:46:54,360 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=68, Invalid=88, Unknown=0, NotChecked=0, Total=156 [2019-11-06 18:46:54,360 INFO L87 Difference]: Start difference. First operand 36 states and 37 transitions. Second operand 13 states. [2019-11-06 18:46:54,427 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-06 18:46:54,427 INFO L93 Difference]: Finished difference Result 52 states and 54 transitions. [2019-11-06 18:46:54,427 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2019-11-06 18:46:54,427 INFO L78 Accepts]: Start accepts. Automaton has 13 states. Word has length 35 [2019-11-06 18:46:54,428 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-06 18:46:54,428 INFO L225 Difference]: With dead ends: 52 [2019-11-06 18:46:54,428 INFO L226 Difference]: Without dead ends: 39 [2019-11-06 18:46:54,429 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 47 GetRequests, 36 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 22 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=68, Invalid=88, Unknown=0, NotChecked=0, Total=156 [2019-11-06 18:46:54,429 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2019-11-06 18:46:54,437 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 38. [2019-11-06 18:46:54,437 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 38 states. [2019-11-06 18:46:54,440 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 38 states to 38 states and 39 transitions. [2019-11-06 18:46:54,440 INFO L78 Accepts]: Start accepts. Automaton has 38 states and 39 transitions. Word has length 35 [2019-11-06 18:46:54,440 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-06 18:46:54,440 INFO L462 AbstractCegarLoop]: Abstraction has 38 states and 39 transitions. [2019-11-06 18:46:54,440 INFO L463 AbstractCegarLoop]: Interpolant automaton has 13 states. [2019-11-06 18:46:54,440 INFO L276 IsEmpty]: Start isEmpty. Operand 38 states and 39 transitions. [2019-11-06 18:46:54,441 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2019-11-06 18:46:54,441 INFO L402 BasicCegarLoop]: Found error trace [2019-11-06 18:46:54,441 INFO L410 BasicCegarLoop]: trace histogram [9, 9, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-06 18:46:54,642 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:46:54,643 INFO L410 AbstractCegarLoop]: === Iteration 12 === [mainErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-06 18:46:54,643 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-06 18:46:54,643 INFO L82 PathProgramCache]: Analyzing trace with hash -1442720528, now seen corresponding path program 9 times [2019-11-06 18:46:54,644 INFO L161 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-06 18:46:54,644 INFO L337 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1910530762] [2019-11-06 18:46:54,644 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-06 18:46:54,660 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:46:54,770 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:46:54,772 INFO L134 CoverageAnalysis]: Checked inductivity of 93 backedges. 0 proven. 81 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2019-11-06 18:46:54,773 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1910530762] [2019-11-06 18:46:54,773 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1533248499] [2019-11-06 18:46:54,773 INFO L92 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:46:54,836 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2019-11-06 18:46:54,837 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-06 18:46:54,838 INFO L256 TraceCheckSpWp]: Trace formula consists of 111 conjuncts, 26 conjunts are in the unsatisfiable core [2019-11-06 18:46:54,848 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2019-11-06 18:46:54,870 INFO L375 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2019-11-06 18:46:54,871 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-06 18:46:54,876 INFO L567 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-06 18:46:54,877 INFO L496 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2019-11-06 18:46:54,877 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:22, output treesize:18 [2019-11-06 18:46:55,068 INFO L341 Elim1Store]: treesize reduction 10, result has 87.3 percent of original size [2019-11-06 18:46:55,069 INFO L375 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 41 treesize of output 83 [2019-11-06 18:46:55,070 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:55,072 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:55,073 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:55,074 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:55,075 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-06 18:46:55,162 INFO L567 ElimStorePlain]: treesize reduction 8, result has 91.9 percent of original size [2019-11-06 18:46:55,163 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:55,163 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:55,164 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:55,165 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:55,166 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:55,166 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:55,168 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:55,169 INFO L496 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2019-11-06 18:46:55,169 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 3 variables, input treesize:47, output treesize:91 [2019-11-06 18:46:55,170 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:55,170 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:55,170 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:55,171 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:55,172 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:55,172 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:55,172 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:55,232 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:55,233 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:55,233 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:55,295 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:55,331 INFO L134 CoverageAnalysis]: Checked inductivity of 93 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 81 trivial. 0 not checked. [2019-11-06 18:46:55,331 INFO L218 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-06 18:46:55,331 INFO L231 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 11] total 22 [2019-11-06 18:46:55,331 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1964247062] [2019-11-06 18:46:55,332 INFO L442 AbstractCegarLoop]: Interpolant automaton has 22 states [2019-11-06 18:46:55,332 INFO L141 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-06 18:46:55,332 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2019-11-06 18:46:55,333 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=97, Invalid=365, Unknown=0, NotChecked=0, Total=462 [2019-11-06 18:46:55,333 INFO L87 Difference]: Start difference. First operand 38 states and 39 transitions. Second operand 22 states. [2019-11-06 18:46:55,625 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-06 18:46:55,625 INFO L93 Difference]: Finished difference Result 57 states and 60 transitions. [2019-11-06 18:46:55,626 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2019-11-06 18:46:55,626 INFO L78 Accepts]: Start accepts. Automaton has 22 states. Word has length 37 [2019-11-06 18:46:55,626 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-06 18:46:55,627 INFO L225 Difference]: With dead ends: 57 [2019-11-06 18:46:55,627 INFO L226 Difference]: Without dead ends: 43 [2019-11-06 18:46:55,628 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 52 GetRequests, 30 SyntacticMatches, 0 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 111 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=108, Invalid=444, Unknown=0, NotChecked=0, Total=552 [2019-11-06 18:46:55,629 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2019-11-06 18:46:55,632 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 42. [2019-11-06 18:46:55,632 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 42 states. [2019-11-06 18:46:55,633 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 42 states to 42 states and 43 transitions. [2019-11-06 18:46:55,633 INFO L78 Accepts]: Start accepts. Automaton has 42 states and 43 transitions. Word has length 37 [2019-11-06 18:46:55,633 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-06 18:46:55,634 INFO L462 AbstractCegarLoop]: Abstraction has 42 states and 43 transitions. [2019-11-06 18:46:55,634 INFO L463 AbstractCegarLoop]: Interpolant automaton has 22 states. [2019-11-06 18:46:55,634 INFO L276 IsEmpty]: Start isEmpty. Operand 42 states and 43 transitions. [2019-11-06 18:46:55,635 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2019-11-06 18:46:55,635 INFO L402 BasicCegarLoop]: Found error trace [2019-11-06 18:46:55,635 INFO L410 BasicCegarLoop]: trace histogram [10, 10, 5, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-06 18:46:55,836 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:46:55,836 INFO L410 AbstractCegarLoop]: === Iteration 13 === [mainErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-06 18:46:55,837 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-06 18:46:55,837 INFO L82 PathProgramCache]: Analyzing trace with hash -1202556527, now seen corresponding path program 10 times [2019-11-06 18:46:55,838 INFO L161 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-06 18:46:55,838 INFO L337 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1000455401] [2019-11-06 18:46:55,839 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-06 18:46:55,855 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:46:55,999 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:46:56,003 INFO L134 CoverageAnalysis]: Checked inductivity of 120 backedges. 0 proven. 100 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2019-11-06 18:46:56,004 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1000455401] [2019-11-06 18:46:56,004 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [279972998] [2019-11-06 18:46:56,004 INFO L92 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:46:56,062 INFO L249 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2019-11-06 18:46:56,062 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-06 18:46:56,063 INFO L256 TraceCheckSpWp]: Trace formula consists of 158 conjuncts, 12 conjunts are in the unsatisfiable core [2019-11-06 18:46:56,070 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2019-11-06 18:46:56,101 INFO L134 CoverageAnalysis]: Checked inductivity of 120 backedges. 0 proven. 100 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2019-11-06 18:46:56,102 INFO L218 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-06 18:46:56,102 INFO L231 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 13] total 15 [2019-11-06 18:46:56,102 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1789870154] [2019-11-06 18:46:56,103 INFO L442 AbstractCegarLoop]: Interpolant automaton has 15 states [2019-11-06 18:46:56,103 INFO L141 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-06 18:46:56,103 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2019-11-06 18:46:56,104 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=93, Invalid=117, Unknown=0, NotChecked=0, Total=210 [2019-11-06 18:46:56,104 INFO L87 Difference]: Start difference. First operand 42 states and 43 transitions. Second operand 15 states. [2019-11-06 18:46:56,187 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-06 18:46:56,187 INFO L93 Difference]: Finished difference Result 60 states and 62 transitions. [2019-11-06 18:46:56,188 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2019-11-06 18:46:56,188 INFO L78 Accepts]: Start accepts. Automaton has 15 states. Word has length 41 [2019-11-06 18:46:56,189 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-06 18:46:56,189 INFO L225 Difference]: With dead ends: 60 [2019-11-06 18:46:56,189 INFO L226 Difference]: Without dead ends: 45 [2019-11-06 18:46:56,190 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 55 GetRequests, 42 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 28 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=93, Invalid=117, Unknown=0, NotChecked=0, Total=210 [2019-11-06 18:46:56,193 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2019-11-06 18:46:56,201 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 44. [2019-11-06 18:46:56,201 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 44 states. [2019-11-06 18:46:56,203 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 45 transitions. [2019-11-06 18:46:56,203 INFO L78 Accepts]: Start accepts. Automaton has 44 states and 45 transitions. Word has length 41 [2019-11-06 18:46:56,203 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-06 18:46:56,204 INFO L462 AbstractCegarLoop]: Abstraction has 44 states and 45 transitions. [2019-11-06 18:46:56,204 INFO L463 AbstractCegarLoop]: Interpolant automaton has 15 states. [2019-11-06 18:46:56,204 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 45 transitions. [2019-11-06 18:46:56,205 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2019-11-06 18:46:56,208 INFO L402 BasicCegarLoop]: Found error trace [2019-11-06 18:46:56,208 INFO L410 BasicCegarLoop]: trace histogram [11, 11, 5, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-06 18:46:56,412 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:46:56,412 INFO L410 AbstractCegarLoop]: === Iteration 14 === [mainErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-06 18:46:56,412 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-06 18:46:56,412 INFO L82 PathProgramCache]: Analyzing trace with hash -1556314257, now seen corresponding path program 11 times [2019-11-06 18:46:56,413 INFO L161 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-06 18:46:56,413 INFO L337 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [733159065] [2019-11-06 18:46:56,413 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-06 18:46:56,437 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:46:56,577 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:46:56,580 INFO L134 CoverageAnalysis]: Checked inductivity of 141 backedges. 0 proven. 121 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2019-11-06 18:46:56,580 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [733159065] [2019-11-06 18:46:56,580 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1983241708] [2019-11-06 18:46:56,581 INFO L92 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:46:56,669 INFO L249 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 12 check-sat command(s) [2019-11-06 18:46:56,669 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-06 18:46:56,671 INFO L256 TraceCheckSpWp]: Trace formula consists of 164 conjuncts, 13 conjunts are in the unsatisfiable core [2019-11-06 18:46:56,672 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2019-11-06 18:46:56,697 INFO L134 CoverageAnalysis]: Checked inductivity of 141 backedges. 0 proven. 121 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2019-11-06 18:46:56,698 INFO L218 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-06 18:46:56,698 INFO L231 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 14] total 16 [2019-11-06 18:46:56,698 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [250107050] [2019-11-06 18:46:56,698 INFO L442 AbstractCegarLoop]: Interpolant automaton has 16 states [2019-11-06 18:46:56,699 INFO L141 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-06 18:46:56,702 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2019-11-06 18:46:56,702 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=107, Invalid=133, Unknown=0, NotChecked=0, Total=240 [2019-11-06 18:46:56,702 INFO L87 Difference]: Start difference. First operand 44 states and 45 transitions. Second operand 16 states. [2019-11-06 18:46:56,775 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-06 18:46:56,775 INFO L93 Difference]: Finished difference Result 62 states and 64 transitions. [2019-11-06 18:46:56,776 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2019-11-06 18:46:56,776 INFO L78 Accepts]: Start accepts. Automaton has 16 states. Word has length 43 [2019-11-06 18:46:56,777 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-06 18:46:56,777 INFO L225 Difference]: With dead ends: 62 [2019-11-06 18:46:56,778 INFO L226 Difference]: Without dead ends: 47 [2019-11-06 18:46:56,778 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 58 GetRequests, 44 SyntacticMatches, 0 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 31 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=107, Invalid=133, Unknown=0, NotChecked=0, Total=240 [2019-11-06 18:46:56,778 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2019-11-06 18:46:56,782 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 46. [2019-11-06 18:46:56,782 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 46 states. [2019-11-06 18:46:56,783 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 47 transitions. [2019-11-06 18:46:56,783 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 47 transitions. Word has length 43 [2019-11-06 18:46:56,784 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-06 18:46:56,784 INFO L462 AbstractCegarLoop]: Abstraction has 46 states and 47 transitions. [2019-11-06 18:46:56,784 INFO L463 AbstractCegarLoop]: Interpolant automaton has 16 states. [2019-11-06 18:46:56,784 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 47 transitions. [2019-11-06 18:46:56,784 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2019-11-06 18:46:56,785 INFO L402 BasicCegarLoop]: Found error trace [2019-11-06 18:46:56,785 INFO L410 BasicCegarLoop]: trace histogram [12, 12, 5, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-06 18:46:56,994 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:46:56,994 INFO L410 AbstractCegarLoop]: === Iteration 15 === [mainErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-06 18:46:56,994 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-06 18:46:56,995 INFO L82 PathProgramCache]: Analyzing trace with hash 2079890893, now seen corresponding path program 12 times [2019-11-06 18:46:56,995 INFO L161 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-06 18:46:56,995 INFO L337 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1488362865] [2019-11-06 18:46:56,996 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-06 18:46:57,010 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:46:57,140 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:46:57,143 INFO L134 CoverageAnalysis]: Checked inductivity of 164 backedges. 0 proven. 144 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2019-11-06 18:46:57,144 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1488362865] [2019-11-06 18:46:57,144 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1185522248] [2019-11-06 18:46:57,144 INFO L92 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:46:57,244 INFO L249 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 9 check-sat command(s) [2019-11-06 18:46:57,244 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-06 18:46:57,245 INFO L256 TraceCheckSpWp]: Trace formula consists of 146 conjuncts, 28 conjunts are in the unsatisfiable core [2019-11-06 18:46:57,247 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2019-11-06 18:46:57,269 INFO L375 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2019-11-06 18:46:57,270 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-06 18:46:57,275 INFO L567 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-06 18:46:57,275 INFO L496 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2019-11-06 18:46:57,276 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:22, output treesize:18 [2019-11-06 18:46:58,791 WARN L191 SmtUtils]: Spent 116.00 ms on a formula simplification. DAG size of input: 59 DAG size of output: 55 [2019-11-06 18:46:58,792 INFO L341 Elim1Store]: treesize reduction 17, result has 88.6 percent of original size [2019-11-06 18:46:58,792 INFO L375 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 5 select indices, 5 select index equivalence classes, 0 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 10 case distinctions, treesize of input 56 treesize of output 150 [2019-11-06 18:46:58,794 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:58,795 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:58,796 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:58,796 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:58,797 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:58,798 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:58,798 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:58,799 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:58,800 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:58,801 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:58,803 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:58,803 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:58,804 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:58,805 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:58,806 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:58,807 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:58,808 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:58,809 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:58,810 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:58,810 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:58,811 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:58,812 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:58,813 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:58,814 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:58,815 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:58,815 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:58,816 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:58,817 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:58,818 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:58,818 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:58,819 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:58,820 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:58,821 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:58,822 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:58,823 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:58,823 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:58,826 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-06 18:46:59,024 WARN L191 SmtUtils]: Spent 197.00 ms on a formula simplification. DAG size of input: 74 DAG size of output: 42 [2019-11-06 18:46:59,025 INFO L567 ElimStorePlain]: treesize reduction 523, result has 16.3 percent of original size [2019-11-06 18:46:59,026 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:59,031 INFO L496 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: 12 dim-0 vars, and 1 xjuncts. [2019-11-06 18:46:59,032 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 4 variables, input treesize:67, output treesize:545 [2019-11-06 18:46:59,232 WARN L191 SmtUtils]: Spent 127.00 ms on a formula simplification. DAG size of input: 48 DAG size of output: 30 [2019-11-06 18:46:59,234 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:59,274 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:46:59,324 INFO L134 CoverageAnalysis]: Checked inductivity of 164 backedges. 0 proven. 20 refuted. 0 times theorem prover too weak. 144 trivial. 0 not checked. [2019-11-06 18:46:59,326 INFO L218 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-06 18:46:59,326 INFO L231 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 13] total 27 [2019-11-06 18:46:59,327 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [15218477] [2019-11-06 18:46:59,330 INFO L442 AbstractCegarLoop]: Interpolant automaton has 27 states [2019-11-06 18:46:59,330 INFO L141 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-06 18:46:59,334 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2019-11-06 18:46:59,335 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=149, Invalid=550, Unknown=3, NotChecked=0, Total=702 [2019-11-06 18:46:59,336 INFO L87 Difference]: Start difference. First operand 46 states and 47 transitions. Second operand 27 states. [2019-11-06 18:47:01,996 WARN L191 SmtUtils]: Spent 801.00 ms on a formula simplification that was a NOOP. DAG size: 41 [2019-11-06 18:47:04,332 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-06 18:47:04,332 INFO L93 Difference]: Finished difference Result 67 states and 70 transitions. [2019-11-06 18:47:04,332 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2019-11-06 18:47:04,333 INFO L78 Accepts]: Start accepts. Automaton has 27 states. Word has length 45 [2019-11-06 18:47:04,333 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-06 18:47:04,334 INFO L225 Difference]: With dead ends: 67 [2019-11-06 18:47:04,334 INFO L226 Difference]: Without dead ends: 51 [2019-11-06 18:47:04,336 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 67 GetRequests, 36 SyntacticMatches, 0 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 197 ImplicationChecksByTransitivity, 6.4s TimeCoverageRelationStatistics Valid=195, Invalid=855, Unknown=6, NotChecked=0, Total=1056 [2019-11-06 18:47:04,336 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2019-11-06 18:47:04,341 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 50. [2019-11-06 18:47:04,341 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 50 states. [2019-11-06 18:47:04,342 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 51 transitions. [2019-11-06 18:47:04,342 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 51 transitions. Word has length 45 [2019-11-06 18:47:04,342 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-06 18:47:04,343 INFO L462 AbstractCegarLoop]: Abstraction has 50 states and 51 transitions. [2019-11-06 18:47:04,343 INFO L463 AbstractCegarLoop]: Interpolant automaton has 27 states. [2019-11-06 18:47:04,343 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 51 transitions. [2019-11-06 18:47:04,344 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2019-11-06 18:47:04,344 INFO L402 BasicCegarLoop]: Found error trace [2019-11-06 18:47:04,344 INFO L410 BasicCegarLoop]: trace histogram [13, 13, 6, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-06 18:47:04,547 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:47:04,547 INFO L410 AbstractCegarLoop]: === Iteration 16 === [mainErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-06 18:47:04,548 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-06 18:47:04,548 INFO L82 PathProgramCache]: Analyzing trace with hash -1240057554, now seen corresponding path program 13 times [2019-11-06 18:47:04,548 INFO L161 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-06 18:47:04,549 INFO L337 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [85660236] [2019-11-06 18:47:04,549 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-06 18:47:04,564 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:47:04,692 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:47:04,696 INFO L134 CoverageAnalysis]: Checked inductivity of 199 backedges. 0 proven. 169 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2019-11-06 18:47:04,696 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [85660236] [2019-11-06 18:47:04,697 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [187320203] [2019-11-06 18:47:04,697 INFO L92 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:47:04,760 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:47:04,761 INFO L256 TraceCheckSpWp]: Trace formula consists of 181 conjuncts, 15 conjunts are in the unsatisfiable core [2019-11-06 18:47:04,762 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2019-11-06 18:47:04,776 INFO L134 CoverageAnalysis]: Checked inductivity of 199 backedges. 0 proven. 169 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2019-11-06 18:47:04,776 INFO L218 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-06 18:47:04,776 INFO L231 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 16] total 18 [2019-11-06 18:47:04,776 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2026502307] [2019-11-06 18:47:04,777 INFO L442 AbstractCegarLoop]: Interpolant automaton has 18 states [2019-11-06 18:47:04,777 INFO L141 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-06 18:47:04,777 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2019-11-06 18:47:04,778 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=138, Invalid=168, Unknown=0, NotChecked=0, Total=306 [2019-11-06 18:47:04,778 INFO L87 Difference]: Start difference. First operand 50 states and 51 transitions. Second operand 18 states. [2019-11-06 18:47:04,865 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-06 18:47:04,865 INFO L93 Difference]: Finished difference Result 70 states and 72 transitions. [2019-11-06 18:47:04,865 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2019-11-06 18:47:04,866 INFO L78 Accepts]: Start accepts. Automaton has 18 states. Word has length 49 [2019-11-06 18:47:04,866 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-06 18:47:04,866 INFO L225 Difference]: With dead ends: 70 [2019-11-06 18:47:04,867 INFO L226 Difference]: Without dead ends: 53 [2019-11-06 18:47:04,867 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 66 GetRequests, 50 SyntacticMatches, 0 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 37 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=138, Invalid=168, Unknown=0, NotChecked=0, Total=306 [2019-11-06 18:47:04,867 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 53 states. [2019-11-06 18:47:04,872 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 53 to 52. [2019-11-06 18:47:04,872 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 52 states. [2019-11-06 18:47:04,873 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52 states to 52 states and 53 transitions. [2019-11-06 18:47:04,873 INFO L78 Accepts]: Start accepts. Automaton has 52 states and 53 transitions. Word has length 49 [2019-11-06 18:47:04,873 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-06 18:47:04,874 INFO L462 AbstractCegarLoop]: Abstraction has 52 states and 53 transitions. [2019-11-06 18:47:04,874 INFO L463 AbstractCegarLoop]: Interpolant automaton has 18 states. [2019-11-06 18:47:04,874 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 53 transitions. [2019-11-06 18:47:04,874 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2019-11-06 18:47:04,875 INFO L402 BasicCegarLoop]: Found error trace [2019-11-06 18:47:04,875 INFO L410 BasicCegarLoop]: trace histogram [14, 14, 6, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-06 18:47:05,084 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:47:05,084 INFO L410 AbstractCegarLoop]: === Iteration 17 === [mainErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-06 18:47:05,085 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-06 18:47:05,085 INFO L82 PathProgramCache]: Analyzing trace with hash 1198756108, now seen corresponding path program 14 times [2019-11-06 18:47:05,085 INFO L161 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-06 18:47:05,086 INFO L337 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1417334608] [2019-11-06 18:47:05,086 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-06 18:47:05,100 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:47:05,266 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:47:05,269 INFO L134 CoverageAnalysis]: Checked inductivity of 226 backedges. 0 proven. 196 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2019-11-06 18:47:05,269 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1417334608] [2019-11-06 18:47:05,269 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [656316496] [2019-11-06 18:47:05,269 INFO L92 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:47:05,333 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2019-11-06 18:47:05,334 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-06 18:47:05,335 INFO L256 TraceCheckSpWp]: Trace formula consists of 187 conjuncts, 16 conjunts are in the unsatisfiable core [2019-11-06 18:47:05,336 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2019-11-06 18:47:05,348 INFO L134 CoverageAnalysis]: Checked inductivity of 226 backedges. 0 proven. 196 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2019-11-06 18:47:05,349 INFO L218 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-06 18:47:05,349 INFO L231 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 17] total 19 [2019-11-06 18:47:05,349 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1284823499] [2019-11-06 18:47:05,349 INFO L442 AbstractCegarLoop]: Interpolant automaton has 19 states [2019-11-06 18:47:05,351 INFO L141 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-06 18:47:05,351 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2019-11-06 18:47:05,351 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=155, Invalid=187, Unknown=0, NotChecked=0, Total=342 [2019-11-06 18:47:05,351 INFO L87 Difference]: Start difference. First operand 52 states and 53 transitions. Second operand 19 states. [2019-11-06 18:47:05,428 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-06 18:47:05,428 INFO L93 Difference]: Finished difference Result 72 states and 74 transitions. [2019-11-06 18:47:05,428 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2019-11-06 18:47:05,428 INFO L78 Accepts]: Start accepts. Automaton has 19 states. Word has length 51 [2019-11-06 18:47:05,429 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-06 18:47:05,429 INFO L225 Difference]: With dead ends: 72 [2019-11-06 18:47:05,429 INFO L226 Difference]: Without dead ends: 55 [2019-11-06 18:47:05,430 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 69 GetRequests, 52 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 40 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=155, Invalid=187, Unknown=0, NotChecked=0, Total=342 [2019-11-06 18:47:05,430 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2019-11-06 18:47:05,434 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 54. [2019-11-06 18:47:05,434 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 54 states. [2019-11-06 18:47:05,435 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 55 transitions. [2019-11-06 18:47:05,435 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 55 transitions. Word has length 51 [2019-11-06 18:47:05,435 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-06 18:47:05,435 INFO L462 AbstractCegarLoop]: Abstraction has 54 states and 55 transitions. [2019-11-06 18:47:05,435 INFO L463 AbstractCegarLoop]: Interpolant automaton has 19 states. [2019-11-06 18:47:05,435 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 55 transitions. [2019-11-06 18:47:05,436 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 54 [2019-11-06 18:47:05,436 INFO L402 BasicCegarLoop]: Found error trace [2019-11-06 18:47:05,436 INFO L410 BasicCegarLoop]: trace histogram [15, 15, 6, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-06 18:47:05,640 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 15 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:47:05,640 INFO L410 AbstractCegarLoop]: === Iteration 18 === [mainErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-06 18:47:05,641 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-06 18:47:05,641 INFO L82 PathProgramCache]: Analyzing trace with hash -153458326, now seen corresponding path program 15 times [2019-11-06 18:47:05,641 INFO L161 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-06 18:47:05,641 INFO L337 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [516438586] [2019-11-06 18:47:05,642 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-06 18:47:05,656 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:47:05,863 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:47:05,868 INFO L134 CoverageAnalysis]: Checked inductivity of 255 backedges. 0 proven. 225 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2019-11-06 18:47:05,868 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [516438586] [2019-11-06 18:47:05,868 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [533938501] [2019-11-06 18:47:05,869 INFO L92 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:47:05,946 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2019-11-06 18:47:05,947 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-06 18:47:05,948 INFO L256 TraceCheckSpWp]: Trace formula consists of 133 conjuncts, 37 conjunts are in the unsatisfiable core [2019-11-06 18:47:05,949 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2019-11-06 18:47:05,976 INFO L375 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2019-11-06 18:47:05,976 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-06 18:47:05,983 INFO L567 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-06 18:47:05,984 INFO L496 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2019-11-06 18:47:05,984 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:22, output treesize:18 [2019-11-06 18:47:06,479 WARN L191 SmtUtils]: Spent 146.00 ms on a formula simplification. DAG size of input: 80 DAG size of output: 64 [2019-11-06 18:47:06,479 INFO L341 Elim1Store]: treesize reduction 62, result has 71.9 percent of original size [2019-11-06 18:47:06,480 INFO L375 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 6 select indices, 6 select index equivalence classes, 0 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 15 case distinctions, treesize of input 67 treesize of output 181 [2019-11-06 18:47:06,481 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,482 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,483 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,483 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,484 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,484 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,485 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,486 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,486 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,487 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,488 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,488 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,489 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,489 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,490 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,491 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,492 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,492 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,493 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,494 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,494 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,495 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,495 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,497 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,498 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,498 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,499 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,499 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,500 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,501 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,501 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,503 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,503 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,504 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,504 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,505 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,505 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,506 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,506 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,507 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,508 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,509 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,509 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,510 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,511 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,511 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,512 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,512 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,513 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,514 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,515 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,515 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,516 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,516 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,518 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,518 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,519 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,519 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,520 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,520 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,522 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,522 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,523 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,523 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,524 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,524 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,525 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,526 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,527 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,527 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,528 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,532 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-06 18:47:06,711 WARN L191 SmtUtils]: Spent 178.00 ms on a formula simplification. DAG size of input: 98 DAG size of output: 32 [2019-11-06 18:47:06,712 INFO L567 ElimStorePlain]: treesize reduction 1251, result has 5.2 percent of original size [2019-11-06 18:47:06,713 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,714 INFO L496 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2019-11-06 18:47:06,714 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 3 variables, input treesize:73, output treesize:67 [2019-11-06 18:47:06,714 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,760 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,801 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:06,878 INFO L134 CoverageAnalysis]: Checked inductivity of 255 backedges. 0 proven. 30 refuted. 0 times theorem prover too weak. 225 trivial. 0 not checked. [2019-11-06 18:47:06,879 INFO L218 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-06 18:47:06,879 INFO L231 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 15] total 32 [2019-11-06 18:47:06,880 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [607589681] [2019-11-06 18:47:06,880 INFO L442 AbstractCegarLoop]: Interpolant automaton has 32 states [2019-11-06 18:47:06,880 INFO L141 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-06 18:47:06,881 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2019-11-06 18:47:06,882 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=196, Invalid=796, Unknown=0, NotChecked=0, Total=992 [2019-11-06 18:47:06,882 INFO L87 Difference]: Start difference. First operand 54 states and 55 transitions. Second operand 32 states. [2019-11-06 18:47:07,397 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-06 18:47:07,397 INFO L93 Difference]: Finished difference Result 77 states and 80 transitions. [2019-11-06 18:47:07,397 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 32 states. [2019-11-06 18:47:07,397 INFO L78 Accepts]: Start accepts. Automaton has 32 states. Word has length 53 [2019-11-06 18:47:07,397 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-06 18:47:07,398 INFO L225 Difference]: With dead ends: 77 [2019-11-06 18:47:07,398 INFO L226 Difference]: Without dead ends: 59 [2019-11-06 18:47:07,399 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 74 GetRequests, 42 SyntacticMatches, 0 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 254 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=206, Invalid=916, Unknown=0, NotChecked=0, Total=1122 [2019-11-06 18:47:07,399 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 59 states. [2019-11-06 18:47:07,403 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 59 to 58. [2019-11-06 18:47:07,403 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 58 states. [2019-11-06 18:47:07,404 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 59 transitions. [2019-11-06 18:47:07,404 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 59 transitions. Word has length 53 [2019-11-06 18:47:07,404 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-06 18:47:07,404 INFO L462 AbstractCegarLoop]: Abstraction has 58 states and 59 transitions. [2019-11-06 18:47:07,404 INFO L463 AbstractCegarLoop]: Interpolant automaton has 32 states. [2019-11-06 18:47:07,404 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 59 transitions. [2019-11-06 18:47:07,405 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 58 [2019-11-06 18:47:07,405 INFO L402 BasicCegarLoop]: Found error trace [2019-11-06 18:47:07,405 INFO L410 BasicCegarLoop]: trace histogram [16, 16, 7, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-06 18:47:07,609 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:47:07,609 INFO L410 AbstractCegarLoop]: === Iteration 19 === [mainErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-06 18:47:07,609 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-06 18:47:07,610 INFO L82 PathProgramCache]: Analyzing trace with hash 523064203, now seen corresponding path program 16 times [2019-11-06 18:47:07,610 INFO L161 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-06 18:47:07,610 INFO L337 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1869538892] [2019-11-06 18:47:07,610 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-06 18:47:07,625 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:47:07,811 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:47:07,815 INFO L134 CoverageAnalysis]: Checked inductivity of 298 backedges. 0 proven. 256 refuted. 0 times theorem prover too weak. 42 trivial. 0 not checked. [2019-11-06 18:47:07,815 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1869538892] [2019-11-06 18:47:07,816 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1577576378] [2019-11-06 18:47:07,816 INFO L92 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 17 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 17 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:47:07,884 INFO L249 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2019-11-06 18:47:07,884 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-06 18:47:07,885 INFO L256 TraceCheckSpWp]: Trace formula consists of 204 conjuncts, 18 conjunts are in the unsatisfiable core [2019-11-06 18:47:07,886 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2019-11-06 18:47:07,899 INFO L134 CoverageAnalysis]: Checked inductivity of 298 backedges. 0 proven. 256 refuted. 0 times theorem prover too weak. 42 trivial. 0 not checked. [2019-11-06 18:47:07,900 INFO L218 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-06 18:47:07,900 INFO L231 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 19] total 21 [2019-11-06 18:47:07,900 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1830249938] [2019-11-06 18:47:07,901 INFO L442 AbstractCegarLoop]: Interpolant automaton has 21 states [2019-11-06 18:47:07,901 INFO L141 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-06 18:47:07,901 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2019-11-06 18:47:07,901 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=192, Invalid=228, Unknown=0, NotChecked=0, Total=420 [2019-11-06 18:47:07,901 INFO L87 Difference]: Start difference. First operand 58 states and 59 transitions. Second operand 21 states. [2019-11-06 18:47:08,004 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-06 18:47:08,004 INFO L93 Difference]: Finished difference Result 80 states and 82 transitions. [2019-11-06 18:47:08,004 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2019-11-06 18:47:08,004 INFO L78 Accepts]: Start accepts. Automaton has 21 states. Word has length 57 [2019-11-06 18:47:08,004 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-06 18:47:08,005 INFO L225 Difference]: With dead ends: 80 [2019-11-06 18:47:08,005 INFO L226 Difference]: Without dead ends: 61 [2019-11-06 18:47:08,006 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 77 GetRequests, 58 SyntacticMatches, 0 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 46 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=192, Invalid=228, Unknown=0, NotChecked=0, Total=420 [2019-11-06 18:47:08,006 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 61 states. [2019-11-06 18:47:08,017 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 61 to 60. [2019-11-06 18:47:08,017 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 60 states. [2019-11-06 18:47:08,018 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 60 states to 60 states and 61 transitions. [2019-11-06 18:47:08,018 INFO L78 Accepts]: Start accepts. Automaton has 60 states and 61 transitions. Word has length 57 [2019-11-06 18:47:08,018 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-06 18:47:08,018 INFO L462 AbstractCegarLoop]: Abstraction has 60 states and 61 transitions. [2019-11-06 18:47:08,018 INFO L463 AbstractCegarLoop]: Interpolant automaton has 21 states. [2019-11-06 18:47:08,019 INFO L276 IsEmpty]: Start isEmpty. Operand 60 states and 61 transitions. [2019-11-06 18:47:08,019 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2019-11-06 18:47:08,019 INFO L402 BasicCegarLoop]: Found error trace [2019-11-06 18:47:08,019 INFO L410 BasicCegarLoop]: trace histogram [17, 17, 7, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-06 18:47:08,220 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:47:08,220 INFO L410 AbstractCegarLoop]: === Iteration 20 === [mainErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-06 18:47:08,220 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-06 18:47:08,220 INFO L82 PathProgramCache]: Analyzing trace with hash -660869783, now seen corresponding path program 17 times [2019-11-06 18:47:08,221 INFO L161 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-06 18:47:08,221 INFO L337 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [491342805] [2019-11-06 18:47:08,221 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-06 18:47:08,237 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:47:08,453 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:47:08,458 INFO L134 CoverageAnalysis]: Checked inductivity of 331 backedges. 0 proven. 289 refuted. 0 times theorem prover too weak. 42 trivial. 0 not checked. [2019-11-06 18:47:08,458 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [491342805] [2019-11-06 18:47:08,458 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2092917594] [2019-11-06 18:47:08,458 INFO L92 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 18 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 18 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:47:08,644 INFO L249 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 18 check-sat command(s) [2019-11-06 18:47:08,645 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-06 18:47:08,646 INFO L256 TraceCheckSpWp]: Trace formula consists of 210 conjuncts, 19 conjunts are in the unsatisfiable core [2019-11-06 18:47:08,648 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2019-11-06 18:47:08,663 INFO L134 CoverageAnalysis]: Checked inductivity of 331 backedges. 0 proven. 289 refuted. 0 times theorem prover too weak. 42 trivial. 0 not checked. [2019-11-06 18:47:08,664 INFO L218 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-06 18:47:08,664 INFO L231 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 20] total 22 [2019-11-06 18:47:08,665 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1092784893] [2019-11-06 18:47:08,665 INFO L442 AbstractCegarLoop]: Interpolant automaton has 22 states [2019-11-06 18:47:08,665 INFO L141 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-06 18:47:08,666 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2019-11-06 18:47:08,666 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=212, Invalid=250, Unknown=0, NotChecked=0, Total=462 [2019-11-06 18:47:08,666 INFO L87 Difference]: Start difference. First operand 60 states and 61 transitions. Second operand 22 states. [2019-11-06 18:47:08,781 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-06 18:47:08,781 INFO L93 Difference]: Finished difference Result 82 states and 84 transitions. [2019-11-06 18:47:08,782 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2019-11-06 18:47:08,782 INFO L78 Accepts]: Start accepts. Automaton has 22 states. Word has length 59 [2019-11-06 18:47:08,782 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-06 18:47:08,783 INFO L225 Difference]: With dead ends: 82 [2019-11-06 18:47:08,783 INFO L226 Difference]: Without dead ends: 63 [2019-11-06 18:47:08,784 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 80 GetRequests, 60 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 49 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=212, Invalid=250, Unknown=0, NotChecked=0, Total=462 [2019-11-06 18:47:08,784 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2019-11-06 18:47:08,788 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 62. [2019-11-06 18:47:08,789 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 62 states. [2019-11-06 18:47:08,789 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 63 transitions. [2019-11-06 18:47:08,789 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 63 transitions. Word has length 59 [2019-11-06 18:47:08,789 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-06 18:47:08,790 INFO L462 AbstractCegarLoop]: Abstraction has 62 states and 63 transitions. [2019-11-06 18:47:08,790 INFO L463 AbstractCegarLoop]: Interpolant automaton has 22 states. [2019-11-06 18:47:08,790 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 63 transitions. [2019-11-06 18:47:08,790 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 62 [2019-11-06 18:47:08,791 INFO L402 BasicCegarLoop]: Found error trace [2019-11-06 18:47:08,791 INFO L410 BasicCegarLoop]: trace histogram [18, 18, 7, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-06 18:47:09,000 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 18 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:47:09,000 INFO L410 AbstractCegarLoop]: === Iteration 21 === [mainErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-06 18:47:09,001 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-06 18:47:09,001 INFO L82 PathProgramCache]: Analyzing trace with hash -255096889, now seen corresponding path program 18 times [2019-11-06 18:47:09,001 INFO L161 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-06 18:47:09,002 INFO L337 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1529362540] [2019-11-06 18:47:09,002 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-06 18:47:09,016 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:47:09,213 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:47:09,221 INFO L134 CoverageAnalysis]: Checked inductivity of 366 backedges. 0 proven. 324 refuted. 0 times theorem prover too weak. 42 trivial. 0 not checked. [2019-11-06 18:47:09,222 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1529362540] [2019-11-06 18:47:09,222 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [577081497] [2019-11-06 18:47:09,222 INFO L92 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 19 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 19 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:47:09,432 INFO L249 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 13 check-sat command(s) [2019-11-06 18:47:09,432 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-06 18:47:09,434 INFO L256 TraceCheckSpWp]: Trace formula consists of 180 conjuncts, 47 conjunts are in the unsatisfiable core [2019-11-06 18:47:09,435 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2019-11-06 18:47:09,496 INFO L375 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2019-11-06 18:47:09,496 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-06 18:47:09,501 INFO L567 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-06 18:47:09,501 INFO L496 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2019-11-06 18:47:09,502 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:22, output treesize:18 [2019-11-06 18:47:10,166 WARN L191 SmtUtils]: Spent 163.00 ms on a formula simplification. DAG size of input: 107 DAG size of output: 67 [2019-11-06 18:47:10,167 INFO L341 Elim1Store]: treesize reduction 112, result has 57.7 percent of original size [2019-11-06 18:47:10,167 INFO L375 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 7 select indices, 7 select index equivalence classes, 0 disjoint index pairs (out of 21 index pairs), introduced 7 new quantified variables, introduced 21 case distinctions, treesize of input 71 treesize of output 179 [2019-11-06 18:47:10,169 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:10,169 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:10,170 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:10,170 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:10,170 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:10,171 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:10,171 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:10,171 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:10,172 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:10,172 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:10,173 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-06 18:47:10,244 INFO L567 ElimStorePlain]: treesize reduction 135, result has 34.5 percent of original size [2019-11-06 18:47:10,245 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:10,246 INFO L496 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2019-11-06 18:47:10,246 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 3 variables, input treesize:77, output treesize:71 [2019-11-06 18:47:10,246 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:10,298 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:10,351 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:10,520 INFO L134 CoverageAnalysis]: Checked inductivity of 366 backedges. 35 proven. 42 refuted. 0 times theorem prover too weak. 289 trivial. 0 not checked. [2019-11-06 18:47:10,521 INFO L218 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-06 18:47:10,521 INFO L231 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 19] total 39 [2019-11-06 18:47:10,521 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [729748634] [2019-11-06 18:47:10,522 INFO L442 AbstractCegarLoop]: Interpolant automaton has 39 states [2019-11-06 18:47:10,522 INFO L141 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-06 18:47:10,522 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 39 interpolants. [2019-11-06 18:47:10,523 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=303, Invalid=1179, Unknown=0, NotChecked=0, Total=1482 [2019-11-06 18:47:10,523 INFO L87 Difference]: Start difference. First operand 62 states and 63 transitions. Second operand 39 states. [2019-11-06 18:47:11,539 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-06 18:47:11,540 INFO L93 Difference]: Finished difference Result 88 states and 92 transitions. [2019-11-06 18:47:11,540 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 39 states. [2019-11-06 18:47:11,540 INFO L78 Accepts]: Start accepts. Automaton has 39 states. Word has length 61 [2019-11-06 18:47:11,540 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-06 18:47:11,541 INFO L225 Difference]: With dead ends: 88 [2019-11-06 18:47:11,541 INFO L226 Difference]: Without dead ends: 68 [2019-11-06 18:47:11,543 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 98 GetRequests, 46 SyntacticMatches, 0 SemanticMatches, 52 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 515 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=405, Invalid=2457, Unknown=0, NotChecked=0, Total=2862 [2019-11-06 18:47:11,544 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 68 states. [2019-11-06 18:47:11,552 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 68 to 68. [2019-11-06 18:47:11,552 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 68 states. [2019-11-06 18:47:11,552 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 68 states to 68 states and 69 transitions. [2019-11-06 18:47:11,553 INFO L78 Accepts]: Start accepts. Automaton has 68 states and 69 transitions. Word has length 61 [2019-11-06 18:47:11,553 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-06 18:47:11,553 INFO L462 AbstractCegarLoop]: Abstraction has 68 states and 69 transitions. [2019-11-06 18:47:11,553 INFO L463 AbstractCegarLoop]: Interpolant automaton has 39 states. [2019-11-06 18:47:11,553 INFO L276 IsEmpty]: Start isEmpty. Operand 68 states and 69 transitions. [2019-11-06 18:47:11,554 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 68 [2019-11-06 18:47:11,554 INFO L402 BasicCegarLoop]: Found error trace [2019-11-06 18:47:11,554 INFO L410 BasicCegarLoop]: trace histogram [20, 20, 8, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-06 18:47:11,757 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 19 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:47:11,757 INFO L410 AbstractCegarLoop]: === Iteration 22 === [mainErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-06 18:47:11,758 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-06 18:47:11,758 INFO L82 PathProgramCache]: Analyzing trace with hash -1190794106, now seen corresponding path program 19 times [2019-11-06 18:47:11,759 INFO L161 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-06 18:47:11,759 INFO L337 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1076298013] [2019-11-06 18:47:11,759 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-06 18:47:11,775 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:47:12,004 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:47:12,008 INFO L134 CoverageAnalysis]: Checked inductivity of 456 backedges. 0 proven. 400 refuted. 0 times theorem prover too weak. 56 trivial. 0 not checked. [2019-11-06 18:47:12,008 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1076298013] [2019-11-06 18:47:12,008 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [431217278] [2019-11-06 18:47:12,008 INFO L92 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 20 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 20 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:47:12,096 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:47:12,097 INFO L256 TraceCheckSpWp]: Trace formula consists of 233 conjuncts, 22 conjunts are in the unsatisfiable core [2019-11-06 18:47:12,099 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2019-11-06 18:47:12,111 INFO L134 CoverageAnalysis]: Checked inductivity of 456 backedges. 0 proven. 400 refuted. 0 times theorem prover too weak. 56 trivial. 0 not checked. [2019-11-06 18:47:12,112 INFO L218 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-06 18:47:12,112 INFO L231 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [24, 23] total 25 [2019-11-06 18:47:12,112 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1401851562] [2019-11-06 18:47:12,112 INFO L442 AbstractCegarLoop]: Interpolant automaton has 25 states [2019-11-06 18:47:12,113 INFO L141 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-06 18:47:12,113 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2019-11-06 18:47:12,113 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=278, Invalid=322, Unknown=0, NotChecked=0, Total=600 [2019-11-06 18:47:12,113 INFO L87 Difference]: Start difference. First operand 68 states and 69 transitions. Second operand 25 states. [2019-11-06 18:47:12,214 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-06 18:47:12,214 INFO L93 Difference]: Finished difference Result 92 states and 94 transitions. [2019-11-06 18:47:12,216 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2019-11-06 18:47:12,217 INFO L78 Accepts]: Start accepts. Automaton has 25 states. Word has length 67 [2019-11-06 18:47:12,217 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-06 18:47:12,217 INFO L225 Difference]: With dead ends: 92 [2019-11-06 18:47:12,218 INFO L226 Difference]: Without dead ends: 71 [2019-11-06 18:47:12,218 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 91 GetRequests, 68 SyntacticMatches, 0 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 58 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=278, Invalid=322, Unknown=0, NotChecked=0, Total=600 [2019-11-06 18:47:12,218 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 71 states. [2019-11-06 18:47:12,224 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 71 to 70. [2019-11-06 18:47:12,224 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 70 states. [2019-11-06 18:47:12,225 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 70 states to 70 states and 71 transitions. [2019-11-06 18:47:12,225 INFO L78 Accepts]: Start accepts. Automaton has 70 states and 71 transitions. Word has length 67 [2019-11-06 18:47:12,225 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-06 18:47:12,225 INFO L462 AbstractCegarLoop]: Abstraction has 70 states and 71 transitions. [2019-11-06 18:47:12,226 INFO L463 AbstractCegarLoop]: Interpolant automaton has 25 states. [2019-11-06 18:47:12,226 INFO L276 IsEmpty]: Start isEmpty. Operand 70 states and 71 transitions. [2019-11-06 18:47:12,226 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 70 [2019-11-06 18:47:12,226 INFO L402 BasicCegarLoop]: Found error trace [2019-11-06 18:47:12,226 INFO L410 BasicCegarLoop]: trace histogram [21, 21, 8, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-06 18:47:12,436 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 20 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:47:12,436 INFO L410 AbstractCegarLoop]: === Iteration 23 === [mainErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-06 18:47:12,436 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-06 18:47:12,436 INFO L82 PathProgramCache]: Analyzing trace with hash -837007132, now seen corresponding path program 20 times [2019-11-06 18:47:12,436 INFO L161 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-06 18:47:12,436 INFO L337 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1809155303] [2019-11-06 18:47:12,437 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-06 18:47:12,453 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:47:12,778 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:47:12,784 INFO L134 CoverageAnalysis]: Checked inductivity of 497 backedges. 0 proven. 441 refuted. 0 times theorem prover too weak. 56 trivial. 0 not checked. [2019-11-06 18:47:12,784 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1809155303] [2019-11-06 18:47:12,785 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1652819594] [2019-11-06 18:47:12,785 INFO L92 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 21 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 21 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:47:12,919 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2019-11-06 18:47:12,920 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-06 18:47:12,922 INFO L256 TraceCheckSpWp]: Trace formula consists of 239 conjuncts, 23 conjunts are in the unsatisfiable core [2019-11-06 18:47:12,924 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2019-11-06 18:47:12,962 INFO L134 CoverageAnalysis]: Checked inductivity of 497 backedges. 0 proven. 441 refuted. 0 times theorem prover too weak. 56 trivial. 0 not checked. [2019-11-06 18:47:12,963 INFO L218 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-06 18:47:12,963 INFO L231 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [25, 24] total 26 [2019-11-06 18:47:12,966 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [989846541] [2019-11-06 18:47:12,966 INFO L442 AbstractCegarLoop]: Interpolant automaton has 26 states [2019-11-06 18:47:12,967 INFO L141 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-06 18:47:12,967 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2019-11-06 18:47:12,968 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=302, Invalid=348, Unknown=0, NotChecked=0, Total=650 [2019-11-06 18:47:12,968 INFO L87 Difference]: Start difference. First operand 70 states and 71 transitions. Second operand 26 states. [2019-11-06 18:47:13,161 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-06 18:47:13,161 INFO L93 Difference]: Finished difference Result 94 states and 96 transitions. [2019-11-06 18:47:13,161 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2019-11-06 18:47:13,162 INFO L78 Accepts]: Start accepts. Automaton has 26 states. Word has length 69 [2019-11-06 18:47:13,162 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-06 18:47:13,163 INFO L225 Difference]: With dead ends: 94 [2019-11-06 18:47:13,163 INFO L226 Difference]: Without dead ends: 73 [2019-11-06 18:47:13,164 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 94 GetRequests, 70 SyntacticMatches, 0 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 61 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=302, Invalid=348, Unknown=0, NotChecked=0, Total=650 [2019-11-06 18:47:13,164 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 73 states. [2019-11-06 18:47:13,168 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 73 to 72. [2019-11-06 18:47:13,168 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 72 states. [2019-11-06 18:47:13,168 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 72 states to 72 states and 73 transitions. [2019-11-06 18:47:13,169 INFO L78 Accepts]: Start accepts. Automaton has 72 states and 73 transitions. Word has length 69 [2019-11-06 18:47:13,169 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-06 18:47:13,170 INFO L462 AbstractCegarLoop]: Abstraction has 72 states and 73 transitions. [2019-11-06 18:47:13,170 INFO L463 AbstractCegarLoop]: Interpolant automaton has 26 states. [2019-11-06 18:47:13,170 INFO L276 IsEmpty]: Start isEmpty. Operand 72 states and 73 transitions. [2019-11-06 18:47:13,170 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 72 [2019-11-06 18:47:13,171 INFO L402 BasicCegarLoop]: Found error trace [2019-11-06 18:47:13,171 INFO L410 BasicCegarLoop]: trace histogram [22, 22, 8, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-06 18:47:13,374 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 21 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:47:13,374 INFO L410 AbstractCegarLoop]: === Iteration 24 === [mainErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-06 18:47:13,374 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-06 18:47:13,375 INFO L82 PathProgramCache]: Analyzing trace with hash -150141502, now seen corresponding path program 21 times [2019-11-06 18:47:13,375 INFO L161 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-06 18:47:13,375 INFO L337 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [344058993] [2019-11-06 18:47:13,375 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-06 18:47:13,395 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:47:13,724 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:47:13,731 INFO L134 CoverageAnalysis]: Checked inductivity of 540 backedges. 0 proven. 484 refuted. 0 times theorem prover too weak. 56 trivial. 0 not checked. [2019-11-06 18:47:13,731 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [344058993] [2019-11-06 18:47:13,731 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [705584751] [2019-11-06 18:47:13,731 INFO L92 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 22 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 22 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:47:13,827 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 8 check-sat command(s) [2019-11-06 18:47:13,827 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-06 18:47:13,829 INFO L256 TraceCheckSpWp]: Trace formula consists of 155 conjuncts, 47 conjunts are in the unsatisfiable core [2019-11-06 18:47:13,831 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2019-11-06 18:47:13,850 INFO L375 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2019-11-06 18:47:13,851 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-06 18:47:13,856 INFO L567 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-06 18:47:13,857 INFO L496 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2019-11-06 18:47:13,857 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:22, output treesize:18 [2019-11-06 18:47:14,762 WARN L191 SmtUtils]: Spent 193.00 ms on a formula simplification. DAG size of input: 138 DAG size of output: 78 [2019-11-06 18:47:14,763 INFO L341 Elim1Store]: treesize reduction 170, result has 51.6 percent of original size [2019-11-06 18:47:14,763 INFO L375 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 8 select indices, 8 select index equivalence classes, 0 disjoint index pairs (out of 28 index pairs), introduced 8 new quantified variables, introduced 28 case distinctions, treesize of input 81 treesize of output 211 [2019-11-06 18:47:14,766 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:14,766 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:14,767 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:14,767 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:14,768 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:14,768 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:14,768 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:14,769 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:14,769 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:14,770 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:14,770 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:14,770 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:14,772 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-06 18:47:14,865 INFO L567 ElimStorePlain]: treesize reduction 150, result has 35.1 percent of original size [2019-11-06 18:47:14,866 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:14,867 INFO L496 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2019-11-06 18:47:14,868 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 3 variables, input treesize:87, output treesize:81 [2019-11-06 18:47:14,868 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:14,961 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:15,048 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:15,355 INFO L134 CoverageAnalysis]: Checked inductivity of 540 backedges. 0 proven. 56 refuted. 0 times theorem prover too weak. 484 trivial. 0 not checked. [2019-11-06 18:47:15,356 INFO L218 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-06 18:47:15,356 INFO L231 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [26, 19] total 43 [2019-11-06 18:47:15,357 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1098343474] [2019-11-06 18:47:15,358 INFO L442 AbstractCegarLoop]: Interpolant automaton has 43 states [2019-11-06 18:47:15,358 INFO L141 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-06 18:47:15,359 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 43 interpolants. [2019-11-06 18:47:15,362 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=357, Invalid=1449, Unknown=0, NotChecked=0, Total=1806 [2019-11-06 18:47:15,362 INFO L87 Difference]: Start difference. First operand 72 states and 73 transitions. Second operand 43 states. [2019-11-06 18:47:16,533 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-06 18:47:16,533 INFO L93 Difference]: Finished difference Result 99 states and 102 transitions. [2019-11-06 18:47:16,533 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 43 states. [2019-11-06 18:47:16,533 INFO L78 Accepts]: Start accepts. Automaton has 43 states. Word has length 71 [2019-11-06 18:47:16,534 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-06 18:47:16,534 INFO L225 Difference]: With dead ends: 99 [2019-11-06 18:47:16,534 INFO L226 Difference]: Without dead ends: 77 [2019-11-06 18:47:16,536 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 99 GetRequests, 56 SyntacticMatches, 0 SemanticMatches, 43 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 472 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=367, Invalid=1613, Unknown=0, NotChecked=0, Total=1980 [2019-11-06 18:47:16,536 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 77 states. [2019-11-06 18:47:16,540 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 77 to 76. [2019-11-06 18:47:16,541 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 76 states. [2019-11-06 18:47:16,541 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 76 states to 76 states and 77 transitions. [2019-11-06 18:47:16,541 INFO L78 Accepts]: Start accepts. Automaton has 76 states and 77 transitions. Word has length 71 [2019-11-06 18:47:16,542 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-06 18:47:16,542 INFO L462 AbstractCegarLoop]: Abstraction has 76 states and 77 transitions. [2019-11-06 18:47:16,542 INFO L463 AbstractCegarLoop]: Interpolant automaton has 43 states. [2019-11-06 18:47:16,542 INFO L276 IsEmpty]: Start isEmpty. Operand 76 states and 77 transitions. [2019-11-06 18:47:16,543 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2019-11-06 18:47:16,543 INFO L402 BasicCegarLoop]: Found error trace [2019-11-06 18:47:16,543 INFO L410 BasicCegarLoop]: trace histogram [23, 23, 9, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-06 18:47:16,744 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 22 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:47:16,744 INFO L410 AbstractCegarLoop]: === Iteration 25 === [mainErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-06 18:47:16,744 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-06 18:47:16,745 INFO L82 PathProgramCache]: Analyzing trace with hash -30548381, now seen corresponding path program 22 times [2019-11-06 18:47:16,745 INFO L161 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-06 18:47:16,745 INFO L337 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [59857466] [2019-11-06 18:47:16,745 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-06 18:47:16,763 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:47:17,043 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:47:17,049 INFO L134 CoverageAnalysis]: Checked inductivity of 601 backedges. 0 proven. 529 refuted. 0 times theorem prover too weak. 72 trivial. 0 not checked. [2019-11-06 18:47:17,050 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [59857466] [2019-11-06 18:47:17,050 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [286694507] [2019-11-06 18:47:17,050 INFO L92 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 23 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 23 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:47:17,141 INFO L249 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2019-11-06 18:47:17,142 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-06 18:47:17,143 INFO L256 TraceCheckSpWp]: Trace formula consists of 256 conjuncts, 25 conjunts are in the unsatisfiable core [2019-11-06 18:47:17,144 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2019-11-06 18:47:17,169 INFO L134 CoverageAnalysis]: Checked inductivity of 601 backedges. 0 proven. 529 refuted. 0 times theorem prover too weak. 72 trivial. 0 not checked. [2019-11-06 18:47:17,169 INFO L218 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-06 18:47:17,170 INFO L231 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [27, 26] total 28 [2019-11-06 18:47:17,170 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1250322034] [2019-11-06 18:47:17,170 INFO L442 AbstractCegarLoop]: Interpolant automaton has 28 states [2019-11-06 18:47:17,170 INFO L141 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-06 18:47:17,170 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2019-11-06 18:47:17,171 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=353, Invalid=403, Unknown=0, NotChecked=0, Total=756 [2019-11-06 18:47:17,171 INFO L87 Difference]: Start difference. First operand 76 states and 77 transitions. Second operand 28 states. [2019-11-06 18:47:17,317 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-06 18:47:17,317 INFO L93 Difference]: Finished difference Result 102 states and 104 transitions. [2019-11-06 18:47:17,318 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2019-11-06 18:47:17,318 INFO L78 Accepts]: Start accepts. Automaton has 28 states. Word has length 75 [2019-11-06 18:47:17,318 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-06 18:47:17,319 INFO L225 Difference]: With dead ends: 102 [2019-11-06 18:47:17,319 INFO L226 Difference]: Without dead ends: 79 [2019-11-06 18:47:17,319 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 102 GetRequests, 76 SyntacticMatches, 0 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 67 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=353, Invalid=403, Unknown=0, NotChecked=0, Total=756 [2019-11-06 18:47:17,320 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 79 states. [2019-11-06 18:47:17,324 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 79 to 78. [2019-11-06 18:47:17,325 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 78 states. [2019-11-06 18:47:17,325 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 78 states to 78 states and 79 transitions. [2019-11-06 18:47:17,326 INFO L78 Accepts]: Start accepts. Automaton has 78 states and 79 transitions. Word has length 75 [2019-11-06 18:47:17,326 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-06 18:47:17,326 INFO L462 AbstractCegarLoop]: Abstraction has 78 states and 79 transitions. [2019-11-06 18:47:17,326 INFO L463 AbstractCegarLoop]: Interpolant automaton has 28 states. [2019-11-06 18:47:17,326 INFO L276 IsEmpty]: Start isEmpty. Operand 78 states and 79 transitions. [2019-11-06 18:47:17,327 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 78 [2019-11-06 18:47:17,327 INFO L402 BasicCegarLoop]: Found error trace [2019-11-06 18:47:17,327 INFO L410 BasicCegarLoop]: trace histogram [24, 24, 9, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-06 18:47:17,538 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 23 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:47:17,538 INFO L410 AbstractCegarLoop]: === Iteration 26 === [mainErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-06 18:47:17,538 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-06 18:47:17,538 INFO L82 PathProgramCache]: Analyzing trace with hash -1505166143, now seen corresponding path program 23 times [2019-11-06 18:47:17,538 INFO L161 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-06 18:47:17,538 INFO L337 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1377886691] [2019-11-06 18:47:17,539 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-06 18:47:17,555 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:47:17,866 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:47:17,871 INFO L134 CoverageAnalysis]: Checked inductivity of 648 backedges. 0 proven. 576 refuted. 0 times theorem prover too weak. 72 trivial. 0 not checked. [2019-11-06 18:47:17,872 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1377886691] [2019-11-06 18:47:17,872 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1816241050] [2019-11-06 18:47:17,872 INFO L92 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 24 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 24 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:47:18,228 INFO L249 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 25 check-sat command(s) [2019-11-06 18:47:18,228 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-06 18:47:18,230 INFO L256 TraceCheckSpWp]: Trace formula consists of 262 conjuncts, 26 conjunts are in the unsatisfiable core [2019-11-06 18:47:18,231 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2019-11-06 18:47:18,254 INFO L134 CoverageAnalysis]: Checked inductivity of 648 backedges. 0 proven. 576 refuted. 0 times theorem prover too weak. 72 trivial. 0 not checked. [2019-11-06 18:47:18,254 INFO L218 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-06 18:47:18,255 INFO L231 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [28, 27] total 29 [2019-11-06 18:47:18,255 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [89376330] [2019-11-06 18:47:18,255 INFO L442 AbstractCegarLoop]: Interpolant automaton has 29 states [2019-11-06 18:47:18,255 INFO L141 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-06 18:47:18,256 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2019-11-06 18:47:18,256 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=380, Invalid=432, Unknown=0, NotChecked=0, Total=812 [2019-11-06 18:47:18,256 INFO L87 Difference]: Start difference. First operand 78 states and 79 transitions. Second operand 29 states. [2019-11-06 18:47:18,383 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-06 18:47:18,383 INFO L93 Difference]: Finished difference Result 104 states and 106 transitions. [2019-11-06 18:47:18,383 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2019-11-06 18:47:18,384 INFO L78 Accepts]: Start accepts. Automaton has 29 states. Word has length 77 [2019-11-06 18:47:18,384 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-06 18:47:18,384 INFO L225 Difference]: With dead ends: 104 [2019-11-06 18:47:18,385 INFO L226 Difference]: Without dead ends: 81 [2019-11-06 18:47:18,385 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 105 GetRequests, 78 SyntacticMatches, 0 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 70 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=380, Invalid=432, Unknown=0, NotChecked=0, Total=812 [2019-11-06 18:47:18,385 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 81 states. [2019-11-06 18:47:18,391 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 81 to 80. [2019-11-06 18:47:18,391 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 80 states. [2019-11-06 18:47:18,392 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 80 states to 80 states and 81 transitions. [2019-11-06 18:47:18,393 INFO L78 Accepts]: Start accepts. Automaton has 80 states and 81 transitions. Word has length 77 [2019-11-06 18:47:18,393 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-06 18:47:18,393 INFO L462 AbstractCegarLoop]: Abstraction has 80 states and 81 transitions. [2019-11-06 18:47:18,393 INFO L463 AbstractCegarLoop]: Interpolant automaton has 29 states. [2019-11-06 18:47:18,393 INFO L276 IsEmpty]: Start isEmpty. Operand 80 states and 81 transitions. [2019-11-06 18:47:18,394 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 80 [2019-11-06 18:47:18,394 INFO L402 BasicCegarLoop]: Found error trace [2019-11-06 18:47:18,394 INFO L410 BasicCegarLoop]: trace histogram [25, 25, 9, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-06 18:47:18,600 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 24 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:47:18,600 INFO L410 AbstractCegarLoop]: === Iteration 27 === [mainErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-06 18:47:18,600 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-06 18:47:18,600 INFO L82 PathProgramCache]: Analyzing trace with hash -1273627745, now seen corresponding path program 24 times [2019-11-06 18:47:18,600 INFO L161 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-06 18:47:18,601 INFO L337 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1202736329] [2019-11-06 18:47:18,601 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-06 18:47:18,620 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:47:18,958 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:47:18,964 INFO L134 CoverageAnalysis]: Checked inductivity of 697 backedges. 0 proven. 625 refuted. 0 times theorem prover too weak. 72 trivial. 0 not checked. [2019-11-06 18:47:18,965 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1202736329] [2019-11-06 18:47:18,965 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [958220344] [2019-11-06 18:47:18,965 INFO L92 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 25 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 25 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:47:19,639 INFO L249 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 17 check-sat command(s) [2019-11-06 18:47:19,639 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-06 18:47:19,642 INFO L256 TraceCheckSpWp]: Trace formula consists of 214 conjuncts, 52 conjunts are in the unsatisfiable core [2019-11-06 18:47:19,644 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2019-11-06 18:47:19,664 INFO L375 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2019-11-06 18:47:19,665 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-06 18:47:19,677 INFO L567 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-06 18:47:19,677 INFO L496 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2019-11-06 18:47:19,678 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:22, output treesize:18 [2019-11-06 18:47:20,929 WARN L191 SmtUtils]: Spent 237.00 ms on a formula simplification. DAG size of input: 173 DAG size of output: 89 [2019-11-06 18:47:20,930 INFO L341 Elim1Store]: treesize reduction 240, result has 46.5 percent of original size [2019-11-06 18:47:20,930 INFO L375 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 9 select indices, 9 select index equivalence classes, 0 disjoint index pairs (out of 36 index pairs), introduced 9 new quantified variables, introduced 36 case distinctions, treesize of input 91 treesize of output 243 [2019-11-06 18:47:20,932 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:20,933 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:20,933 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:20,934 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:20,934 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:20,935 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:20,935 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:20,935 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:20,936 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:20,936 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:20,937 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:20,937 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:20,937 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:20,938 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:20,939 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-06 18:47:21,025 INFO L567 ElimStorePlain]: treesize reduction 149, result has 37.9 percent of original size [2019-11-06 18:47:21,026 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:21,027 INFO L496 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2019-11-06 18:47:21,028 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 3 variables, input treesize:97, output treesize:91 [2019-11-06 18:47:21,028 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:21,110 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:21,191 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:21,659 INFO L134 CoverageAnalysis]: Checked inductivity of 697 backedges. 0 proven. 72 refuted. 0 times theorem prover too weak. 625 trivial. 0 not checked. [2019-11-06 18:47:21,660 INFO L218 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-06 18:47:21,660 INFO L231 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [29, 21] total 48 [2019-11-06 18:47:21,660 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [9653381] [2019-11-06 18:47:21,661 INFO L442 AbstractCegarLoop]: Interpolant automaton has 48 states [2019-11-06 18:47:21,661 INFO L141 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-06 18:47:21,661 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 48 interpolants. [2019-11-06 18:47:21,661 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=442, Invalid=1814, Unknown=0, NotChecked=0, Total=2256 [2019-11-06 18:47:21,662 INFO L87 Difference]: Start difference. First operand 80 states and 81 transitions. Second operand 48 states. [2019-11-06 18:47:22,726 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-06 18:47:22,726 INFO L93 Difference]: Finished difference Result 109 states and 112 transitions. [2019-11-06 18:47:22,727 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 48 states. [2019-11-06 18:47:22,727 INFO L78 Accepts]: Start accepts. Automaton has 48 states. Word has length 79 [2019-11-06 18:47:22,727 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-06 18:47:22,728 INFO L225 Difference]: With dead ends: 109 [2019-11-06 18:47:22,728 INFO L226 Difference]: Without dead ends: 85 [2019-11-06 18:47:22,730 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 110 GetRequests, 62 SyntacticMatches, 0 SemanticMatches, 48 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 595 ImplicationChecksByTransitivity, 1.7s TimeCoverageRelationStatistics Valid=452, Invalid=1998, Unknown=0, NotChecked=0, Total=2450 [2019-11-06 18:47:22,731 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 85 states. [2019-11-06 18:47:22,735 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 85 to 84. [2019-11-06 18:47:22,735 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 84 states. [2019-11-06 18:47:22,735 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 84 states to 84 states and 85 transitions. [2019-11-06 18:47:22,735 INFO L78 Accepts]: Start accepts. Automaton has 84 states and 85 transitions. Word has length 79 [2019-11-06 18:47:22,736 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-06 18:47:22,736 INFO L462 AbstractCegarLoop]: Abstraction has 84 states and 85 transitions. [2019-11-06 18:47:22,736 INFO L463 AbstractCegarLoop]: Interpolant automaton has 48 states. [2019-11-06 18:47:22,736 INFO L276 IsEmpty]: Start isEmpty. Operand 84 states and 85 transitions. [2019-11-06 18:47:22,737 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 84 [2019-11-06 18:47:22,737 INFO L402 BasicCegarLoop]: Found error trace [2019-11-06 18:47:22,737 INFO L410 BasicCegarLoop]: trace histogram [26, 26, 10, 9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-06 18:47:22,941 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 25 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:47:22,942 INFO L410 AbstractCegarLoop]: === Iteration 28 === [mainErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-06 18:47:22,942 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-06 18:47:22,942 INFO L82 PathProgramCache]: Analyzing trace with hash 1438388992, now seen corresponding path program 25 times [2019-11-06 18:47:22,942 INFO L161 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-06 18:47:22,943 INFO L337 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1903996184] [2019-11-06 18:47:22,943 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-06 18:47:22,961 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:47:23,298 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:47:23,305 INFO L134 CoverageAnalysis]: Checked inductivity of 766 backedges. 0 proven. 676 refuted. 0 times theorem prover too weak. 90 trivial. 0 not checked. [2019-11-06 18:47:23,306 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1903996184] [2019-11-06 18:47:23,306 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [994097520] [2019-11-06 18:47:23,306 INFO L92 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 26 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 26 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:47:23,433 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:47:23,435 INFO L256 TraceCheckSpWp]: Trace formula consists of 279 conjuncts, 28 conjunts are in the unsatisfiable core [2019-11-06 18:47:23,436 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2019-11-06 18:47:23,453 INFO L134 CoverageAnalysis]: Checked inductivity of 766 backedges. 0 proven. 676 refuted. 0 times theorem prover too weak. 90 trivial. 0 not checked. [2019-11-06 18:47:23,453 INFO L218 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-06 18:47:23,453 INFO L231 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [30, 29] total 31 [2019-11-06 18:47:23,453 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [143608256] [2019-11-06 18:47:23,454 INFO L442 AbstractCegarLoop]: Interpolant automaton has 31 states [2019-11-06 18:47:23,454 INFO L141 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-06 18:47:23,454 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2019-11-06 18:47:23,455 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=437, Invalid=493, Unknown=0, NotChecked=0, Total=930 [2019-11-06 18:47:23,455 INFO L87 Difference]: Start difference. First operand 84 states and 85 transitions. Second operand 31 states. [2019-11-06 18:47:23,625 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-06 18:47:23,625 INFO L93 Difference]: Finished difference Result 112 states and 114 transitions. [2019-11-06 18:47:23,625 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2019-11-06 18:47:23,626 INFO L78 Accepts]: Start accepts. Automaton has 31 states. Word has length 83 [2019-11-06 18:47:23,626 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-06 18:47:23,627 INFO L225 Difference]: With dead ends: 112 [2019-11-06 18:47:23,627 INFO L226 Difference]: Without dead ends: 87 [2019-11-06 18:47:23,628 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 113 GetRequests, 84 SyntacticMatches, 0 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 76 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=437, Invalid=493, Unknown=0, NotChecked=0, Total=930 [2019-11-06 18:47:23,628 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 87 states. [2019-11-06 18:47:23,632 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 87 to 86. [2019-11-06 18:47:23,632 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 86 states. [2019-11-06 18:47:23,632 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 86 states to 86 states and 87 transitions. [2019-11-06 18:47:23,633 INFO L78 Accepts]: Start accepts. Automaton has 86 states and 87 transitions. Word has length 83 [2019-11-06 18:47:23,633 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-06 18:47:23,633 INFO L462 AbstractCegarLoop]: Abstraction has 86 states and 87 transitions. [2019-11-06 18:47:23,633 INFO L463 AbstractCegarLoop]: Interpolant automaton has 31 states. [2019-11-06 18:47:23,633 INFO L276 IsEmpty]: Start isEmpty. Operand 86 states and 87 transitions. [2019-11-06 18:47:23,634 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 86 [2019-11-06 18:47:23,634 INFO L402 BasicCegarLoop]: Found error trace [2019-11-06 18:47:23,634 INFO L410 BasicCegarLoop]: trace histogram [27, 27, 10, 9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-06 18:47:23,837 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 26 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:47:23,838 INFO L410 AbstractCegarLoop]: === Iteration 29 === [mainErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-06 18:47:23,838 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-06 18:47:23,838 INFO L82 PathProgramCache]: Analyzing trace with hash 687469406, now seen corresponding path program 26 times [2019-11-06 18:47:23,839 INFO L161 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-06 18:47:23,839 INFO L337 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2050169431] [2019-11-06 18:47:23,839 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-06 18:47:23,857 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:47:24,243 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:47:24,250 INFO L134 CoverageAnalysis]: Checked inductivity of 819 backedges. 0 proven. 729 refuted. 0 times theorem prover too weak. 90 trivial. 0 not checked. [2019-11-06 18:47:24,250 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2050169431] [2019-11-06 18:47:24,250 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [718424973] [2019-11-06 18:47:24,250 INFO L92 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 27 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 27 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:47:24,386 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2019-11-06 18:47:24,387 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-06 18:47:24,388 INFO L256 TraceCheckSpWp]: Trace formula consists of 285 conjuncts, 29 conjunts are in the unsatisfiable core [2019-11-06 18:47:24,389 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2019-11-06 18:47:24,406 INFO L134 CoverageAnalysis]: Checked inductivity of 819 backedges. 0 proven. 729 refuted. 0 times theorem prover too weak. 90 trivial. 0 not checked. [2019-11-06 18:47:24,406 INFO L218 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-06 18:47:24,406 INFO L231 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [31, 30] total 32 [2019-11-06 18:47:24,406 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1967659149] [2019-11-06 18:47:24,407 INFO L442 AbstractCegarLoop]: Interpolant automaton has 32 states [2019-11-06 18:47:24,407 INFO L141 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-06 18:47:24,407 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2019-11-06 18:47:24,408 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=467, Invalid=525, Unknown=0, NotChecked=0, Total=992 [2019-11-06 18:47:24,408 INFO L87 Difference]: Start difference. First operand 86 states and 87 transitions. Second operand 32 states. [2019-11-06 18:47:24,564 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-06 18:47:24,564 INFO L93 Difference]: Finished difference Result 114 states and 116 transitions. [2019-11-06 18:47:24,564 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 31 states. [2019-11-06 18:47:24,564 INFO L78 Accepts]: Start accepts. Automaton has 32 states. Word has length 85 [2019-11-06 18:47:24,564 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-06 18:47:24,565 INFO L225 Difference]: With dead ends: 114 [2019-11-06 18:47:24,565 INFO L226 Difference]: Without dead ends: 89 [2019-11-06 18:47:24,566 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 116 GetRequests, 86 SyntacticMatches, 0 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 79 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=467, Invalid=525, Unknown=0, NotChecked=0, Total=992 [2019-11-06 18:47:24,567 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 89 states. [2019-11-06 18:47:24,570 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 89 to 88. [2019-11-06 18:47:24,570 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 88 states. [2019-11-06 18:47:24,570 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 88 states to 88 states and 89 transitions. [2019-11-06 18:47:24,571 INFO L78 Accepts]: Start accepts. Automaton has 88 states and 89 transitions. Word has length 85 [2019-11-06 18:47:24,571 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-06 18:47:24,571 INFO L462 AbstractCegarLoop]: Abstraction has 88 states and 89 transitions. [2019-11-06 18:47:24,571 INFO L463 AbstractCegarLoop]: Interpolant automaton has 32 states. [2019-11-06 18:47:24,571 INFO L276 IsEmpty]: Start isEmpty. Operand 88 states and 89 transitions. [2019-11-06 18:47:24,572 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2019-11-06 18:47:24,572 INFO L402 BasicCegarLoop]: Found error trace [2019-11-06 18:47:24,572 INFO L410 BasicCegarLoop]: trace histogram [28, 28, 10, 9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-06 18:47:24,775 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 27 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:47:24,775 INFO L410 AbstractCegarLoop]: === Iteration 30 === [mainErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-06 18:47:24,776 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-06 18:47:24,776 INFO L82 PathProgramCache]: Analyzing trace with hash 608252988, now seen corresponding path program 27 times [2019-11-06 18:47:24,776 INFO L161 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-06 18:47:24,777 INFO L337 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [464804509] [2019-11-06 18:47:24,777 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-06 18:47:24,796 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:47:25,216 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:47:25,224 INFO L134 CoverageAnalysis]: Checked inductivity of 874 backedges. 0 proven. 784 refuted. 0 times theorem prover too weak. 90 trivial. 0 not checked. [2019-11-06 18:47:25,224 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [464804509] [2019-11-06 18:47:25,225 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [538377441] [2019-11-06 18:47:25,225 INFO L92 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 28 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 28 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:47:25,388 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 10 check-sat command(s) [2019-11-06 18:47:25,388 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-06 18:47:25,390 INFO L256 TraceCheckSpWp]: Trace formula consists of 177 conjuncts, 65 conjunts are in the unsatisfiable core [2019-11-06 18:47:25,391 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2019-11-06 18:47:25,441 INFO L375 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2019-11-06 18:47:25,441 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-06 18:47:25,450 INFO L567 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-06 18:47:25,450 INFO L496 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2019-11-06 18:47:25,451 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:25, output treesize:21 [2019-11-06 18:47:26,499 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-06 18:47:26,501 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-06 18:47:26,503 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-06 18:47:26,505 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-06 18:47:26,512 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-06 18:47:26,513 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-06 18:47:26,514 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-06 18:47:26,516 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-06 18:47:26,565 INFO L341 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2019-11-06 18:47:26,566 INFO L375 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 10 select indices, 10 select index equivalence classes, 36 disjoint index pairs (out of 45 index pairs), introduced 10 new quantified variables, introduced 45 case distinctions, treesize of input 83 treesize of output 131 [2019-11-06 18:47:26,567 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:26,567 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:26,568 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:26,569 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:26,569 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:26,570 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:26,570 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:26,570 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:26,571 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-06 18:47:26,599 INFO L567 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-06 18:47:26,599 INFO L496 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2019-11-06 18:47:26,600 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 2 variables, input treesize:89, output treesize:67 [2019-11-06 18:47:26,672 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:26,743 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-06 18:47:27,880 INFO L134 CoverageAnalysis]: Checked inductivity of 874 backedges. 0 proven. 198 refuted. 0 times theorem prover too weak. 676 trivial. 0 not checked. [2019-11-06 18:47:27,881 INFO L218 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-06 18:47:27,881 INFO L231 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [32, 26] total 56 [2019-11-06 18:47:27,881 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1723450788] [2019-11-06 18:47:27,881 INFO L442 AbstractCegarLoop]: Interpolant automaton has 56 states [2019-11-06 18:47:27,882 INFO L141 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-06 18:47:27,882 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 56 interpolants. [2019-11-06 18:47:27,883 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=617, Invalid=2463, Unknown=0, NotChecked=0, Total=3080 [2019-11-06 18:47:27,883 INFO L87 Difference]: Start difference. First operand 88 states and 89 transitions. Second operand 56 states. [2019-11-06 18:47:29,636 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-06 18:47:29,636 INFO L93 Difference]: Finished difference Result 119 states and 122 transitions. [2019-11-06 18:47:29,636 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 54 states. [2019-11-06 18:47:29,637 INFO L78 Accepts]: Start accepts. Automaton has 56 states. Word has length 87 [2019-11-06 18:47:29,637 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-06 18:47:29,638 INFO L225 Difference]: With dead ends: 119 [2019-11-06 18:47:29,638 INFO L226 Difference]: Without dead ends: 93 [2019-11-06 18:47:29,641 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 149 GetRequests, 65 SyntacticMatches, 0 SemanticMatches, 84 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1916 ImplicationChecksByTransitivity, 2.4s TimeCoverageRelationStatistics Valid=1499, Invalid=5811, Unknown=0, NotChecked=0, Total=7310 [2019-11-06 18:47:29,641 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 93 states. [2019-11-06 18:47:29,644 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 93 to 92. [2019-11-06 18:47:29,644 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 92 states. [2019-11-06 18:47:29,645 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 92 states to 92 states and 93 transitions. [2019-11-06 18:47:29,645 INFO L78 Accepts]: Start accepts. Automaton has 92 states and 93 transitions. Word has length 87 [2019-11-06 18:47:29,645 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-06 18:47:29,645 INFO L462 AbstractCegarLoop]: Abstraction has 92 states and 93 transitions. [2019-11-06 18:47:29,645 INFO L463 AbstractCegarLoop]: Interpolant automaton has 56 states. [2019-11-06 18:47:29,646 INFO L276 IsEmpty]: Start isEmpty. Operand 92 states and 93 transitions. [2019-11-06 18:47:29,646 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 92 [2019-11-06 18:47:29,646 INFO L402 BasicCegarLoop]: Found error trace [2019-11-06 18:47:29,646 INFO L410 BasicCegarLoop]: trace histogram [29, 29, 11, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-06 18:47:29,850 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 28 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:47:29,850 INFO L410 AbstractCegarLoop]: === Iteration 31 === [mainErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-06 18:47:29,851 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-06 18:47:29,851 INFO L82 PathProgramCache]: Analyzing trace with hash -1434133923, now seen corresponding path program 28 times [2019-11-06 18:47:29,851 INFO L161 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-06 18:47:29,851 INFO L337 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1391646201] [2019-11-06 18:47:29,852 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-06 18:47:29,872 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:47:30,478 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:47:30,492 INFO L134 CoverageAnalysis]: Checked inductivity of 951 backedges. 0 proven. 841 refuted. 0 times theorem prover too weak. 110 trivial. 0 not checked. [2019-11-06 18:47:30,492 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1391646201] [2019-11-06 18:47:30,492 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1038369235] [2019-11-06 18:47:30,492 INFO L92 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 29 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 29 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:47:30,763 INFO L249 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2019-11-06 18:47:30,764 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-06 18:47:30,765 INFO L256 TraceCheckSpWp]: Trace formula consists of 302 conjuncts, 31 conjunts are in the unsatisfiable core [2019-11-06 18:47:30,768 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2019-11-06 18:47:30,850 INFO L134 CoverageAnalysis]: Checked inductivity of 951 backedges. 0 proven. 841 refuted. 0 times theorem prover too weak. 110 trivial. 0 not checked. [2019-11-06 18:47:30,850 INFO L218 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-06 18:47:30,851 INFO L231 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [33, 32] total 34 [2019-11-06 18:47:30,851 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1551247524] [2019-11-06 18:47:30,852 INFO L442 AbstractCegarLoop]: Interpolant automaton has 34 states [2019-11-06 18:47:30,852 INFO L141 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-06 18:47:30,853 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 34 interpolants. [2019-11-06 18:47:30,854 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=530, Invalid=592, Unknown=0, NotChecked=0, Total=1122 [2019-11-06 18:47:30,854 INFO L87 Difference]: Start difference. First operand 92 states and 93 transitions. Second operand 34 states. [2019-11-06 18:47:31,025 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-06 18:47:31,025 INFO L93 Difference]: Finished difference Result 122 states and 124 transitions. [2019-11-06 18:47:31,025 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2019-11-06 18:47:31,025 INFO L78 Accepts]: Start accepts. Automaton has 34 states. Word has length 91 [2019-11-06 18:47:31,026 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-06 18:47:31,026 INFO L225 Difference]: With dead ends: 122 [2019-11-06 18:47:31,026 INFO L226 Difference]: Without dead ends: 95 [2019-11-06 18:47:31,027 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 124 GetRequests, 92 SyntacticMatches, 0 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 85 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=530, Invalid=592, Unknown=0, NotChecked=0, Total=1122 [2019-11-06 18:47:31,027 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 95 states. [2019-11-06 18:47:31,031 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 95 to 94. [2019-11-06 18:47:31,032 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 94 states. [2019-11-06 18:47:31,032 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 94 states to 94 states and 95 transitions. [2019-11-06 18:47:31,032 INFO L78 Accepts]: Start accepts. Automaton has 94 states and 95 transitions. Word has length 91 [2019-11-06 18:47:31,033 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-06 18:47:31,033 INFO L462 AbstractCegarLoop]: Abstraction has 94 states and 95 transitions. [2019-11-06 18:47:31,033 INFO L463 AbstractCegarLoop]: Interpolant automaton has 34 states. [2019-11-06 18:47:31,033 INFO L276 IsEmpty]: Start isEmpty. Operand 94 states and 95 transitions. [2019-11-06 18:47:31,033 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 94 [2019-11-06 18:47:31,033 INFO L402 BasicCegarLoop]: Found error trace [2019-11-06 18:47:31,034 INFO L410 BasicCegarLoop]: trace histogram [30, 30, 11, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-06 18:47:31,234 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 29 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:47:31,234 INFO L410 AbstractCegarLoop]: === Iteration 32 === [mainErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-06 18:47:31,235 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-06 18:47:31,235 INFO L82 PathProgramCache]: Analyzing trace with hash 1124302011, now seen corresponding path program 29 times [2019-11-06 18:47:31,235 INFO L161 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-06 18:47:31,236 INFO L337 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [894064244] [2019-11-06 18:47:31,236 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-06 18:47:31,257 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:47:31,716 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-06 18:47:31,725 INFO L134 CoverageAnalysis]: Checked inductivity of 1010 backedges. 0 proven. 900 refuted. 0 times theorem prover too weak. 110 trivial. 0 not checked. [2019-11-06 18:47:31,725 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [894064244] [2019-11-06 18:47:31,725 INFO L337 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2035952646] [2019-11-06 18:47:31,726 INFO L92 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 30 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 30 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:47:32,330 INFO L249 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 31 check-sat command(s) [2019-11-06 18:47:32,330 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-06 18:47:32,333 INFO L256 TraceCheckSpWp]: Trace formula consists of 308 conjuncts, 32 conjunts are in the unsatisfiable core [2019-11-06 18:47:32,335 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2019-11-06 18:47:32,355 INFO L134 CoverageAnalysis]: Checked inductivity of 1010 backedges. 0 proven. 900 refuted. 0 times theorem prover too weak. 110 trivial. 0 not checked. [2019-11-06 18:47:32,356 INFO L218 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-06 18:47:32,356 INFO L231 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [34, 33] total 35 [2019-11-06 18:47:32,356 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [253262562] [2019-11-06 18:47:32,356 INFO L442 AbstractCegarLoop]: Interpolant automaton has 35 states [2019-11-06 18:47:32,357 INFO L141 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-06 18:47:32,357 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 35 interpolants. [2019-11-06 18:47:32,357 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=563, Invalid=627, Unknown=0, NotChecked=0, Total=1190 [2019-11-06 18:47:32,357 INFO L87 Difference]: Start difference. First operand 94 states and 95 transitions. Second operand 35 states. [2019-11-06 18:47:32,539 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-06 18:47:32,540 INFO L93 Difference]: Finished difference Result 124 states and 126 transitions. [2019-11-06 18:47:32,540 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 34 states. [2019-11-06 18:47:32,540 INFO L78 Accepts]: Start accepts. Automaton has 35 states. Word has length 93 [2019-11-06 18:47:32,540 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-06 18:47:32,541 INFO L225 Difference]: With dead ends: 124 [2019-11-06 18:47:32,541 INFO L226 Difference]: Without dead ends: 97 [2019-11-06 18:47:32,542 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 127 GetRequests, 94 SyntacticMatches, 0 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 88 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=563, Invalid=627, Unknown=0, NotChecked=0, Total=1190 [2019-11-06 18:47:32,543 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 97 states. [2019-11-06 18:47:32,547 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 97 to 96. [2019-11-06 18:47:32,547 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 96 states. [2019-11-06 18:47:32,548 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 97 transitions. [2019-11-06 18:47:32,550 INFO L78 Accepts]: Start accepts. Automaton has 96 states and 97 transitions. Word has length 93 [2019-11-06 18:47:32,550 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-06 18:47:32,550 INFO L462 AbstractCegarLoop]: Abstraction has 96 states and 97 transitions. [2019-11-06 18:47:32,550 INFO L463 AbstractCegarLoop]: Interpolant automaton has 35 states. [2019-11-06 18:47:32,550 INFO L276 IsEmpty]: Start isEmpty. Operand 96 states and 97 transitions. [2019-11-06 18:47:32,551 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 96 [2019-11-06 18:47:32,551 INFO L402 BasicCegarLoop]: Found error trace [2019-11-06 18:47:32,551 INFO L410 BasicCegarLoop]: trace histogram [31, 31, 11, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-06 18:47:32,756 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 30 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-06 18:47:32,756 INFO L410 AbstractCegarLoop]: === Iteration 33 === [mainErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-06 18:47:32,757 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-06 18:47:32,757 INFO L82 PathProgramCache]: Analyzing trace with hash -1235026023, now seen corresponding path program 30 times [2019-11-06 18:47:32,757 INFO L161 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-06 18:47:32,757 INFO L337 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1881719615] [2019-11-06 18:47:32,758 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY