/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/AutomizerCInline.xml -s ../../../trunk/examples/settings/default/automizer/svcomp-Reach-32bit-Automizer_Default.epf -i ../../../trunk/examples/svcomp/array-tiling/tcpy.c -------------------------------------------------------------------------------- This is Ultimate 0.1.24-6598664 [2019-11-23 20:49:58,531 INFO L177 SettingsManager]: Resetting all preferences to default values... [2019-11-23 20:49:58,533 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2019-11-23 20:49:58,546 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2019-11-23 20:49:58,547 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2019-11-23 20:49:58,548 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2019-11-23 20:49:58,549 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2019-11-23 20:49:58,551 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2019-11-23 20:49:58,553 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2019-11-23 20:49:58,554 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2019-11-23 20:49:58,555 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2019-11-23 20:49:58,556 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2019-11-23 20:49:58,556 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2019-11-23 20:49:58,557 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2019-11-23 20:49:58,558 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2019-11-23 20:49:58,559 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2019-11-23 20:49:58,560 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2019-11-23 20:49:58,561 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2019-11-23 20:49:58,562 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2019-11-23 20:49:58,565 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2019-11-23 20:49:58,566 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2019-11-23 20:49:58,567 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2019-11-23 20:49:58,568 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2019-11-23 20:49:58,569 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2019-11-23 20:49:58,571 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2019-11-23 20:49:58,572 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2019-11-23 20:49:58,572 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2019-11-23 20:49:58,573 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2019-11-23 20:49:58,573 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2019-11-23 20:49:58,574 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2019-11-23 20:49:58,574 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2019-11-23 20:49:58,575 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2019-11-23 20:49:58,576 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2019-11-23 20:49:58,576 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2019-11-23 20:49:58,577 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2019-11-23 20:49:58,578 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2019-11-23 20:49:58,578 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2019-11-23 20:49:58,579 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2019-11-23 20:49:58,579 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2019-11-23 20:49:58,580 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2019-11-23 20:49:58,580 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2019-11-23 20:49:58,581 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-23 20:49:58,595 INFO L113 SettingsManager]: Loading preferences was successful [2019-11-23 20:49:58,596 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2019-11-23 20:49:58,597 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2019-11-23 20:49:58,597 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2019-11-23 20:49:58,597 INFO L138 SettingsManager]: * Use SBE=true [2019-11-23 20:49:58,597 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2019-11-23 20:49:58,598 INFO L138 SettingsManager]: * sizeof long=4 [2019-11-23 20:49:58,598 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2019-11-23 20:49:58,598 INFO L138 SettingsManager]: * sizeof POINTER=4 [2019-11-23 20:49:58,598 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2019-11-23 20:49:58,598 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2019-11-23 20:49:58,599 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2019-11-23 20:49:58,599 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2019-11-23 20:49:58,599 INFO L138 SettingsManager]: * Adapt memory model on pointer casts if necessary=true [2019-11-23 20:49:58,599 INFO L138 SettingsManager]: * sizeof long double=12 [2019-11-23 20:49:58,599 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2019-11-23 20:49:58,599 INFO L138 SettingsManager]: * Use constant arrays=true [2019-11-23 20:49:58,600 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2019-11-23 20:49:58,600 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2019-11-23 20:49:58,600 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2019-11-23 20:49:58,600 INFO L138 SettingsManager]: * To the following directory=./dump/ [2019-11-23 20:49:58,600 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2019-11-23 20:49:58,601 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2019-11-23 20:49:58,601 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2019-11-23 20:49:58,601 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2019-11-23 20:49:58,601 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2019-11-23 20:49:58,602 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2019-11-23 20:49:58,602 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2019-11-23 20:49:58,602 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2019-11-23 20:49:58,602 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2019-11-23 20:49:58,880 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2019-11-23 20:49:58,896 INFO L258 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2019-11-23 20:49:58,900 INFO L214 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2019-11-23 20:49:58,901 INFO L271 PluginConnector]: Initializing CDTParser... [2019-11-23 20:49:58,901 INFO L275 PluginConnector]: CDTParser initialized [2019-11-23 20:49:58,902 INFO L428 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/array-tiling/tcpy.c [2019-11-23 20:49:58,977 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/b0a3c8b2b/820a91aaaaa94a8ab43b693a0896123d/FLAG8c575eb28 [2019-11-23 20:49:59,458 INFO L306 CDTParser]: Found 1 translation units. [2019-11-23 20:49:59,459 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/array-tiling/tcpy.c [2019-11-23 20:49:59,466 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/b0a3c8b2b/820a91aaaaa94a8ab43b693a0896123d/FLAG8c575eb28 [2019-11-23 20:49:59,875 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/b0a3c8b2b/820a91aaaaa94a8ab43b693a0896123d [2019-11-23 20:49:59,883 INFO L296 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2019-11-23 20:49:59,885 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2019-11-23 20:49:59,886 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2019-11-23 20:49:59,887 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2019-11-23 20:49:59,893 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2019-11-23 20:49:59,895 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 23.11 08:49:59" (1/1) ... [2019-11-23 20:49:59,898 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@20950098 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 08:49:59, skipping insertion in model container [2019-11-23 20:49:59,898 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 23.11 08:49:59" (1/1) ... [2019-11-23 20:49:59,906 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2019-11-23 20:49:59,930 INFO L178 MainTranslator]: Built tables and reachable declarations [2019-11-23 20:50:00,133 INFO L206 PostProcessor]: Analyzing one entry point: main [2019-11-23 20:50:00,156 INFO L203 MainTranslator]: Completed pre-run [2019-11-23 20:50:00,186 INFO L206 PostProcessor]: Analyzing one entry point: main [2019-11-23 20:50:00,199 INFO L208 MainTranslator]: Completed translation [2019-11-23 20:50:00,200 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 08:50:00 WrapperNode [2019-11-23 20:50:00,200 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2019-11-23 20:50:00,200 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2019-11-23 20:50:00,200 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2019-11-23 20:50:00,200 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2019-11-23 20:50:00,291 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 08:50:00" (1/1) ... [2019-11-23 20:50:00,301 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 08:50:00" (1/1) ... [2019-11-23 20:50:00,324 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2019-11-23 20:50:00,324 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2019-11-23 20:50:00,324 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2019-11-23 20:50:00,324 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2019-11-23 20:50:00,334 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 08:50:00" (1/1) ... [2019-11-23 20:50:00,334 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 08:50:00" (1/1) ... [2019-11-23 20:50:00,336 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 08:50:00" (1/1) ... [2019-11-23 20:50:00,337 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 08:50:00" (1/1) ... [2019-11-23 20:50:00,342 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 08:50:00" (1/1) ... [2019-11-23 20:50:00,347 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 08:50:00" (1/1) ... [2019-11-23 20:50:00,349 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 08:50:00" (1/1) ... [2019-11-23 20:50:00,351 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2019-11-23 20:50:00,352 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2019-11-23 20:50:00,352 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2019-11-23 20:50:00,352 INFO L275 PluginConnector]: RCFGBuilder initialized [2019-11-23 20:50:00,359 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 08:50:00" (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-23 20:50:00,409 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2019-11-23 20:50:00,409 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2019-11-23 20:50:00,410 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2019-11-23 20:50:00,410 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2019-11-23 20:50:00,410 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2019-11-23 20:50:00,650 INFO L279 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2019-11-23 20:50:00,651 INFO L284 CfgBuilder]: Removed 9 assume(true) statements. [2019-11-23 20:50:00,652 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.11 08:50:00 BoogieIcfgContainer [2019-11-23 20:50:00,652 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2019-11-23 20:50:00,659 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2019-11-23 20:50:00,659 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2019-11-23 20:50:00,668 INFO L275 PluginConnector]: TraceAbstraction initialized [2019-11-23 20:50:00,668 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 23.11 08:49:59" (1/3) ... [2019-11-23 20:50:00,669 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3b5f1bf2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 23.11 08:50:00, skipping insertion in model container [2019-11-23 20:50:00,669 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 08:50:00" (2/3) ... [2019-11-23 20:50:00,670 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3b5f1bf2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 23.11 08:50:00, skipping insertion in model container [2019-11-23 20:50:00,670 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.11 08:50:00" (3/3) ... [2019-11-23 20:50:00,675 INFO L109 eAbstractionObserver]: Analyzing ICFG tcpy.c [2019-11-23 20:50:00,707 INFO L153 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2019-11-23 20:50:00,727 INFO L165 ceAbstractionStarter]: Appying trace abstraction to program that has 1 error locations. [2019-11-23 20:50:00,755 INFO L249 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2019-11-23 20:50:00,785 INFO L373 AbstractCegarLoop]: Interprodecural is true [2019-11-23 20:50:00,786 INFO L374 AbstractCegarLoop]: Hoare is true [2019-11-23 20:50:00,786 INFO L375 AbstractCegarLoop]: Compute interpolants for FPandBP [2019-11-23 20:50:00,786 INFO L376 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2019-11-23 20:50:00,786 INFO L377 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2019-11-23 20:50:00,786 INFO L378 AbstractCegarLoop]: Difference is false [2019-11-23 20:50:00,787 INFO L379 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2019-11-23 20:50:00,787 INFO L383 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2019-11-23 20:50:00,801 INFO L276 IsEmpty]: Start isEmpty. Operand 19 states. [2019-11-23 20:50:00,806 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2019-11-23 20:50:00,806 INFO L402 BasicCegarLoop]: Found error trace [2019-11-23 20:50:00,807 INFO L410 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-23 20:50:00,807 INFO L410 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-23 20:50:00,813 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-23 20:50:00,814 INFO L82 PathProgramCache]: Analyzing trace with hash 1901825541, now seen corresponding path program 1 times [2019-11-23 20:50:00,823 INFO L163 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-23 20:50:00,823 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1991335998] [2019-11-23 20:50:00,824 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-23 20:50:00,915 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-23 20:50:00,950 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-23 20:50:00,951 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1991335998] [2019-11-23 20:50:00,952 INFO L220 FreeRefinementEngine]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2019-11-23 20:50:00,952 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2019-11-23 20:50:00,953 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1084586385] [2019-11-23 20:50:00,958 INFO L442 AbstractCegarLoop]: Interpolant automaton has 2 states [2019-11-23 20:50:00,958 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-23 20:50:00,971 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2019-11-23 20:50:00,972 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2019-11-23 20:50:00,973 INFO L87 Difference]: Start difference. First operand 19 states. Second operand 2 states. [2019-11-23 20:50:00,987 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-23 20:50:00,987 INFO L93 Difference]: Finished difference Result 33 states and 46 transitions. [2019-11-23 20:50:00,987 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2019-11-23 20:50:00,988 INFO L78 Accepts]: Start accepts. Automaton has 2 states. Word has length 10 [2019-11-23 20:50:00,988 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-23 20:50:00,996 INFO L225 Difference]: With dead ends: 33 [2019-11-23 20:50:00,997 INFO L226 Difference]: Without dead ends: 15 [2019-11-23 20:50:00,999 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2019-11-23 20:50:01,016 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 15 states. [2019-11-23 20:50:01,027 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 15 to 15. [2019-11-23 20:50:01,028 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 15 states. [2019-11-23 20:50:01,029 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 17 transitions. [2019-11-23 20:50:01,030 INFO L78 Accepts]: Start accepts. Automaton has 15 states and 17 transitions. Word has length 10 [2019-11-23 20:50:01,031 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-23 20:50:01,031 INFO L462 AbstractCegarLoop]: Abstraction has 15 states and 17 transitions. [2019-11-23 20:50:01,031 INFO L463 AbstractCegarLoop]: Interpolant automaton has 2 states. [2019-11-23 20:50:01,031 INFO L276 IsEmpty]: Start isEmpty. Operand 15 states and 17 transitions. [2019-11-23 20:50:01,032 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2019-11-23 20:50:01,032 INFO L402 BasicCegarLoop]: Found error trace [2019-11-23 20:50:01,032 INFO L410 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-23 20:50:01,033 INFO L410 AbstractCegarLoop]: === Iteration 2 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-23 20:50:01,033 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-23 20:50:01,033 INFO L82 PathProgramCache]: Analyzing trace with hash 866229625, now seen corresponding path program 1 times [2019-11-23 20:50:01,034 INFO L163 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-23 20:50:01,034 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1615627811] [2019-11-23 20:50:01,034 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-23 20:50:01,069 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-23 20:50:01,130 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-23 20:50:01,131 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1615627811] [2019-11-23 20:50:01,131 INFO L220 FreeRefinementEngine]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2019-11-23 20:50:01,131 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2019-11-23 20:50:01,132 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [504616853] [2019-11-23 20:50:01,133 INFO L442 AbstractCegarLoop]: Interpolant automaton has 3 states [2019-11-23 20:50:01,134 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-23 20:50:01,134 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2019-11-23 20:50:01,134 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2019-11-23 20:50:01,134 INFO L87 Difference]: Start difference. First operand 15 states and 17 transitions. Second operand 3 states. [2019-11-23 20:50:01,214 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-23 20:50:01,215 INFO L93 Difference]: Finished difference Result 27 states and 31 transitions. [2019-11-23 20:50:01,216 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2019-11-23 20:50:01,216 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 10 [2019-11-23 20:50:01,216 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-23 20:50:01,217 INFO L225 Difference]: With dead ends: 27 [2019-11-23 20:50:01,217 INFO L226 Difference]: Without dead ends: 17 [2019-11-23 20:50:01,218 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 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-23 20:50:01,218 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 17 states. [2019-11-23 20:50:01,221 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 17 to 16. [2019-11-23 20:50:01,222 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 16 states. [2019-11-23 20:50:01,222 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 16 states to 16 states and 18 transitions. [2019-11-23 20:50:01,223 INFO L78 Accepts]: Start accepts. Automaton has 16 states and 18 transitions. Word has length 10 [2019-11-23 20:50:01,223 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-23 20:50:01,223 INFO L462 AbstractCegarLoop]: Abstraction has 16 states and 18 transitions. [2019-11-23 20:50:01,223 INFO L463 AbstractCegarLoop]: Interpolant automaton has 3 states. [2019-11-23 20:50:01,223 INFO L276 IsEmpty]: Start isEmpty. Operand 16 states and 18 transitions. [2019-11-23 20:50:01,224 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2019-11-23 20:50:01,224 INFO L402 BasicCegarLoop]: Found error trace [2019-11-23 20:50:01,224 INFO L410 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-23 20:50:01,224 INFO L410 AbstractCegarLoop]: === Iteration 3 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-23 20:50:01,224 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-23 20:50:01,225 INFO L82 PathProgramCache]: Analyzing trace with hash -365620713, now seen corresponding path program 1 times [2019-11-23 20:50:01,225 INFO L163 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-23 20:50:01,225 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [820180705] [2019-11-23 20:50:01,225 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-23 20:50:01,251 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-23 20:50:01,320 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-23 20:50:01,321 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [820180705] [2019-11-23 20:50:01,321 INFO L220 FreeRefinementEngine]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2019-11-23 20:50:01,321 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2019-11-23 20:50:01,321 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [329293698] [2019-11-23 20:50:01,322 INFO L442 AbstractCegarLoop]: Interpolant automaton has 4 states [2019-11-23 20:50:01,322 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-23 20:50:01,322 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2019-11-23 20:50:01,323 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2019-11-23 20:50:01,323 INFO L87 Difference]: Start difference. First operand 16 states and 18 transitions. Second operand 4 states. [2019-11-23 20:50:01,379 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-23 20:50:01,379 INFO L93 Difference]: Finished difference Result 32 states and 35 transitions. [2019-11-23 20:50:01,379 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2019-11-23 20:50:01,380 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 12 [2019-11-23 20:50:01,380 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-23 20:50:01,380 INFO L225 Difference]: With dead ends: 32 [2019-11-23 20:50:01,381 INFO L226 Difference]: Without dead ends: 25 [2019-11-23 20:50:01,381 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2019-11-23 20:50:01,381 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states. [2019-11-23 20:50:01,385 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 17. [2019-11-23 20:50:01,385 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 17 states. [2019-11-23 20:50:01,386 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 17 states to 17 states and 19 transitions. [2019-11-23 20:50:01,386 INFO L78 Accepts]: Start accepts. Automaton has 17 states and 19 transitions. Word has length 12 [2019-11-23 20:50:01,386 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-23 20:50:01,386 INFO L462 AbstractCegarLoop]: Abstraction has 17 states and 19 transitions. [2019-11-23 20:50:01,387 INFO L463 AbstractCegarLoop]: Interpolant automaton has 4 states. [2019-11-23 20:50:01,387 INFO L276 IsEmpty]: Start isEmpty. Operand 17 states and 19 transitions. [2019-11-23 20:50:01,387 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2019-11-23 20:50:01,387 INFO L402 BasicCegarLoop]: Found error trace [2019-11-23 20:50:01,388 INFO L410 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-23 20:50:01,388 INFO L410 AbstractCegarLoop]: === Iteration 4 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-23 20:50:01,388 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-23 20:50:01,388 INFO L82 PathProgramCache]: Analyzing trace with hash -1823770763, now seen corresponding path program 1 times [2019-11-23 20:50:01,389 INFO L163 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-23 20:50:01,389 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1632354494] [2019-11-23 20:50:01,389 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-23 20:50:01,435 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-23 20:50:01,481 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2019-11-23 20:50:01,482 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1632354494] [2019-11-23 20:50:01,482 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [924461859] [2019-11-23 20:50:01,482 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-23 20:50:01,561 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-23 20:50:01,563 INFO L255 TraceCheckSpWp]: Trace formula consists of 73 conjuncts, 4 conjunts are in the unsatisfiable core [2019-11-23 20:50:01,571 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2019-11-23 20:50:01,622 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2019-11-23 20:50:01,622 INFO L220 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-23 20:50:01,623 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 6 [2019-11-23 20:50:01,623 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2132634708] [2019-11-23 20:50:01,623 INFO L442 AbstractCegarLoop]: Interpolant automaton has 6 states [2019-11-23 20:50:01,624 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-23 20:50:01,624 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2019-11-23 20:50:01,624 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=15, Unknown=0, NotChecked=0, Total=30 [2019-11-23 20:50:01,625 INFO L87 Difference]: Start difference. First operand 17 states and 19 transitions. Second operand 6 states. [2019-11-23 20:50:01,690 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-23 20:50:01,690 INFO L93 Difference]: Finished difference Result 31 states and 35 transitions. [2019-11-23 20:50:01,691 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2019-11-23 20:50:01,691 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 14 [2019-11-23 20:50:01,691 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-23 20:50:01,692 INFO L225 Difference]: With dead ends: 31 [2019-11-23 20:50:01,692 INFO L226 Difference]: Without dead ends: 20 [2019-11-23 20:50:01,693 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 13 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=15, Unknown=0, NotChecked=0, Total=30 [2019-11-23 20:50:01,693 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 20 states. [2019-11-23 20:50:01,697 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 20 to 19. [2019-11-23 20:50:01,697 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 19 states. [2019-11-23 20:50:01,698 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 19 states to 19 states and 21 transitions. [2019-11-23 20:50:01,698 INFO L78 Accepts]: Start accepts. Automaton has 19 states and 21 transitions. Word has length 14 [2019-11-23 20:50:01,698 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-23 20:50:01,698 INFO L462 AbstractCegarLoop]: Abstraction has 19 states and 21 transitions. [2019-11-23 20:50:01,698 INFO L463 AbstractCegarLoop]: Interpolant automaton has 6 states. [2019-11-23 20:50:01,698 INFO L276 IsEmpty]: Start isEmpty. Operand 19 states and 21 transitions. [2019-11-23 20:50:01,699 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2019-11-23 20:50:01,699 INFO L402 BasicCegarLoop]: Found error trace [2019-11-23 20:50:01,699 INFO L410 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-23 20:50:01,903 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-23 20:50:01,904 INFO L410 AbstractCegarLoop]: === Iteration 5 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-23 20:50:01,904 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-23 20:50:01,905 INFO L82 PathProgramCache]: Analyzing trace with hash 867659027, now seen corresponding path program 2 times [2019-11-23 20:50:01,905 INFO L163 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-23 20:50:01,906 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [744637613] [2019-11-23 20:50:01,906 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-23 20:50:01,954 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-23 20:50:02,423 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-11-23 20:50:02,424 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [744637613] [2019-11-23 20:50:02,424 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1696335418] [2019-11-23 20:50:02,424 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-23 20:50:02,482 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2019-11-23 20:50:02,482 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-23 20:50:02,484 INFO L255 TraceCheckSpWp]: Trace formula consists of 79 conjuncts, 30 conjunts are in the unsatisfiable core [2019-11-23 20:50:02,489 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2019-11-23 20:50:02,540 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 8 [2019-11-23 20:50:02,540 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-23 20:50:02,548 INFO L567 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-23 20:50:02,548 INFO L496 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2019-11-23 20:50:02,549 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:15, output treesize:11 [2019-11-23 20:50:02,642 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:02,648 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:02,650 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:02,660 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 32 treesize of output 39 [2019-11-23 20:50:02,661 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-23 20:50:02,678 INFO L567 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-23 20:50:02,679 INFO L496 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2019-11-23 20:50:02,679 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 2 variables, input treesize:70, output treesize:48 [2019-11-23 20:50:02,782 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-23 20:50:02,806 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2019-11-23 20:50:02,806 INFO L220 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-23 20:50:02,806 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 7] total 15 [2019-11-23 20:50:02,807 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [995968136] [2019-11-23 20:50:02,807 INFO L442 AbstractCegarLoop]: Interpolant automaton has 15 states [2019-11-23 20:50:02,807 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-23 20:50:02,807 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2019-11-23 20:50:02,808 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=45, Invalid=165, Unknown=0, NotChecked=0, Total=210 [2019-11-23 20:50:02,808 INFO L87 Difference]: Start difference. First operand 19 states and 21 transitions. Second operand 15 states. [2019-11-23 20:50:03,895 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-23 20:50:03,896 INFO L93 Difference]: Finished difference Result 71 states and 80 transitions. [2019-11-23 20:50:03,896 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 29 states. [2019-11-23 20:50:03,896 INFO L78 Accepts]: Start accepts. Automaton has 15 states. Word has length 16 [2019-11-23 20:50:03,896 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-23 20:50:03,897 INFO L225 Difference]: With dead ends: 71 [2019-11-23 20:50:03,898 INFO L226 Difference]: Without dead ends: 69 [2019-11-23 20:50:03,899 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 47 GetRequests, 12 SyntacticMatches, 2 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 243 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=315, Invalid=875, Unknown=0, NotChecked=0, Total=1190 [2019-11-23 20:50:03,899 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 69 states. [2019-11-23 20:50:03,904 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 69 to 21. [2019-11-23 20:50:03,905 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 21 states. [2019-11-23 20:50:03,905 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 23 transitions. [2019-11-23 20:50:03,906 INFO L78 Accepts]: Start accepts. Automaton has 21 states and 23 transitions. Word has length 16 [2019-11-23 20:50:03,906 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-23 20:50:03,906 INFO L462 AbstractCegarLoop]: Abstraction has 21 states and 23 transitions. [2019-11-23 20:50:03,906 INFO L463 AbstractCegarLoop]: Interpolant automaton has 15 states. [2019-11-23 20:50:03,906 INFO L276 IsEmpty]: Start isEmpty. Operand 21 states and 23 transitions. [2019-11-23 20:50:03,907 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2019-11-23 20:50:03,907 INFO L402 BasicCegarLoop]: Found error trace [2019-11-23 20:50:03,907 INFO L410 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-23 20:50:04,111 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-23 20:50:04,112 INFO L410 AbstractCegarLoop]: === Iteration 6 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-23 20:50:04,112 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-23 20:50:04,113 INFO L82 PathProgramCache]: Analyzing trace with hash -1976699831, now seen corresponding path program 1 times [2019-11-23 20:50:04,113 INFO L163 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-23 20:50:04,114 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [165074644] [2019-11-23 20:50:04,114 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-23 20:50:04,150 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-23 20:50:04,635 WARN L192 SmtUtils]: Spent 124.00 ms on a formula simplification. DAG size of input: 96 DAG size of output: 38 [2019-11-23 20:50:04,790 WARN L192 SmtUtils]: Spent 126.00 ms on a formula simplification. DAG size of input: 93 DAG size of output: 43 [2019-11-23 20:50:05,157 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-11-23 20:50:05,158 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [165074644] [2019-11-23 20:50:05,158 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1781271141] [2019-11-23 20:50:05,158 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY 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-23 20:50:05,208 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-23 20:50:05,209 INFO L255 TraceCheckSpWp]: Trace formula consists of 92 conjuncts, 32 conjunts are in the unsatisfiable core [2019-11-23 20:50:05,211 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2019-11-23 20:50:05,217 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 8 [2019-11-23 20:50:05,218 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-23 20:50:05,234 INFO L567 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-23 20:50:05,235 INFO L496 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2019-11-23 20:50:05,235 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:15, output treesize:11 [2019-11-23 20:50:05,304 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 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-23 20:50:05,304 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-23 20:50:05,312 INFO L567 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-23 20:50:05,312 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-23 20:50:05,312 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 2 variables, input treesize:26, output treesize:11 [2019-11-23 20:50:05,394 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:05,439 INFO L343 Elim1Store]: treesize reduction 22, result has 61.4 percent of original size [2019-11-23 20:50:05,440 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 32 treesize of output 61 [2019-11-23 20:50:05,441 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-23 20:50:05,479 INFO L567 ElimStorePlain]: treesize reduction 26, result has 62.3 percent of original size [2019-11-23 20:50:05,480 INFO L496 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2019-11-23 20:50:05,481 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 2 variables, input treesize:65, output treesize:43 [2019-11-23 20:50:05,620 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-23 20:50:05,652 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-11-23 20:50:05,652 INFO L220 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-23 20:50:05,652 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 11] total 22 [2019-11-23 20:50:05,653 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1007368401] [2019-11-23 20:50:05,653 INFO L442 AbstractCegarLoop]: Interpolant automaton has 22 states [2019-11-23 20:50:05,653 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-23 20:50:05,654 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2019-11-23 20:50:05,654 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=59, Invalid=403, Unknown=0, NotChecked=0, Total=462 [2019-11-23 20:50:05,654 INFO L87 Difference]: Start difference. First operand 21 states and 23 transitions. Second operand 22 states. [2019-11-23 20:50:06,810 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-23 20:50:06,810 INFO L93 Difference]: Finished difference Result 55 states and 61 transitions. [2019-11-23 20:50:06,811 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2019-11-23 20:50:06,811 INFO L78 Accepts]: Start accepts. Automaton has 22 states. Word has length 20 [2019-11-23 20:50:06,812 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-23 20:50:06,812 INFO L225 Difference]: With dead ends: 55 [2019-11-23 20:50:06,812 INFO L226 Difference]: Without dead ends: 44 [2019-11-23 20:50:06,814 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 44 GetRequests, 13 SyntacticMatches, 0 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 146 ImplicationChecksByTransitivity, 1.9s TimeCoverageRelationStatistics Valid=220, Invalid=836, Unknown=0, NotChecked=0, Total=1056 [2019-11-23 20:50:06,814 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2019-11-23 20:50:06,819 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 32. [2019-11-23 20:50:06,820 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 32 states. [2019-11-23 20:50:06,820 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 35 transitions. [2019-11-23 20:50:06,821 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 35 transitions. Word has length 20 [2019-11-23 20:50:06,821 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-23 20:50:06,821 INFO L462 AbstractCegarLoop]: Abstraction has 32 states and 35 transitions. [2019-11-23 20:50:06,821 INFO L463 AbstractCegarLoop]: Interpolant automaton has 22 states. [2019-11-23 20:50:06,821 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 35 transitions. [2019-11-23 20:50:06,822 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2019-11-23 20:50:06,822 INFO L402 BasicCegarLoop]: Found error trace [2019-11-23 20:50:06,822 INFO L410 BasicCegarLoop]: trace histogram [3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-23 20:50:07,033 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 4 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-23 20:50:07,033 INFO L410 AbstractCegarLoop]: === Iteration 7 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-23 20:50:07,033 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-23 20:50:07,033 INFO L82 PathProgramCache]: Analyzing trace with hash -349783193, now seen corresponding path program 2 times [2019-11-23 20:50:07,034 INFO L163 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-23 20:50:07,034 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [155242736] [2019-11-23 20:50:07,034 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-23 20:50:07,067 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-23 20:50:07,364 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 1 proven. 9 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2019-11-23 20:50:07,365 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [155242736] [2019-11-23 20:50:07,365 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [342474837] [2019-11-23 20:50:07,365 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 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-23 20:50:07,405 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2019-11-23 20:50:07,405 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-23 20:50:07,406 INFO L255 TraceCheckSpWp]: Trace formula consists of 98 conjuncts, 9 conjunts are in the unsatisfiable core [2019-11-23 20:50:07,408 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2019-11-23 20:50:07,518 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 4 proven. 6 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2019-11-23 20:50:07,519 INFO L220 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-23 20:50:07,519 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 14 [2019-11-23 20:50:07,519 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [959865614] [2019-11-23 20:50:07,520 INFO L442 AbstractCegarLoop]: Interpolant automaton has 14 states [2019-11-23 20:50:07,520 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-23 20:50:07,520 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2019-11-23 20:50:07,520 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=47, Invalid=135, Unknown=0, NotChecked=0, Total=182 [2019-11-23 20:50:07,521 INFO L87 Difference]: Start difference. First operand 32 states and 35 transitions. Second operand 14 states. [2019-11-23 20:50:07,876 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-23 20:50:07,876 INFO L93 Difference]: Finished difference Result 57 states and 61 transitions. [2019-11-23 20:50:07,881 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2019-11-23 20:50:07,882 INFO L78 Accepts]: Start accepts. Automaton has 14 states. Word has length 22 [2019-11-23 20:50:07,882 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-23 20:50:07,882 INFO L225 Difference]: With dead ends: 57 [2019-11-23 20:50:07,883 INFO L226 Difference]: Without dead ends: 48 [2019-11-23 20:50:07,883 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 36 GetRequests, 17 SyntacticMatches, 1 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 65 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=94, Invalid=286, Unknown=0, NotChecked=0, Total=380 [2019-11-23 20:50:07,884 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2019-11-23 20:50:07,889 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 34. [2019-11-23 20:50:07,889 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 34 states. [2019-11-23 20:50:07,890 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 37 transitions. [2019-11-23 20:50:07,890 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 37 transitions. Word has length 22 [2019-11-23 20:50:07,890 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-23 20:50:07,891 INFO L462 AbstractCegarLoop]: Abstraction has 34 states and 37 transitions. [2019-11-23 20:50:07,891 INFO L463 AbstractCegarLoop]: Interpolant automaton has 14 states. [2019-11-23 20:50:07,891 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 37 transitions. [2019-11-23 20:50:07,891 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2019-11-23 20:50:07,892 INFO L402 BasicCegarLoop]: Found error trace [2019-11-23 20:50:07,892 INFO L410 BasicCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-23 20:50:08,095 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-23 20:50:08,095 INFO L410 AbstractCegarLoop]: === Iteration 8 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-23 20:50:08,096 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-23 20:50:08,096 INFO L82 PathProgramCache]: Analyzing trace with hash 654438527, now seen corresponding path program 3 times [2019-11-23 20:50:08,096 INFO L163 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-23 20:50:08,096 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1691924955] [2019-11-23 20:50:08,097 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-23 20:50:08,113 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-23 20:50:08,172 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 3 proven. 9 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2019-11-23 20:50:08,173 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1691924955] [2019-11-23 20:50:08,173 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1658876051] [2019-11-23 20:50:08,173 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 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-23 20:50:08,220 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2019-11-23 20:50:08,220 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-23 20:50:08,221 INFO L255 TraceCheckSpWp]: Trace formula consists of 105 conjuncts, 8 conjunts are in the unsatisfiable core [2019-11-23 20:50:08,222 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2019-11-23 20:50:08,280 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 8 proven. 4 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2019-11-23 20:50:08,280 INFO L220 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-23 20:50:08,280 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 13 [2019-11-23 20:50:08,281 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1790451708] [2019-11-23 20:50:08,281 INFO L442 AbstractCegarLoop]: Interpolant automaton has 13 states [2019-11-23 20:50:08,281 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-23 20:50:08,282 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2019-11-23 20:50:08,282 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=45, Invalid=111, Unknown=0, NotChecked=0, Total=156 [2019-11-23 20:50:08,282 INFO L87 Difference]: Start difference. First operand 34 states and 37 transitions. Second operand 13 states. [2019-11-23 20:50:08,436 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-23 20:50:08,437 INFO L93 Difference]: Finished difference Result 64 states and 68 transitions. [2019-11-23 20:50:08,437 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2019-11-23 20:50:08,437 INFO L78 Accepts]: Start accepts. Automaton has 13 states. Word has length 24 [2019-11-23 20:50:08,438 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-23 20:50:08,438 INFO L225 Difference]: With dead ends: 64 [2019-11-23 20:50:08,439 INFO L226 Difference]: Without dead ends: 44 [2019-11-23 20:50:08,440 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 35 GetRequests, 21 SyntacticMatches, 0 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 45 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=69, Invalid=171, Unknown=0, NotChecked=0, Total=240 [2019-11-23 20:50:08,440 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2019-11-23 20:50:08,444 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 25. [2019-11-23 20:50:08,445 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 25 states. [2019-11-23 20:50:08,446 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 25 states to 25 states and 27 transitions. [2019-11-23 20:50:08,447 INFO L78 Accepts]: Start accepts. Automaton has 25 states and 27 transitions. Word has length 24 [2019-11-23 20:50:08,447 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-23 20:50:08,447 INFO L462 AbstractCegarLoop]: Abstraction has 25 states and 27 transitions. [2019-11-23 20:50:08,447 INFO L463 AbstractCegarLoop]: Interpolant automaton has 13 states. [2019-11-23 20:50:08,447 INFO L276 IsEmpty]: Start isEmpty. Operand 25 states and 27 transitions. [2019-11-23 20:50:08,448 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2019-11-23 20:50:08,448 INFO L402 BasicCegarLoop]: Found error trace [2019-11-23 20:50:08,448 INFO L410 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-23 20:50:08,652 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-23 20:50:08,652 INFO L410 AbstractCegarLoop]: === Iteration 9 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-23 20:50:08,652 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-23 20:50:08,652 INFO L82 PathProgramCache]: Analyzing trace with hash 997106501, now seen corresponding path program 4 times [2019-11-23 20:50:08,653 INFO L163 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-23 20:50:08,653 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [161395939] [2019-11-23 20:50:08,653 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-23 20:50:08,670 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-23 20:50:08,846 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 3 proven. 10 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2019-11-23 20:50:08,847 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [161395939] [2019-11-23 20:50:08,847 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [870989464] [2019-11-23 20:50:08,847 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 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-23 20:50:08,879 INFO L249 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2019-11-23 20:50:08,879 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-23 20:50:08,880 INFO L255 TraceCheckSpWp]: Trace formula consists of 76 conjuncts, 9 conjunts are in the unsatisfiable core [2019-11-23 20:50:08,882 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2019-11-23 20:50:08,935 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 4 proven. 9 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2019-11-23 20:50:08,936 INFO L220 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-23 20:50:08,936 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 9] total 13 [2019-11-23 20:50:08,936 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2007456210] [2019-11-23 20:50:08,936 INFO L442 AbstractCegarLoop]: Interpolant automaton has 13 states [2019-11-23 20:50:08,937 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-23 20:50:08,937 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2019-11-23 20:50:08,937 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=38, Invalid=118, Unknown=0, NotChecked=0, Total=156 [2019-11-23 20:50:08,937 INFO L87 Difference]: Start difference. First operand 25 states and 27 transitions. Second operand 13 states. [2019-11-23 20:50:09,105 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-23 20:50:09,105 INFO L93 Difference]: Finished difference Result 43 states and 47 transitions. [2019-11-23 20:50:09,106 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2019-11-23 20:50:09,106 INFO L78 Accepts]: Start accepts. Automaton has 13 states. Word has length 24 [2019-11-23 20:50:09,106 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-23 20:50:09,107 INFO L225 Difference]: With dead ends: 43 [2019-11-23 20:50:09,107 INFO L226 Difference]: Without dead ends: 28 [2019-11-23 20:50:09,107 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 37 GetRequests, 21 SyntacticMatches, 2 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 37 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=66, Invalid=174, Unknown=0, NotChecked=0, Total=240 [2019-11-23 20:50:09,108 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 28 states. [2019-11-23 20:50:09,111 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 28 to 27. [2019-11-23 20:50:09,112 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 27 states. [2019-11-23 20:50:09,112 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 29 transitions. [2019-11-23 20:50:09,112 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 29 transitions. Word has length 24 [2019-11-23 20:50:09,112 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-23 20:50:09,113 INFO L462 AbstractCegarLoop]: Abstraction has 27 states and 29 transitions. [2019-11-23 20:50:09,113 INFO L463 AbstractCegarLoop]: Interpolant automaton has 13 states. [2019-11-23 20:50:09,113 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 29 transitions. [2019-11-23 20:50:09,113 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2019-11-23 20:50:09,114 INFO L402 BasicCegarLoop]: Found error trace [2019-11-23 20:50:09,114 INFO L410 BasicCegarLoop]: trace histogram [4, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-23 20:50:09,322 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-23 20:50:09,322 INFO L410 AbstractCegarLoop]: === Iteration 10 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-23 20:50:09,322 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-23 20:50:09,322 INFO L82 PathProgramCache]: Analyzing trace with hash 1448258403, now seen corresponding path program 5 times [2019-11-23 20:50:09,323 INFO L163 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-23 20:50:09,323 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [891041437] [2019-11-23 20:50:09,323 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-23 20:50:09,374 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-23 20:50:10,107 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 0 proven. 22 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-11-23 20:50:10,107 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [891041437] [2019-11-23 20:50:10,108 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1685376678] [2019-11-23 20:50:10,108 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 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-23 20:50:10,200 INFO L249 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 5 check-sat command(s) [2019-11-23 20:50:10,200 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-23 20:50:10,201 INFO L255 TraceCheckSpWp]: Trace formula consists of 108 conjuncts, 34 conjunts are in the unsatisfiable core [2019-11-23 20:50:10,203 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2019-11-23 20:50:10,220 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 8 [2019-11-23 20:50:10,221 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-23 20:50:10,226 INFO L567 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-23 20:50:10,227 INFO L496 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2019-11-23 20:50:10,227 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:15, output treesize:11 [2019-11-23 20:50:10,334 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:10,337 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:10,339 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:10,340 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 36 treesize of output 43 [2019-11-23 20:50:10,342 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-23 20:50:10,355 INFO L567 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-23 20:50:10,356 INFO L496 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2019-11-23 20:50:10,357 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 2 variables, input treesize:74, output treesize:52 [2019-11-23 20:50:10,519 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-23 20:50:10,551 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2019-11-23 20:50:10,552 INFO L220 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-23 20:50:10,552 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 9] total 23 [2019-11-23 20:50:10,552 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2065790235] [2019-11-23 20:50:10,553 INFO L442 AbstractCegarLoop]: Interpolant automaton has 23 states [2019-11-23 20:50:10,553 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-23 20:50:10,553 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2019-11-23 20:50:10,553 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=75, Invalid=431, Unknown=0, NotChecked=0, Total=506 [2019-11-23 20:50:10,554 INFO L87 Difference]: Start difference. First operand 27 states and 29 transitions. Second operand 23 states. [2019-11-23 20:50:13,860 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-23 20:50:13,860 INFO L93 Difference]: Finished difference Result 99 states and 107 transitions. [2019-11-23 20:50:13,861 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 51 states. [2019-11-23 20:50:13,861 INFO L78 Accepts]: Start accepts. Automaton has 23 states. Word has length 26 [2019-11-23 20:50:13,861 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-23 20:50:13,862 INFO L225 Difference]: With dead ends: 99 [2019-11-23 20:50:13,862 INFO L226 Difference]: Without dead ends: 97 [2019-11-23 20:50:13,864 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 85 GetRequests, 20 SyntacticMatches, 1 SemanticMatches, 64 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1093 ImplicationChecksByTransitivity, 3.6s TimeCoverageRelationStatistics Valid=846, Invalid=3444, Unknown=0, NotChecked=0, Total=4290 [2019-11-23 20:50:13,865 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 97 states. [2019-11-23 20:50:13,874 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 97 to 31. [2019-11-23 20:50:13,874 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 31 states. [2019-11-23 20:50:13,875 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 33 transitions. [2019-11-23 20:50:13,876 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 33 transitions. Word has length 26 [2019-11-23 20:50:13,876 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-23 20:50:13,877 INFO L462 AbstractCegarLoop]: Abstraction has 31 states and 33 transitions. [2019-11-23 20:50:13,877 INFO L463 AbstractCegarLoop]: Interpolant automaton has 23 states. [2019-11-23 20:50:13,877 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 33 transitions. [2019-11-23 20:50:13,877 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2019-11-23 20:50:13,878 INFO L402 BasicCegarLoop]: Found error trace [2019-11-23 20:50:13,878 INFO L410 BasicCegarLoop]: trace histogram [4, 4, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-23 20:50:14,081 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-23 20:50:14,082 INFO L410 AbstractCegarLoop]: === Iteration 11 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-23 20:50:14,083 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-23 20:50:14,083 INFO L82 PathProgramCache]: Analyzing trace with hash 1432455833, now seen corresponding path program 6 times [2019-11-23 20:50:14,083 INFO L163 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-23 20:50:14,084 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1932777365] [2019-11-23 20:50:14,084 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-23 20:50:14,131 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-23 20:50:14,950 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-11-23 20:50:14,950 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1932777365] [2019-11-23 20:50:14,951 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1772901838] [2019-11-23 20:50:14,951 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 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-23 20:50:15,021 INFO L249 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 5 check-sat command(s) [2019-11-23 20:50:15,021 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-23 20:50:15,023 INFO L255 TraceCheckSpWp]: Trace formula consists of 121 conjuncts, 46 conjunts are in the unsatisfiable core [2019-11-23 20:50:15,025 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2019-11-23 20:50:15,031 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 8 [2019-11-23 20:50:15,032 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-23 20:50:15,037 INFO L567 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-23 20:50:15,038 INFO L496 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2019-11-23 20:50:15,038 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:15, output treesize:11 [2019-11-23 20:50:15,121 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 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-23 20:50:15,121 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-23 20:50:15,128 INFO L567 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-23 20:50:15,129 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-23 20:50:15,129 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 2 variables, input treesize:26, output treesize:11 [2019-11-23 20:50:15,161 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 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-23 20:50:15,161 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-23 20:50:15,171 INFO L567 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-23 20:50:15,172 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-23 20:50:15,172 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 2 variables, input treesize:29, output treesize:14 [2019-11-23 20:50:15,316 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:15,319 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:15,334 INFO L343 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2019-11-23 20:50:15,334 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 46 treesize of output 101 [2019-11-23 20:50:15,335 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-23 20:50:15,372 INFO L567 ElimStorePlain]: treesize reduction 56, result has 52.9 percent of original size [2019-11-23 20:50:15,373 INFO L496 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2019-11-23 20:50:15,373 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:91, output treesize:63 [2019-11-23 20:50:15,487 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:15,490 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:15,492 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:15,493 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:15,494 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:15,496 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:15,497 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:15,580 INFO L343 Elim1Store]: treesize reduction 104, result has 51.6 percent of original size [2019-11-23 20:50:15,580 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 6 select indices, 6 select index equivalence classes, 7 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 4 case distinctions, treesize of input 69 treesize of output 166 [2019-11-23 20:50:15,582 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-23 20:50:15,658 INFO L567 ElimStorePlain]: treesize reduction 91, result has 47.4 percent of original size [2019-11-23 20:50:15,660 INFO L496 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2019-11-23 20:50:15,660 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 2 variables, input treesize:104, output treesize:82 [2019-11-23 20:50:15,980 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-23 20:50:16,020 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-11-23 20:50:16,020 INFO L220 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-23 20:50:16,020 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 17] total 33 [2019-11-23 20:50:16,020 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [204938702] [2019-11-23 20:50:16,021 INFO L442 AbstractCegarLoop]: Interpolant automaton has 33 states [2019-11-23 20:50:16,023 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-23 20:50:16,023 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2019-11-23 20:50:16,024 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=100, Invalid=956, Unknown=0, NotChecked=0, Total=1056 [2019-11-23 20:50:16,024 INFO L87 Difference]: Start difference. First operand 31 states and 33 transitions. Second operand 33 states. [2019-11-23 20:50:17,999 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-23 20:50:17,999 INFO L93 Difference]: Finished difference Result 76 states and 84 transitions. [2019-11-23 20:50:17,999 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2019-11-23 20:50:18,000 INFO L78 Accepts]: Start accepts. Automaton has 33 states. Word has length 30 [2019-11-23 20:50:18,000 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-23 20:50:18,001 INFO L225 Difference]: With dead ends: 76 [2019-11-23 20:50:18,001 INFO L226 Difference]: Without dead ends: 34 [2019-11-23 20:50:18,003 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 64 GetRequests, 16 SyntacticMatches, 1 SemanticMatches, 47 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 441 ImplicationChecksByTransitivity, 2.6s TimeCoverageRelationStatistics Valid=357, Invalid=1995, Unknown=0, NotChecked=0, Total=2352 [2019-11-23 20:50:18,003 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 34 states. [2019-11-23 20:50:18,008 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 34 to 33. [2019-11-23 20:50:18,008 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 33 states. [2019-11-23 20:50:18,009 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 35 transitions. [2019-11-23 20:50:18,009 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 35 transitions. Word has length 30 [2019-11-23 20:50:18,009 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-23 20:50:18,009 INFO L462 AbstractCegarLoop]: Abstraction has 33 states and 35 transitions. [2019-11-23 20:50:18,010 INFO L463 AbstractCegarLoop]: Interpolant automaton has 33 states. [2019-11-23 20:50:18,010 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 35 transitions. [2019-11-23 20:50:18,010 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2019-11-23 20:50:18,011 INFO L402 BasicCegarLoop]: Found error trace [2019-11-23 20:50:18,011 INFO L410 BasicCegarLoop]: trace histogram [5, 5, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-23 20:50:18,213 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-23 20:50:18,214 INFO L410 AbstractCegarLoop]: === Iteration 12 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-23 20:50:18,214 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-23 20:50:18,214 INFO L82 PathProgramCache]: Analyzing trace with hash 437945399, now seen corresponding path program 7 times [2019-11-23 20:50:18,214 INFO L163 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-23 20:50:18,215 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1497128667] [2019-11-23 20:50:18,215 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-23 20:50:18,232 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-23 20:50:18,597 INFO L134 CoverageAnalysis]: Checked inductivity of 37 backedges. 9 proven. 20 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2019-11-23 20:50:18,598 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1497128667] [2019-11-23 20:50:18,598 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2113269110] [2019-11-23 20:50:18,598 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 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-23 20:50:18,655 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-23 20:50:18,656 INFO L255 TraceCheckSpWp]: Trace formula consists of 127 conjuncts, 12 conjunts are in the unsatisfiable core [2019-11-23 20:50:18,659 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2019-11-23 20:50:18,859 INFO L134 CoverageAnalysis]: Checked inductivity of 37 backedges. 16 proven. 13 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2019-11-23 20:50:18,859 INFO L220 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-23 20:50:18,859 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 20 [2019-11-23 20:50:18,859 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [183735658] [2019-11-23 20:50:18,860 INFO L442 AbstractCegarLoop]: Interpolant automaton has 20 states [2019-11-23 20:50:18,860 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-23 20:50:18,860 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2019-11-23 20:50:18,861 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=88, Invalid=292, Unknown=0, NotChecked=0, Total=380 [2019-11-23 20:50:18,861 INFO L87 Difference]: Start difference. First operand 33 states and 35 transitions. Second operand 20 states. [2019-11-23 20:50:19,294 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-23 20:50:19,294 INFO L93 Difference]: Finished difference Result 66 states and 70 transitions. [2019-11-23 20:50:19,295 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2019-11-23 20:50:19,295 INFO L78 Accepts]: Start accepts. Automaton has 20 states. Word has length 32 [2019-11-23 20:50:19,295 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-23 20:50:19,296 INFO L225 Difference]: With dead ends: 66 [2019-11-23 20:50:19,296 INFO L226 Difference]: Without dead ends: 53 [2019-11-23 20:50:19,297 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 51 GetRequests, 24 SyntacticMatches, 1 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 163 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=172, Invalid=584, Unknown=0, NotChecked=0, Total=756 [2019-11-23 20:50:19,297 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 53 states. [2019-11-23 20:50:19,302 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 53 to 35. [2019-11-23 20:50:19,302 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 35 states. [2019-11-23 20:50:19,302 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 37 transitions. [2019-11-23 20:50:19,302 INFO L78 Accepts]: Start accepts. Automaton has 35 states and 37 transitions. Word has length 32 [2019-11-23 20:50:19,303 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-23 20:50:19,303 INFO L462 AbstractCegarLoop]: Abstraction has 35 states and 37 transitions. [2019-11-23 20:50:19,303 INFO L463 AbstractCegarLoop]: Interpolant automaton has 20 states. [2019-11-23 20:50:19,303 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 37 transitions. [2019-11-23 20:50:19,304 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2019-11-23 20:50:19,304 INFO L402 BasicCegarLoop]: Found error trace [2019-11-23 20:50:19,304 INFO L410 BasicCegarLoop]: trace histogram [5, 5, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-23 20:50:19,507 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-23 20:50:19,507 INFO L410 AbstractCegarLoop]: === Iteration 13 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-23 20:50:19,508 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-23 20:50:19,508 INFO L82 PathProgramCache]: Analyzing trace with hash 2002439829, now seen corresponding path program 8 times [2019-11-23 20:50:19,508 INFO L163 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-23 20:50:19,508 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [669084609] [2019-11-23 20:50:19,509 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-23 20:50:19,523 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-23 20:50:19,726 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 6 proven. 28 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2019-11-23 20:50:19,726 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [669084609] [2019-11-23 20:50:19,726 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [789002203] [2019-11-23 20:50:19,726 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 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-23 20:50:19,804 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2019-11-23 20:50:19,804 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-23 20:50:19,805 INFO L255 TraceCheckSpWp]: Trace formula consists of 131 conjuncts, 12 conjunts are in the unsatisfiable core [2019-11-23 20:50:19,807 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2019-11-23 20:50:19,914 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 9 proven. 25 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2019-11-23 20:50:19,914 INFO L220 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-23 20:50:19,915 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 12] total 17 [2019-11-23 20:50:19,915 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1380865967] [2019-11-23 20:50:19,915 INFO L442 AbstractCegarLoop]: Interpolant automaton has 17 states [2019-11-23 20:50:19,915 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-23 20:50:19,916 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2019-11-23 20:50:19,916 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=63, Invalid=209, Unknown=0, NotChecked=0, Total=272 [2019-11-23 20:50:19,916 INFO L87 Difference]: Start difference. First operand 35 states and 37 transitions. Second operand 17 states. [2019-11-23 20:50:20,087 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-23 20:50:20,088 INFO L93 Difference]: Finished difference Result 59 states and 63 transitions. [2019-11-23 20:50:20,088 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2019-11-23 20:50:20,088 INFO L78 Accepts]: Start accepts. Automaton has 17 states. Word has length 34 [2019-11-23 20:50:20,088 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-23 20:50:20,089 INFO L225 Difference]: With dead ends: 59 [2019-11-23 20:50:20,089 INFO L226 Difference]: Without dead ends: 38 [2019-11-23 20:50:20,090 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 51 GetRequests, 30 SyntacticMatches, 2 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 78 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=109, Invalid=311, Unknown=0, NotChecked=0, Total=420 [2019-11-23 20:50:20,090 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 38 states. [2019-11-23 20:50:20,095 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 38 to 37. [2019-11-23 20:50:20,096 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 37 states. [2019-11-23 20:50:20,096 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 39 transitions. [2019-11-23 20:50:20,096 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 39 transitions. Word has length 34 [2019-11-23 20:50:20,097 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-23 20:50:20,097 INFO L462 AbstractCegarLoop]: Abstraction has 37 states and 39 transitions. [2019-11-23 20:50:20,097 INFO L463 AbstractCegarLoop]: Interpolant automaton has 17 states. [2019-11-23 20:50:20,097 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 39 transitions. [2019-11-23 20:50:20,098 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2019-11-23 20:50:20,098 INFO L402 BasicCegarLoop]: Found error trace [2019-11-23 20:50:20,098 INFO L410 BasicCegarLoop]: trace histogram [6, 6, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-23 20:50:20,301 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-23 20:50:20,302 INFO L410 AbstractCegarLoop]: === Iteration 14 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-23 20:50:20,302 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-23 20:50:20,302 INFO L82 PathProgramCache]: Analyzing trace with hash -576599757, now seen corresponding path program 9 times [2019-11-23 20:50:20,303 INFO L163 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-23 20:50:20,303 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2073993206] [2019-11-23 20:50:20,303 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-23 20:50:20,333 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-23 20:50:20,576 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 0 proven. 44 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2019-11-23 20:50:20,576 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2073993206] [2019-11-23 20:50:20,576 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [670553883] [2019-11-23 20:50:20,576 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 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-23 20:50:20,623 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2019-11-23 20:50:20,623 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-23 20:50:20,624 INFO L255 TraceCheckSpWp]: Trace formula consists of 119 conjuncts, 34 conjunts are in the unsatisfiable core [2019-11-23 20:50:20,626 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2019-11-23 20:50:20,637 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 8 [2019-11-23 20:50:20,638 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-23 20:50:20,641 INFO L567 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-23 20:50:20,641 INFO L496 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2019-11-23 20:50:20,641 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:12, output treesize:8 [2019-11-23 20:50:20,733 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:20,737 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:20,755 INFO L343 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2019-11-23 20:50:20,755 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 36 treesize of output 78 [2019-11-23 20:50:20,756 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-23 20:50:20,783 INFO L567 ElimStorePlain]: treesize reduction 41, result has 54.4 percent of original size [2019-11-23 20:50:20,784 INFO L496 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2019-11-23 20:50:20,784 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 2 variables, input treesize:71, output treesize:49 [2019-11-23 20:50:20,966 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-23 20:50:20,990 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 0 proven. 17 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2019-11-23 20:50:20,991 INFO L220 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-23 20:50:20,991 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11] total 21 [2019-11-23 20:50:20,991 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2107748864] [2019-11-23 20:50:20,991 INFO L442 AbstractCegarLoop]: Interpolant automaton has 21 states [2019-11-23 20:50:20,991 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-23 20:50:20,992 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2019-11-23 20:50:20,992 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=60, Invalid=360, Unknown=0, NotChecked=0, Total=420 [2019-11-23 20:50:20,992 INFO L87 Difference]: Start difference. First operand 37 states and 39 transitions. Second operand 21 states. [2019-11-23 20:50:22,119 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-23 20:50:22,119 INFO L93 Difference]: Finished difference Result 47 states and 49 transitions. [2019-11-23 20:50:22,119 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2019-11-23 20:50:22,119 INFO L78 Accepts]: Start accepts. Automaton has 21 states. Word has length 36 [2019-11-23 20:50:22,120 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-23 20:50:22,120 INFO L225 Difference]: With dead ends: 47 [2019-11-23 20:50:22,120 INFO L226 Difference]: Without dead ends: 45 [2019-11-23 20:50:22,122 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 66 GetRequests, 29 SyntacticMatches, 2 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 202 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=217, Invalid=1115, Unknown=0, NotChecked=0, Total=1332 [2019-11-23 20:50:22,122 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2019-11-23 20:50:22,127 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 41. [2019-11-23 20:50:22,128 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 41 states. [2019-11-23 20:50:22,128 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 43 transitions. [2019-11-23 20:50:22,128 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 43 transitions. Word has length 36 [2019-11-23 20:50:22,129 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-23 20:50:22,129 INFO L462 AbstractCegarLoop]: Abstraction has 41 states and 43 transitions. [2019-11-23 20:50:22,129 INFO L463 AbstractCegarLoop]: Interpolant automaton has 21 states. [2019-11-23 20:50:22,129 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 43 transitions. [2019-11-23 20:50:22,130 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2019-11-23 20:50:22,130 INFO L402 BasicCegarLoop]: Found error trace [2019-11-23 20:50:22,130 INFO L410 BasicCegarLoop]: trace histogram [6, 6, 4, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-23 20:50:22,333 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-23 20:50:22,333 INFO L410 AbstractCegarLoop]: === Iteration 15 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-23 20:50:22,334 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-23 20:50:22,334 INFO L82 PathProgramCache]: Analyzing trace with hash 1095581801, now seen corresponding path program 10 times [2019-11-23 20:50:22,334 INFO L163 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-23 20:50:22,334 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1735177861] [2019-11-23 20:50:22,335 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-23 20:50:22,366 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-23 20:50:23,031 WARN L192 SmtUtils]: Spent 116.00 ms on a formula simplification. DAG size of input: 65 DAG size of output: 35 [2019-11-23 20:50:23,174 WARN L192 SmtUtils]: Spent 104.00 ms on a formula simplification. DAG size of input: 78 DAG size of output: 37 [2019-11-23 20:50:23,598 INFO L134 CoverageAnalysis]: Checked inductivity of 63 backedges. 0 proven. 63 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-11-23 20:50:23,599 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1735177861] [2019-11-23 20:50:23,599 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [240768417] [2019-11-23 20:50:23,599 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 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-23 20:50:23,640 INFO L249 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2019-11-23 20:50:23,640 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-23 20:50:23,642 INFO L255 TraceCheckSpWp]: Trace formula consists of 112 conjuncts, 42 conjunts are in the unsatisfiable core [2019-11-23 20:50:23,644 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2019-11-23 20:50:23,659 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 8 [2019-11-23 20:50:23,660 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-23 20:50:23,665 INFO L567 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-23 20:50:23,665 INFO L496 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2019-11-23 20:50:23,666 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:15, output treesize:11 [2019-11-23 20:50:24,055 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-23 20:50:24,055 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-23 20:50:24,062 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:24,066 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:24,068 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:24,071 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 61 treesize of output 67 [2019-11-23 20:50:24,072 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-23 20:50:24,075 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:24,079 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:24,081 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:24,082 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 57 treesize of output 63 [2019-11-23 20:50:24,083 INFO L496 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2019-11-23 20:50:24,126 INFO L567 ElimStorePlain]: treesize reduction 70, result has 41.2 percent of original size [2019-11-23 20:50:24,127 INFO L496 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2019-11-23 20:50:24,127 INFO L221 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:163, output treesize:49 [2019-11-23 20:50:24,549 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-23 20:50:24,625 INFO L134 CoverageAnalysis]: Checked inductivity of 63 backedges. 0 proven. 63 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-11-23 20:50:24,626 INFO L220 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-23 20:50:24,626 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 19] total 39 [2019-11-23 20:50:24,626 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [167618187] [2019-11-23 20:50:24,628 INFO L442 AbstractCegarLoop]: Interpolant automaton has 39 states [2019-11-23 20:50:24,628 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-23 20:50:24,628 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 39 interpolants. [2019-11-23 20:50:24,629 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=165, Invalid=1317, Unknown=0, NotChecked=0, Total=1482 [2019-11-23 20:50:24,629 INFO L87 Difference]: Start difference. First operand 41 states and 43 transitions. Second operand 39 states. [2019-11-23 20:50:27,378 WARN L192 SmtUtils]: Spent 112.00 ms on a formula simplification. DAG size of input: 94 DAG size of output: 59 [2019-11-23 20:50:27,550 WARN L192 SmtUtils]: Spent 103.00 ms on a formula simplification. DAG size of input: 91 DAG size of output: 54 [2019-11-23 20:50:27,738 WARN L192 SmtUtils]: Spent 121.00 ms on a formula simplification. DAG size of input: 94 DAG size of output: 57 [2019-11-23 20:50:27,922 WARN L192 SmtUtils]: Spent 110.00 ms on a formula simplification. DAG size of input: 97 DAG size of output: 58 [2019-11-23 20:50:28,114 WARN L192 SmtUtils]: Spent 122.00 ms on a formula simplification. DAG size of input: 93 DAG size of output: 58 [2019-11-23 20:50:28,303 WARN L192 SmtUtils]: Spent 120.00 ms on a formula simplification. DAG size of input: 96 DAG size of output: 61 [2019-11-23 20:50:28,503 WARN L192 SmtUtils]: Spent 116.00 ms on a formula simplification. DAG size of input: 91 DAG size of output: 62 [2019-11-23 20:50:28,513 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-23 20:50:28,513 INFO L93 Difference]: Finished difference Result 101 states and 107 transitions. [2019-11-23 20:50:28,514 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 36 states. [2019-11-23 20:50:28,514 INFO L78 Accepts]: Start accepts. Automaton has 39 states. Word has length 40 [2019-11-23 20:50:28,515 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-23 20:50:28,515 INFO L225 Difference]: With dead ends: 101 [2019-11-23 20:50:28,516 INFO L226 Difference]: Without dead ends: 82 [2019-11-23 20:50:28,518 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 91 GetRequests, 24 SyntacticMatches, 1 SemanticMatches, 66 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 789 ImplicationChecksByTransitivity, 5.0s TimeCoverageRelationStatistics Valid=816, Invalid=3740, Unknown=0, NotChecked=0, Total=4556 [2019-11-23 20:50:28,518 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 82 states. [2019-11-23 20:50:28,526 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 82 to 56. [2019-11-23 20:50:28,526 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 56 states. [2019-11-23 20:50:28,527 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 59 transitions. [2019-11-23 20:50:28,527 INFO L78 Accepts]: Start accepts. Automaton has 56 states and 59 transitions. Word has length 40 [2019-11-23 20:50:28,527 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-23 20:50:28,527 INFO L462 AbstractCegarLoop]: Abstraction has 56 states and 59 transitions. [2019-11-23 20:50:28,527 INFO L463 AbstractCegarLoop]: Interpolant automaton has 39 states. [2019-11-23 20:50:28,527 INFO L276 IsEmpty]: Start isEmpty. Operand 56 states and 59 transitions. [2019-11-23 20:50:28,528 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2019-11-23 20:50:28,528 INFO L402 BasicCegarLoop]: Found error trace [2019-11-23 20:50:28,529 INFO L410 BasicCegarLoop]: trace histogram [7, 7, 4, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-23 20:50:28,731 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-23 20:50:28,732 INFO L410 AbstractCegarLoop]: === Iteration 16 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-23 20:50:28,732 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-23 20:50:28,733 INFO L82 PathProgramCache]: Analyzing trace with hash -687256441, now seen corresponding path program 11 times [2019-11-23 20:50:28,733 INFO L163 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-23 20:50:28,733 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1565020795] [2019-11-23 20:50:28,734 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-23 20:50:28,753 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-23 20:50:29,227 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 25 proven. 33 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2019-11-23 20:50:29,228 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1565020795] [2019-11-23 20:50:29,228 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1232634805] [2019-11-23 20:50:29,228 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 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-23 20:50:29,508 INFO L249 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 8 check-sat command(s) [2019-11-23 20:50:29,509 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-23 20:50:29,510 INFO L255 TraceCheckSpWp]: Trace formula consists of 156 conjuncts, 15 conjunts are in the unsatisfiable core [2019-11-23 20:50:29,512 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2019-11-23 20:50:29,745 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 36 proven. 22 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2019-11-23 20:50:29,745 INFO L220 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-23 20:50:29,745 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 26 [2019-11-23 20:50:29,746 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1195501038] [2019-11-23 20:50:29,746 INFO L442 AbstractCegarLoop]: Interpolant automaton has 26 states [2019-11-23 20:50:29,746 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-23 20:50:29,746 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2019-11-23 20:50:29,747 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=144, Invalid=506, Unknown=0, NotChecked=0, Total=650 [2019-11-23 20:50:29,747 INFO L87 Difference]: Start difference. First operand 56 states and 59 transitions. Second operand 26 states. [2019-11-23 20:50:30,703 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-23 20:50:30,703 INFO L93 Difference]: Finished difference Result 127 states and 133 transitions. [2019-11-23 20:50:30,704 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2019-11-23 20:50:30,704 INFO L78 Accepts]: Start accepts. Automaton has 26 states. Word has length 42 [2019-11-23 20:50:30,704 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-23 20:50:30,705 INFO L225 Difference]: With dead ends: 127 [2019-11-23 20:50:30,705 INFO L226 Difference]: Without dead ends: 110 [2019-11-23 20:50:30,706 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 68 GetRequests, 31 SyntacticMatches, 1 SemanticMatches, 36 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 352 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=296, Invalid=1110, Unknown=0, NotChecked=0, Total=1406 [2019-11-23 20:50:30,707 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 110 states. [2019-11-23 20:50:30,716 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 110 to 58. [2019-11-23 20:50:30,716 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 58 states. [2019-11-23 20:50:30,717 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 61 transitions. [2019-11-23 20:50:30,717 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 61 transitions. Word has length 42 [2019-11-23 20:50:30,717 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-23 20:50:30,717 INFO L462 AbstractCegarLoop]: Abstraction has 58 states and 61 transitions. [2019-11-23 20:50:30,717 INFO L463 AbstractCegarLoop]: Interpolant automaton has 26 states. [2019-11-23 20:50:30,717 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 61 transitions. [2019-11-23 20:50:30,718 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2019-11-23 20:50:30,718 INFO L402 BasicCegarLoop]: Found error trace [2019-11-23 20:50:30,718 INFO L410 BasicCegarLoop]: trace histogram [6, 6, 5, 4, 4, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-23 20:50:30,922 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-23 20:50:30,923 INFO L410 AbstractCegarLoop]: === Iteration 17 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-23 20:50:30,923 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-23 20:50:30,923 INFO L82 PathProgramCache]: Analyzing trace with hash 1734225055, now seen corresponding path program 12 times [2019-11-23 20:50:30,924 INFO L163 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-23 20:50:30,924 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1140269983] [2019-11-23 20:50:30,924 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-23 20:50:30,949 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-23 20:50:31,719 WARN L192 SmtUtils]: Spent 108.00 ms on a formula simplification. DAG size of input: 94 DAG size of output: 51 [2019-11-23 20:50:32,248 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 1 proven. 76 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-11-23 20:50:32,249 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1140269983] [2019-11-23 20:50:32,249 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1713591095] [2019-11-23 20:50:32,249 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 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-23 20:50:32,334 INFO L249 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2019-11-23 20:50:32,334 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-23 20:50:32,336 INFO L255 TraceCheckSpWp]: Trace formula consists of 163 conjuncts, 58 conjunts are in the unsatisfiable core [2019-11-23 20:50:32,338 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2019-11-23 20:50:32,347 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 8 [2019-11-23 20:50:32,348 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-23 20:50:32,353 INFO L567 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-23 20:50:32,353 INFO L496 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2019-11-23 20:50:32,354 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:18, output treesize:14 [2019-11-23 20:50:32,783 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:32,786 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:32,787 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:32,789 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 46 treesize of output 53 [2019-11-23 20:50:32,789 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-23 20:50:32,806 INFO L567 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-23 20:50:32,807 INFO L496 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2019-11-23 20:50:32,807 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:94, output treesize:66 [2019-11-23 20:50:32,974 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:32,982 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:32,983 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:32,984 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:32,985 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:32,986 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:32,987 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:32,988 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:32,989 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:32,991 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:32,992 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:32,993 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:32,994 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:32,996 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 6 select indices, 6 select index equivalence classes, 13 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 0 case distinctions, treesize of input 73 treesize of output 91 [2019-11-23 20:50:32,997 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-23 20:50:33,015 INFO L567 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-23 20:50:33,016 INFO L496 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2019-11-23 20:50:33,016 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 2 variables, input treesize:111, output treesize:89 [2019-11-23 20:50:33,609 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-23 20:50:33,704 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 0 proven. 77 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-11-23 20:50:33,704 INFO L220 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-23 20:50:33,704 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [23, 22] total 43 [2019-11-23 20:50:33,705 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [791149527] [2019-11-23 20:50:33,705 INFO L442 AbstractCegarLoop]: Interpolant automaton has 43 states [2019-11-23 20:50:33,706 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-23 20:50:33,706 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 43 interpolants. [2019-11-23 20:50:33,707 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=201, Invalid=1605, Unknown=0, NotChecked=0, Total=1806 [2019-11-23 20:50:33,707 INFO L87 Difference]: Start difference. First operand 58 states and 61 transitions. Second operand 43 states. [2019-11-23 20:50:34,586 WARN L192 SmtUtils]: Spent 130.00 ms on a formula simplification. DAG size of input: 75 DAG size of output: 61 [2019-11-23 20:50:36,662 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-23 20:50:36,663 INFO L93 Difference]: Finished difference Result 89 states and 92 transitions. [2019-11-23 20:50:36,663 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 34 states. [2019-11-23 20:50:36,663 INFO L78 Accepts]: Start accepts. Automaton has 43 states. Word has length 44 [2019-11-23 20:50:36,664 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-23 20:50:36,664 INFO L225 Difference]: With dead ends: 89 [2019-11-23 20:50:36,664 INFO L226 Difference]: Without dead ends: 87 [2019-11-23 20:50:36,667 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 88 GetRequests, 25 SyntacticMatches, 1 SemanticMatches, 62 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 836 ImplicationChecksByTransitivity, 4.4s TimeCoverageRelationStatistics Valid=584, Invalid=3448, Unknown=0, NotChecked=0, Total=4032 [2019-11-23 20:50:36,667 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 87 states. [2019-11-23 20:50:36,677 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 87 to 62. [2019-11-23 20:50:36,677 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 62 states. [2019-11-23 20:50:36,677 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 65 transitions. [2019-11-23 20:50:36,678 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 65 transitions. Word has length 44 [2019-11-23 20:50:36,678 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-23 20:50:36,678 INFO L462 AbstractCegarLoop]: Abstraction has 62 states and 65 transitions. [2019-11-23 20:50:36,678 INFO L463 AbstractCegarLoop]: Interpolant automaton has 43 states. [2019-11-23 20:50:36,678 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 65 transitions. [2019-11-23 20:50:36,679 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2019-11-23 20:50:36,679 INFO L402 BasicCegarLoop]: Found error trace [2019-11-23 20:50:36,679 INFO L410 BasicCegarLoop]: trace histogram [7, 7, 4, 4, 4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-23 20:50:36,882 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 15 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-23 20:50:36,882 INFO L410 AbstractCegarLoop]: === Iteration 18 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-23 20:50:36,883 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-23 20:50:36,883 INFO L82 PathProgramCache]: Analyzing trace with hash -1242506907, now seen corresponding path program 13 times [2019-11-23 20:50:36,883 INFO L163 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-23 20:50:36,884 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1556883107] [2019-11-23 20:50:36,884 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-23 20:50:36,897 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-23 20:50:37,160 INFO L134 CoverageAnalysis]: Checked inductivity of 83 backedges. 11 proven. 54 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2019-11-23 20:50:37,160 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1556883107] [2019-11-23 20:50:37,160 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [733854508] [2019-11-23 20:50:37,160 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 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-23 20:50:37,208 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-23 20:50:37,209 INFO L255 TraceCheckSpWp]: Trace formula consists of 160 conjuncts, 15 conjunts are in the unsatisfiable core [2019-11-23 20:50:37,211 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2019-11-23 20:50:37,321 INFO L134 CoverageAnalysis]: Checked inductivity of 83 backedges. 16 proven. 49 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2019-11-23 20:50:37,321 INFO L220 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-23 20:50:37,321 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 15] total 21 [2019-11-23 20:50:37,322 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1981446006] [2019-11-23 20:50:37,322 INFO L442 AbstractCegarLoop]: Interpolant automaton has 21 states [2019-11-23 20:50:37,322 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-23 20:50:37,323 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2019-11-23 20:50:37,323 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=95, Invalid=325, Unknown=0, NotChecked=0, Total=420 [2019-11-23 20:50:37,324 INFO L87 Difference]: Start difference. First operand 62 states and 65 transitions. Second operand 21 states. [2019-11-23 20:50:37,729 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-23 20:50:37,729 INFO L93 Difference]: Finished difference Result 117 states and 122 transitions. [2019-11-23 20:50:37,730 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2019-11-23 20:50:37,730 INFO L78 Accepts]: Start accepts. Automaton has 21 states. Word has length 44 [2019-11-23 20:50:37,730 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-23 20:50:37,731 INFO L225 Difference]: With dead ends: 117 [2019-11-23 20:50:37,731 INFO L226 Difference]: Without dead ends: 90 [2019-11-23 20:50:37,732 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 70 GetRequests, 39 SyntacticMatches, 2 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 167 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=243, Invalid=687, Unknown=0, NotChecked=0, Total=930 [2019-11-23 20:50:37,732 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 90 states. [2019-11-23 20:50:37,741 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 90 to 64. [2019-11-23 20:50:37,741 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 64 states. [2019-11-23 20:50:37,742 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 67 transitions. [2019-11-23 20:50:37,742 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 67 transitions. Word has length 44 [2019-11-23 20:50:37,742 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-23 20:50:37,742 INFO L462 AbstractCegarLoop]: Abstraction has 64 states and 67 transitions. [2019-11-23 20:50:37,742 INFO L463 AbstractCegarLoop]: Interpolant automaton has 21 states. [2019-11-23 20:50:37,742 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 67 transitions. [2019-11-23 20:50:37,743 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2019-11-23 20:50:37,743 INFO L402 BasicCegarLoop]: Found error trace [2019-11-23 20:50:37,743 INFO L410 BasicCegarLoop]: trace histogram [8, 8, 4, 4, 4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-23 20:50:37,946 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-23 20:50:37,946 INFO L410 AbstractCegarLoop]: === Iteration 19 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-23 20:50:37,946 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-23 20:50:37,946 INFO L82 PathProgramCache]: Analyzing trace with hash -1200773501, now seen corresponding path program 14 times [2019-11-23 20:50:37,946 INFO L163 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-23 20:50:37,947 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1414547760] [2019-11-23 20:50:37,947 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-23 20:50:37,972 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-23 20:50:38,430 INFO L134 CoverageAnalysis]: Checked inductivity of 98 backedges. 6 proven. 92 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-11-23 20:50:38,430 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1414547760] [2019-11-23 20:50:38,430 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1441357919] [2019-11-23 20:50:38,430 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 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-23 20:50:38,477 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2019-11-23 20:50:38,477 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-23 20:50:38,478 INFO L255 TraceCheckSpWp]: Trace formula consists of 166 conjuncts, 42 conjunts are in the unsatisfiable core [2019-11-23 20:50:38,479 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2019-11-23 20:50:38,483 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 8 [2019-11-23 20:50:38,483 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-23 20:50:38,489 INFO L567 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-23 20:50:38,490 INFO L496 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2019-11-23 20:50:38,490 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:15, output treesize:11 [2019-11-23 20:50:38,600 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:38,605 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:38,606 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:38,607 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 36 treesize of output 43 [2019-11-23 20:50:38,607 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-23 20:50:38,621 INFO L567 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-23 20:50:38,622 INFO L496 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2019-11-23 20:50:38,622 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 2 variables, input treesize:74, output treesize:52 [2019-11-23 20:50:38,876 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-23 20:50:38,909 INFO L134 CoverageAnalysis]: Checked inductivity of 98 backedges. 0 proven. 34 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2019-11-23 20:50:38,909 INFO L220 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-23 20:50:38,909 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 13] total 28 [2019-11-23 20:50:38,910 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1935372774] [2019-11-23 20:50:38,910 INFO L442 AbstractCegarLoop]: Interpolant automaton has 28 states [2019-11-23 20:50:38,910 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-23 20:50:38,910 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2019-11-23 20:50:38,911 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=120, Invalid=636, Unknown=0, NotChecked=0, Total=756 [2019-11-23 20:50:38,911 INFO L87 Difference]: Start difference. First operand 64 states and 67 transitions. Second operand 28 states. [2019-11-23 20:50:40,627 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-23 20:50:40,628 INFO L93 Difference]: Finished difference Result 115 states and 120 transitions. [2019-11-23 20:50:40,628 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 42 states. [2019-11-23 20:50:40,628 INFO L78 Accepts]: Start accepts. Automaton has 28 states. Word has length 46 [2019-11-23 20:50:40,629 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-23 20:50:40,630 INFO L225 Difference]: With dead ends: 115 [2019-11-23 20:50:40,630 INFO L226 Difference]: Without dead ends: 113 [2019-11-23 20:50:40,631 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 100 GetRequests, 43 SyntacticMatches, 5 SemanticMatches, 52 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 791 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=371, Invalid=2491, Unknown=0, NotChecked=0, Total=2862 [2019-11-23 20:50:40,632 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 113 states. [2019-11-23 20:50:40,641 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 113 to 64. [2019-11-23 20:50:40,641 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 64 states. [2019-11-23 20:50:40,642 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 67 transitions. [2019-11-23 20:50:40,642 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 67 transitions. Word has length 46 [2019-11-23 20:50:40,642 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-23 20:50:40,642 INFO L462 AbstractCegarLoop]: Abstraction has 64 states and 67 transitions. [2019-11-23 20:50:40,642 INFO L463 AbstractCegarLoop]: Interpolant automaton has 28 states. [2019-11-23 20:50:40,643 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 67 transitions. [2019-11-23 20:50:40,643 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 49 [2019-11-23 20:50:40,643 INFO L402 BasicCegarLoop]: Found error trace [2019-11-23 20:50:40,643 INFO L410 BasicCegarLoop]: trace histogram [6, 6, 6, 5, 5, 5, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-23 20:50:40,846 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-23 20:50:40,846 INFO L410 AbstractCegarLoop]: === Iteration 20 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-23 20:50:40,847 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-23 20:50:40,847 INFO L82 PathProgramCache]: Analyzing trace with hash 101846485, now seen corresponding path program 15 times [2019-11-23 20:50:40,847 INFO L163 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-23 20:50:40,847 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [938997534] [2019-11-23 20:50:40,848 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-23 20:50:40,877 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-23 20:50:41,655 WARN L192 SmtUtils]: Spent 108.00 ms on a formula simplification. DAG size of input: 104 DAG size of output: 62 [2019-11-23 20:50:41,929 WARN L192 SmtUtils]: Spent 122.00 ms on a formula simplification. DAG size of input: 88 DAG size of output: 54 [2019-11-23 20:50:42,504 INFO L134 CoverageAnalysis]: Checked inductivity of 95 backedges. 1 proven. 94 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-11-23 20:50:42,505 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [938997534] [2019-11-23 20:50:42,505 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1861072421] [2019-11-23 20:50:42,505 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 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-23 20:50:42,581 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2019-11-23 20:50:42,582 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-23 20:50:42,583 INFO L255 TraceCheckSpWp]: Trace formula consists of 170 conjuncts, 42 conjunts are in the unsatisfiable core [2019-11-23 20:50:42,584 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2019-11-23 20:50:42,588 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 8 [2019-11-23 20:50:42,588 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-23 20:50:42,592 INFO L567 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-23 20:50:42,592 INFO L496 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2019-11-23 20:50:42,593 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:12, output treesize:8 [2019-11-23 20:50:42,624 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 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-23 20:50:42,625 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-23 20:50:42,632 INFO L567 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-23 20:50:42,633 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-23 20:50:42,633 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 2 variables, input treesize:26, output treesize:11 [2019-11-23 20:50:42,750 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:42,775 INFO L343 Elim1Store]: treesize reduction 48, result has 42.9 percent of original size [2019-11-23 20:50:42,775 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 46 treesize of output 73 [2019-11-23 20:50:42,776 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-23 20:50:42,808 INFO L567 ElimStorePlain]: treesize reduction 40, result has 60.8 percent of original size [2019-11-23 20:50:42,808 INFO L496 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2019-11-23 20:50:42,808 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:90, output treesize:62 [2019-11-23 20:50:42,917 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,096 WARN L192 SmtUtils]: Spent 173.00 ms on a formula simplification. DAG size of input: 82 DAG size of output: 71 [2019-11-23 20:50:43,097 INFO L343 Elim1Store]: treesize reduction 117, result has 66.9 percent of original size [2019-11-23 20:50:43,097 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 6 select indices, 6 select index equivalence classes, 1 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 10 case distinctions, treesize of input 79 treesize of output 299 [2019-11-23 20:50:43,100 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-23 20:50:43,187 INFO L567 ElimStorePlain]: treesize reduction 330, result has 22.2 percent of original size [2019-11-23 20:50:43,188 INFO L496 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2019-11-23 20:50:43,188 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:122, output treesize:94 [2019-11-23 20:50:43,337 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,345 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,348 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,350 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,353 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,355 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,357 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,360 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,362 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,364 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,367 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,369 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,371 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,372 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,374 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,376 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,378 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,381 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,383 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,386 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,388 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,390 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,392 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,393 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,396 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,397 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,399 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,402 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,404 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,405 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,407 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,527 INFO L237 Elim1Store]: Index analysis took 183 ms [2019-11-23 20:50:43,533 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 10 select indices, 10 select index equivalence classes, 31 disjoint index pairs (out of 45 index pairs), introduced 10 new quantified variables, introduced 0 case distinctions, treesize of input 145 treesize of output 175 [2019-11-23 20:50:43,534 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-23 20:50:43,542 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,553 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,554 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,556 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,557 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,558 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,561 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,563 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,565 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,566 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,567 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,568 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,570 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,571 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,572 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,574 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,575 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,576 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,578 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,579 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,580 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,582 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,583 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,584 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,585 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,594 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,595 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,595 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,596 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,597 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,598 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:43,602 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 10 select indices, 10 select index equivalence classes, 31 disjoint index pairs (out of 45 index pairs), introduced 10 new quantified variables, introduced 0 case distinctions, treesize of input 149 treesize of output 179 [2019-11-23 20:50:43,603 INFO L496 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2019-11-23 20:50:43,691 INFO L567 ElimStorePlain]: treesize reduction 153, result has 48.1 percent of original size [2019-11-23 20:50:43,691 INFO L496 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2019-11-23 20:50:43,692 INFO L221 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:351, output treesize:142 [2019-11-23 20:50:43,866 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 3 terms [2019-11-23 20:50:43,867 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-23 20:50:43,868 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-23 20:50:44,622 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-23 20:50:44,697 INFO L134 CoverageAnalysis]: Checked inductivity of 95 backedges. 56 proven. 14 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2019-11-23 20:50:44,697 INFO L220 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-23 20:50:44,697 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [23, 20] total 41 [2019-11-23 20:50:44,698 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1761902576] [2019-11-23 20:50:44,698 INFO L442 AbstractCegarLoop]: Interpolant automaton has 41 states [2019-11-23 20:50:44,698 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-23 20:50:44,698 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 41 interpolants. [2019-11-23 20:50:44,699 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=160, Invalid=1480, Unknown=0, NotChecked=0, Total=1640 [2019-11-23 20:50:44,699 INFO L87 Difference]: Start difference. First operand 64 states and 67 transitions. Second operand 41 states. [2019-11-23 20:50:45,583 WARN L192 SmtUtils]: Spent 122.00 ms on a formula simplification. DAG size of input: 82 DAG size of output: 57 [2019-11-23 20:50:46,460 WARN L192 SmtUtils]: Spent 104.00 ms on a formula simplification. DAG size of input: 135 DAG size of output: 56 [2019-11-23 20:50:46,649 WARN L192 SmtUtils]: Spent 111.00 ms on a formula simplification. DAG size of input: 121 DAG size of output: 57 [2019-11-23 20:50:46,885 WARN L192 SmtUtils]: Spent 152.00 ms on a formula simplification. DAG size of input: 118 DAG size of output: 57 [2019-11-23 20:50:47,093 WARN L192 SmtUtils]: Spent 155.00 ms on a formula simplification. DAG size of input: 120 DAG size of output: 60 [2019-11-23 20:50:47,385 WARN L192 SmtUtils]: Spent 115.00 ms on a formula simplification. DAG size of input: 137 DAG size of output: 56 [2019-11-23 20:50:47,655 WARN L192 SmtUtils]: Spent 110.00 ms on a formula simplification. DAG size of input: 137 DAG size of output: 59 [2019-11-23 20:50:48,211 WARN L192 SmtUtils]: Spent 114.00 ms on a formula simplification. DAG size of input: 124 DAG size of output: 60 [2019-11-23 20:50:48,435 WARN L192 SmtUtils]: Spent 102.00 ms on a formula simplification. DAG size of input: 115 DAG size of output: 61 [2019-11-23 20:50:48,662 WARN L192 SmtUtils]: Spent 107.00 ms on a formula simplification. DAG size of input: 117 DAG size of output: 63 [2019-11-23 20:50:48,681 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-23 20:50:48,682 INFO L93 Difference]: Finished difference Result 90 states and 94 transitions. [2019-11-23 20:50:48,682 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 41 states. [2019-11-23 20:50:48,682 INFO L78 Accepts]: Start accepts. Automaton has 41 states. Word has length 48 [2019-11-23 20:50:48,683 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-23 20:50:48,683 INFO L225 Difference]: With dead ends: 90 [2019-11-23 20:50:48,683 INFO L226 Difference]: Without dead ends: 54 [2019-11-23 20:50:48,686 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 98 GetRequests, 31 SyntacticMatches, 2 SemanticMatches, 65 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 824 ImplicationChecksByTransitivity, 5.5s TimeCoverageRelationStatistics Valid=601, Invalid=3821, Unknown=0, NotChecked=0, Total=4422 [2019-11-23 20:50:48,686 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2019-11-23 20:50:48,694 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 51. [2019-11-23 20:50:48,694 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 51 states. [2019-11-23 20:50:48,695 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 53 transitions. [2019-11-23 20:50:48,695 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 53 transitions. Word has length 48 [2019-11-23 20:50:48,695 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-23 20:50:48,695 INFO L462 AbstractCegarLoop]: Abstraction has 51 states and 53 transitions. [2019-11-23 20:50:48,695 INFO L463 AbstractCegarLoop]: Interpolant automaton has 41 states. [2019-11-23 20:50:48,695 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 53 transitions. [2019-11-23 20:50:48,696 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2019-11-23 20:50:48,696 INFO L402 BasicCegarLoop]: Found error trace [2019-11-23 20:50:48,696 INFO L410 BasicCegarLoop]: trace histogram [8, 8, 5, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-23 20:50:48,899 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 18 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-23 20:50:48,899 INFO L410 AbstractCegarLoop]: === Iteration 21 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-23 20:50:48,900 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-23 20:50:48,900 INFO L82 PathProgramCache]: Analyzing trace with hash -313920071, now seen corresponding path program 16 times [2019-11-23 20:50:48,900 INFO L163 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-23 20:50:48,901 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [598877398] [2019-11-23 20:50:48,901 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-23 20:50:48,933 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-23 20:50:49,882 WARN L192 SmtUtils]: Spent 119.00 ms on a formula simplification. DAG size of input: 73 DAG size of output: 36 [2019-11-23 20:50:50,139 WARN L192 SmtUtils]: Spent 170.00 ms on a formula simplification. DAG size of input: 79 DAG size of output: 48 [2019-11-23 20:50:50,359 WARN L192 SmtUtils]: Spent 152.00 ms on a formula simplification. DAG size of input: 78 DAG size of output: 49 [2019-11-23 20:50:50,562 WARN L192 SmtUtils]: Spent 135.00 ms on a formula simplification. DAG size of input: 91 DAG size of output: 42 [2019-11-23 20:50:51,126 INFO L134 CoverageAnalysis]: Checked inductivity of 112 backedges. 0 proven. 112 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-11-23 20:50:51,127 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [598877398] [2019-11-23 20:50:51,127 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1260108374] [2019-11-23 20:50:51,127 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 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-23 20:50:51,179 INFO L249 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2019-11-23 20:50:51,180 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-23 20:50:51,181 INFO L255 TraceCheckSpWp]: Trace formula consists of 133 conjuncts, 52 conjunts are in the unsatisfiable core [2019-11-23 20:50:51,182 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2019-11-23 20:50:51,186 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 8 [2019-11-23 20:50:51,186 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-23 20:50:51,192 INFO L567 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-23 20:50:51,193 INFO L496 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2019-11-23 20:50:51,193 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:18, output treesize:14 [2019-11-23 20:50:51,831 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-23 20:50:51,832 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-23 20:50:51,840 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:51,844 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:51,846 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:51,849 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 60 treesize of output 66 [2019-11-23 20:50:51,850 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-23 20:50:51,854 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:51,858 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:51,873 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:50:51,874 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 64 treesize of output 70 [2019-11-23 20:50:51,875 INFO L496 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2019-11-23 20:50:51,921 INFO L567 ElimStorePlain]: treesize reduction 73, result has 41.6 percent of original size [2019-11-23 20:50:51,922 INFO L496 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2019-11-23 20:50:51,922 INFO L221 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:169, output treesize:52 [2019-11-23 20:50:52,418 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-23 20:50:52,484 INFO L134 CoverageAnalysis]: Checked inductivity of 112 backedges. 0 proven. 112 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-11-23 20:50:52,485 INFO L220 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-23 20:50:52,485 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [27, 23] total 48 [2019-11-23 20:50:52,485 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [858467146] [2019-11-23 20:50:52,485 INFO L442 AbstractCegarLoop]: Interpolant automaton has 48 states [2019-11-23 20:50:52,485 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-23 20:50:52,485 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 48 interpolants. [2019-11-23 20:50:52,486 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=209, Invalid=2047, Unknown=0, NotChecked=0, Total=2256 [2019-11-23 20:50:52,486 INFO L87 Difference]: Start difference. First operand 51 states and 53 transitions. Second operand 48 states. [2019-11-23 20:50:55,209 WARN L192 SmtUtils]: Spent 112.00 ms on a formula simplification. DAG size of input: 136 DAG size of output: 49 [2019-11-23 20:50:55,428 WARN L192 SmtUtils]: Spent 126.00 ms on a formula simplification. DAG size of input: 139 DAG size of output: 52 [2019-11-23 20:50:55,662 WARN L192 SmtUtils]: Spent 101.00 ms on a formula simplification. DAG size of input: 141 DAG size of output: 49 [2019-11-23 20:50:57,591 WARN L192 SmtUtils]: Spent 117.00 ms on a formula simplification. DAG size of input: 91 DAG size of output: 52 [2019-11-23 20:50:57,820 WARN L192 SmtUtils]: Spent 109.00 ms on a formula simplification. DAG size of input: 88 DAG size of output: 49 [2019-11-23 20:50:58,439 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-23 20:50:58,439 INFO L93 Difference]: Finished difference Result 127 states and 133 transitions. [2019-11-23 20:50:58,440 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 41 states. [2019-11-23 20:50:58,440 INFO L78 Accepts]: Start accepts. Automaton has 48 states. Word has length 50 [2019-11-23 20:50:58,440 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-23 20:50:58,441 INFO L225 Difference]: With dead ends: 127 [2019-11-23 20:50:58,441 INFO L226 Difference]: Without dead ends: 104 [2019-11-23 20:50:58,443 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 109 GetRequests, 30 SyntacticMatches, 0 SemanticMatches, 79 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1016 ImplicationChecksByTransitivity, 7.5s TimeCoverageRelationStatistics Valid=852, Invalid=5628, Unknown=0, NotChecked=0, Total=6480 [2019-11-23 20:50:58,444 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 104 states. [2019-11-23 20:50:58,452 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 104 to 68. [2019-11-23 20:50:58,452 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 68 states. [2019-11-23 20:50:58,453 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 68 states to 68 states and 71 transitions. [2019-11-23 20:50:58,453 INFO L78 Accepts]: Start accepts. Automaton has 68 states and 71 transitions. Word has length 50 [2019-11-23 20:50:58,453 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-23 20:50:58,453 INFO L462 AbstractCegarLoop]: Abstraction has 68 states and 71 transitions. [2019-11-23 20:50:58,453 INFO L463 AbstractCegarLoop]: Interpolant automaton has 48 states. [2019-11-23 20:50:58,453 INFO L276 IsEmpty]: Start isEmpty. Operand 68 states and 71 transitions. [2019-11-23 20:50:58,454 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 53 [2019-11-23 20:50:58,454 INFO L402 BasicCegarLoop]: Found error trace [2019-11-23 20:50:58,454 INFO L410 BasicCegarLoop]: trace histogram [9, 9, 5, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-23 20:50:58,654 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 19 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-23 20:50:58,655 INFO L410 AbstractCegarLoop]: === Iteration 22 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-23 20:50:58,655 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-23 20:50:58,655 INFO L82 PathProgramCache]: Analyzing trace with hash -1288440745, now seen corresponding path program 17 times [2019-11-23 20:50:58,656 INFO L163 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-23 20:50:58,656 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1173404214] [2019-11-23 20:50:58,656 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-23 20:50:58,671 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-23 20:50:59,221 INFO L134 CoverageAnalysis]: Checked inductivity of 129 backedges. 49 proven. 48 refuted. 0 times theorem prover too weak. 32 trivial. 0 not checked. [2019-11-23 20:50:59,221 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1173404214] [2019-11-23 20:50:59,221 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [182637332] [2019-11-23 20:50:59,222 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 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-23 20:50:59,807 INFO L249 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 10 check-sat command(s) [2019-11-23 20:50:59,807 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-23 20:50:59,811 INFO L255 TraceCheckSpWp]: Trace formula consists of 185 conjuncts, 18 conjunts are in the unsatisfiable core [2019-11-23 20:50:59,812 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2019-11-23 20:51:00,137 INFO L134 CoverageAnalysis]: Checked inductivity of 129 backedges. 64 proven. 33 refuted. 0 times theorem prover too weak. 32 trivial. 0 not checked. [2019-11-23 20:51:00,137 INFO L220 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-23 20:51:00,138 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 17] total 32 [2019-11-23 20:51:00,138 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1869460195] [2019-11-23 20:51:00,138 INFO L442 AbstractCegarLoop]: Interpolant automaton has 32 states [2019-11-23 20:51:00,138 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-23 20:51:00,138 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2019-11-23 20:51:00,139 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=215, Invalid=777, Unknown=0, NotChecked=0, Total=992 [2019-11-23 20:51:00,139 INFO L87 Difference]: Start difference. First operand 68 states and 71 transitions. Second operand 32 states. [2019-11-23 20:51:01,447 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-23 20:51:01,448 INFO L93 Difference]: Finished difference Result 162 states and 169 transitions. [2019-11-23 20:51:01,450 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2019-11-23 20:51:01,450 INFO L78 Accepts]: Start accepts. Automaton has 32 states. Word has length 52 [2019-11-23 20:51:01,451 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-23 20:51:01,453 INFO L225 Difference]: With dead ends: 162 [2019-11-23 20:51:01,453 INFO L226 Difference]: Without dead ends: 141 [2019-11-23 20:51:01,454 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 84 GetRequests, 38 SyntacticMatches, 1 SemanticMatches, 45 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 574 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=445, Invalid=1717, Unknown=0, NotChecked=0, Total=2162 [2019-11-23 20:51:01,454 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 141 states. [2019-11-23 20:51:01,466 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 141 to 70. [2019-11-23 20:51:01,466 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 70 states. [2019-11-23 20:51:01,466 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 70 states to 70 states and 73 transitions. [2019-11-23 20:51:01,467 INFO L78 Accepts]: Start accepts. Automaton has 70 states and 73 transitions. Word has length 52 [2019-11-23 20:51:01,467 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-23 20:51:01,467 INFO L462 AbstractCegarLoop]: Abstraction has 70 states and 73 transitions. [2019-11-23 20:51:01,467 INFO L463 AbstractCegarLoop]: Interpolant automaton has 32 states. [2019-11-23 20:51:01,467 INFO L276 IsEmpty]: Start isEmpty. Operand 70 states and 73 transitions. [2019-11-23 20:51:01,467 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2019-11-23 20:51:01,467 INFO L402 BasicCegarLoop]: Found error trace [2019-11-23 20:51:01,467 INFO L410 BasicCegarLoop]: trace histogram [8, 8, 6, 5, 5, 5, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-23 20:51:01,668 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 20 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-23 20:51:01,668 INFO L410 AbstractCegarLoop]: === Iteration 23 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-23 20:51:01,668 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-23 20:51:01,669 INFO L82 PathProgramCache]: Analyzing trace with hash -1335903761, now seen corresponding path program 18 times [2019-11-23 20:51:01,669 INFO L163 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-23 20:51:01,669 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1295299894] [2019-11-23 20:51:01,669 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-23 20:51:01,699 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-23 20:51:02,489 WARN L192 SmtUtils]: Spent 114.00 ms on a formula simplification. DAG size of input: 59 DAG size of output: 35 [2019-11-23 20:51:02,656 WARN L192 SmtUtils]: Spent 122.00 ms on a formula simplification. DAG size of input: 88 DAG size of output: 37 [2019-11-23 20:51:02,847 WARN L192 SmtUtils]: Spent 144.00 ms on a formula simplification. DAG size of input: 85 DAG size of output: 49 [2019-11-23 20:51:03,352 INFO L134 CoverageAnalysis]: Checked inductivity of 130 backedges. 3 proven. 127 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-11-23 20:51:03,353 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1295299894] [2019-11-23 20:51:03,353 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1711600224] [2019-11-23 20:51:03,353 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 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-23 20:51:03,486 INFO L249 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 9 check-sat command(s) [2019-11-23 20:51:03,487 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-23 20:51:03,488 INFO L255 TraceCheckSpWp]: Trace formula consists of 192 conjuncts, 66 conjunts are in the unsatisfiable core [2019-11-23 20:51:03,490 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2019-11-23 20:51:03,503 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 8 [2019-11-23 20:51:03,504 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-23 20:51:03,515 INFO L567 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-23 20:51:03,515 INFO L496 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2019-11-23 20:51:03,515 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:18, output treesize:14 [2019-11-23 20:51:04,040 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:04,043 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:04,045 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:04,047 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 46 treesize of output 53 [2019-11-23 20:51:04,047 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-23 20:51:04,064 INFO L567 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-23 20:51:04,064 INFO L496 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2019-11-23 20:51:04,064 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:94, output treesize:66 [2019-11-23 20:51:04,215 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:04,218 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:04,219 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:04,220 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:04,221 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:04,223 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:04,224 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:04,225 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:04,226 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:04,227 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:04,228 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:04,229 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:04,231 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:04,233 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 6 select indices, 6 select index equivalence classes, 13 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 0 case distinctions, treesize of input 73 treesize of output 91 [2019-11-23 20:51:04,233 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-23 20:51:04,254 INFO L567 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-23 20:51:04,255 INFO L496 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2019-11-23 20:51:04,255 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 2 variables, input treesize:111, output treesize:89 [2019-11-23 20:51:04,981 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-23 20:51:05,044 INFO L134 CoverageAnalysis]: Checked inductivity of 130 backedges. 0 proven. 130 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-11-23 20:51:05,044 INFO L220 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-23 20:51:05,044 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [27, 26] total 51 [2019-11-23 20:51:05,044 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1617228786] [2019-11-23 20:51:05,045 INFO L442 AbstractCegarLoop]: Interpolant automaton has 51 states [2019-11-23 20:51:05,045 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-23 20:51:05,045 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 51 interpolants. [2019-11-23 20:51:05,046 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=264, Invalid=2286, Unknown=0, NotChecked=0, Total=2550 [2019-11-23 20:51:05,046 INFO L87 Difference]: Start difference. First operand 70 states and 73 transitions. Second operand 51 states. [2019-11-23 20:51:08,009 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-23 20:51:08,009 INFO L93 Difference]: Finished difference Result 111 states and 114 transitions. [2019-11-23 20:51:08,010 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 40 states. [2019-11-23 20:51:08,010 INFO L78 Accepts]: Start accepts. Automaton has 51 states. Word has length 54 [2019-11-23 20:51:08,011 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-23 20:51:08,012 INFO L225 Difference]: With dead ends: 111 [2019-11-23 20:51:08,012 INFO L226 Difference]: Without dead ends: 109 [2019-11-23 20:51:08,014 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 105 GetRequests, 31 SyntacticMatches, 1 SemanticMatches, 73 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1206 ImplicationChecksByTransitivity, 4.8s TimeCoverageRelationStatistics Valid=751, Invalid=4799, Unknown=0, NotChecked=0, Total=5550 [2019-11-23 20:51:08,014 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 109 states. [2019-11-23 20:51:08,025 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 109 to 74. [2019-11-23 20:51:08,025 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 74 states. [2019-11-23 20:51:08,026 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 74 states to 74 states and 77 transitions. [2019-11-23 20:51:08,026 INFO L78 Accepts]: Start accepts. Automaton has 74 states and 77 transitions. Word has length 54 [2019-11-23 20:51:08,026 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-23 20:51:08,026 INFO L462 AbstractCegarLoop]: Abstraction has 74 states and 77 transitions. [2019-11-23 20:51:08,026 INFO L463 AbstractCegarLoop]: Interpolant automaton has 51 states. [2019-11-23 20:51:08,027 INFO L276 IsEmpty]: Start isEmpty. Operand 74 states and 77 transitions. [2019-11-23 20:51:08,027 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2019-11-23 20:51:08,027 INFO L402 BasicCegarLoop]: Found error trace [2019-11-23 20:51:08,027 INFO L410 BasicCegarLoop]: trace histogram [9, 9, 5, 5, 5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-23 20:51:08,230 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 21 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-23 20:51:08,231 INFO L410 AbstractCegarLoop]: === Iteration 24 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-23 20:51:08,231 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-23 20:51:08,231 INFO L82 PathProgramCache]: Analyzing trace with hash -1789287499, now seen corresponding path program 19 times [2019-11-23 20:51:08,231 INFO L163 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-23 20:51:08,231 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1682235618] [2019-11-23 20:51:08,232 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-23 20:51:08,248 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-23 20:51:09,109 INFO L134 CoverageAnalysis]: Checked inductivity of 138 backedges. 18 proven. 88 refuted. 0 times theorem prover too weak. 32 trivial. 0 not checked. [2019-11-23 20:51:09,109 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1682235618] [2019-11-23 20:51:09,110 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [508406142] [2019-11-23 20:51:09,110 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 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-23 20:51:09,173 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-23 20:51:09,174 INFO L255 TraceCheckSpWp]: Trace formula consists of 189 conjuncts, 18 conjunts are in the unsatisfiable core [2019-11-23 20:51:09,175 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2019-11-23 20:51:09,564 INFO L134 CoverageAnalysis]: Checked inductivity of 138 backedges. 25 proven. 81 refuted. 0 times theorem prover too weak. 32 trivial. 0 not checked. [2019-11-23 20:51:09,564 INFO L220 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-23 20:51:09,564 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 18] total 35 [2019-11-23 20:51:09,565 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [331632456] [2019-11-23 20:51:09,565 INFO L442 AbstractCegarLoop]: Interpolant automaton has 35 states [2019-11-23 20:51:09,565 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-23 20:51:09,565 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 35 interpolants. [2019-11-23 20:51:09,566 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=239, Invalid=951, Unknown=0, NotChecked=0, Total=1190 [2019-11-23 20:51:09,566 INFO L87 Difference]: Start difference. First operand 74 states and 77 transitions. Second operand 35 states. [2019-11-23 20:51:10,278 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-23 20:51:10,278 INFO L93 Difference]: Finished difference Result 139 states and 144 transitions. [2019-11-23 20:51:10,278 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2019-11-23 20:51:10,279 INFO L78 Accepts]: Start accepts. Automaton has 35 states. Word has length 54 [2019-11-23 20:51:10,279 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-23 20:51:10,279 INFO L225 Difference]: With dead ends: 139 [2019-11-23 20:51:10,279 INFO L226 Difference]: Without dead ends: 106 [2019-11-23 20:51:10,280 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 86 GetRequests, 39 SyntacticMatches, 2 SemanticMatches, 45 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 616 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=514, Invalid=1648, Unknown=0, NotChecked=0, Total=2162 [2019-11-23 20:51:10,280 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 106 states. [2019-11-23 20:51:10,291 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 106 to 76. [2019-11-23 20:51:10,291 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 76 states. [2019-11-23 20:51:10,292 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 76 states to 76 states and 79 transitions. [2019-11-23 20:51:10,292 INFO L78 Accepts]: Start accepts. Automaton has 76 states and 79 transitions. Word has length 54 [2019-11-23 20:51:10,292 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-23 20:51:10,292 INFO L462 AbstractCegarLoop]: Abstraction has 76 states and 79 transitions. [2019-11-23 20:51:10,292 INFO L463 AbstractCegarLoop]: Interpolant automaton has 35 states. [2019-11-23 20:51:10,292 INFO L276 IsEmpty]: Start isEmpty. Operand 76 states and 79 transitions. [2019-11-23 20:51:10,293 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2019-11-23 20:51:10,293 INFO L402 BasicCegarLoop]: Found error trace [2019-11-23 20:51:10,293 INFO L410 BasicCegarLoop]: trace histogram [10, 10, 5, 5, 5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-23 20:51:10,499 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 22 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-23 20:51:10,499 INFO L410 AbstractCegarLoop]: === Iteration 25 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-23 20:51:10,499 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-23 20:51:10,499 INFO L82 PathProgramCache]: Analyzing trace with hash 1120346963, now seen corresponding path program 20 times [2019-11-23 20:51:10,500 INFO L163 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-23 20:51:10,500 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1825094248] [2019-11-23 20:51:10,500 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-23 20:51:10,523 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-23 20:51:10,897 INFO L134 CoverageAnalysis]: Checked inductivity of 157 backedges. 0 proven. 132 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2019-11-23 20:51:10,897 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1825094248] [2019-11-23 20:51:10,897 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1734489902] [2019-11-23 20:51:10,898 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 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-23 20:51:10,949 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2019-11-23 20:51:10,950 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-23 20:51:10,951 INFO L255 TraceCheckSpWp]: Trace formula consists of 195 conjuncts, 46 conjunts are in the unsatisfiable core [2019-11-23 20:51:10,952 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2019-11-23 20:51:10,957 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 8 [2019-11-23 20:51:10,957 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-23 20:51:10,970 INFO L567 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-23 20:51:10,971 INFO L496 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2019-11-23 20:51:10,971 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:15, output treesize:11 [2019-11-23 20:51:11,108 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:11,111 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:11,112 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:11,113 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 36 treesize of output 43 [2019-11-23 20:51:11,114 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-23 20:51:11,128 INFO L567 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-23 20:51:11,128 INFO L496 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2019-11-23 20:51:11,129 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 2 variables, input treesize:74, output treesize:52 [2019-11-23 20:51:11,478 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-23 20:51:11,529 INFO L134 CoverageAnalysis]: Checked inductivity of 157 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 100 trivial. 0 not checked. [2019-11-23 20:51:11,530 INFO L220 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-23 20:51:11,530 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 15] total 28 [2019-11-23 20:51:11,530 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [453705861] [2019-11-23 20:51:11,530 INFO L442 AbstractCegarLoop]: Interpolant automaton has 28 states [2019-11-23 20:51:11,530 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-23 20:51:11,531 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2019-11-23 20:51:11,531 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=100, Invalid=656, Unknown=0, NotChecked=0, Total=756 [2019-11-23 20:51:11,531 INFO L87 Difference]: Start difference. First operand 76 states and 79 transitions. Second operand 28 states. [2019-11-23 20:51:12,963 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-23 20:51:12,963 INFO L93 Difference]: Finished difference Result 106 states and 109 transitions. [2019-11-23 20:51:12,963 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 38 states. [2019-11-23 20:51:12,963 INFO L78 Accepts]: Start accepts. Automaton has 28 states. Word has length 56 [2019-11-23 20:51:12,964 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-23 20:51:12,964 INFO L225 Difference]: With dead ends: 106 [2019-11-23 20:51:12,964 INFO L226 Difference]: Without dead ends: 104 [2019-11-23 20:51:12,965 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 96 GetRequests, 46 SyntacticMatches, 4 SemanticMatches, 46 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 526 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=270, Invalid=1986, Unknown=0, NotChecked=0, Total=2256 [2019-11-23 20:51:12,965 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 104 states. [2019-11-23 20:51:12,977 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 104 to 76. [2019-11-23 20:51:12,978 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 76 states. [2019-11-23 20:51:12,978 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 76 states to 76 states and 79 transitions. [2019-11-23 20:51:12,978 INFO L78 Accepts]: Start accepts. Automaton has 76 states and 79 transitions. Word has length 56 [2019-11-23 20:51:12,978 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-23 20:51:12,978 INFO L462 AbstractCegarLoop]: Abstraction has 76 states and 79 transitions. [2019-11-23 20:51:12,978 INFO L463 AbstractCegarLoop]: Interpolant automaton has 28 states. [2019-11-23 20:51:12,978 INFO L276 IsEmpty]: Start isEmpty. Operand 76 states and 79 transitions. [2019-11-23 20:51:12,988 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2019-11-23 20:51:12,988 INFO L402 BasicCegarLoop]: Found error trace [2019-11-23 20:51:12,988 INFO L410 BasicCegarLoop]: trace histogram [8, 8, 7, 6, 6, 6, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-23 20:51:13,189 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 23 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-23 20:51:13,189 INFO L410 AbstractCegarLoop]: === Iteration 26 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-23 20:51:13,190 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-23 20:51:13,190 INFO L82 PathProgramCache]: Analyzing trace with hash -1377012955, now seen corresponding path program 21 times [2019-11-23 20:51:13,190 INFO L163 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-23 20:51:13,190 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [628425722] [2019-11-23 20:51:13,191 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-23 20:51:13,212 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-23 20:51:14,322 WARN L192 SmtUtils]: Spent 102.00 ms on a formula simplification. DAG size of input: 108 DAG size of output: 22 [2019-11-23 20:51:14,515 WARN L192 SmtUtils]: Spent 133.00 ms on a formula simplification. DAG size of input: 145 DAG size of output: 32 [2019-11-23 20:51:14,792 WARN L192 SmtUtils]: Spent 160.00 ms on a formula simplification. DAG size of input: 144 DAG size of output: 44 [2019-11-23 20:51:15,044 WARN L192 SmtUtils]: Spent 175.00 ms on a formula simplification. DAG size of input: 136 DAG size of output: 59 [2019-11-23 20:51:15,262 WARN L192 SmtUtils]: Spent 150.00 ms on a formula simplification. DAG size of input: 120 DAG size of output: 45 [2019-11-23 20:51:15,447 WARN L192 SmtUtils]: Spent 109.00 ms on a formula simplification. DAG size of input: 97 DAG size of output: 47 [2019-11-23 20:51:16,527 INFO L134 CoverageAnalysis]: Checked inductivity of 152 backedges. 3 proven. 149 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-11-23 20:51:16,527 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [628425722] [2019-11-23 20:51:16,527 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1670402659] [2019-11-23 20:51:16,527 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 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-23 20:51:16,672 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) [2019-11-23 20:51:16,672 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-23 20:51:16,674 INFO L255 TraceCheckSpWp]: Trace formula consists of 193 conjuncts, 54 conjunts are in the unsatisfiable core [2019-11-23 20:51:16,675 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2019-11-23 20:51:16,716 INFO L377 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-23 20:51:16,716 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-23 20:51:16,723 INFO L567 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-23 20:51:16,723 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-23 20:51:16,723 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 2 variables, input treesize:25, output treesize:10 [2019-11-23 20:51:16,727 INFO L377 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-23 20:51:16,727 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-23 20:51:16,736 INFO L567 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-23 20:51:16,737 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-23 20:51:16,737 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 2 variables, input treesize:28, output treesize:13 [2019-11-23 20:51:16,884 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:16,893 INFO L172 IndexEqualityManager]: detected equality via solver [2019-11-23 20:51:16,894 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:16,895 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:16,896 INFO L172 IndexEqualityManager]: detected equality via solver [2019-11-23 20:51:16,917 INFO L343 Elim1Store]: treesize reduction 44, result has 38.0 percent of original size [2019-11-23 20:51:16,917 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 3 case distinctions, treesize of input 46 treesize of output 53 [2019-11-23 20:51:16,918 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-23 20:51:16,933 INFO L567 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-23 20:51:16,933 INFO L496 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2019-11-23 20:51:16,934 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:92, output treesize:64 [2019-11-23 20:51:17,065 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:17,068 INFO L172 IndexEqualityManager]: detected equality via solver [2019-11-23 20:51:17,070 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:17,071 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:17,072 INFO L172 IndexEqualityManager]: detected equality via solver [2019-11-23 20:51:17,074 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:17,083 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:17,085 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:17,090 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:17,091 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:17,092 INFO L172 IndexEqualityManager]: detected equality via solver [2019-11-23 20:51:17,344 WARN L192 SmtUtils]: Spent 251.00 ms on a formula simplification. DAG size of input: 87 DAG size of output: 75 [2019-11-23 20:51:17,345 INFO L343 Elim1Store]: treesize reduction 77, result has 78.4 percent of original size [2019-11-23 20:51:17,346 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 6 select indices, 6 select index equivalence classes, 5 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 21 case distinctions, treesize of input 79 treesize of output 312 [2019-11-23 20:51:17,347 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 3 terms [2019-11-23 20:51:17,347 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-23 20:51:17,348 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-23 20:51:17,349 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-23 20:51:17,350 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-23 20:51:17,504 WARN L192 SmtUtils]: Spent 153.00 ms on a formula simplification. DAG size of input: 79 DAG size of output: 42 [2019-11-23 20:51:17,505 INFO L567 ElimStorePlain]: treesize reduction 427, result has 18.4 percent of original size [2019-11-23 20:51:17,505 INFO L496 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2019-11-23 20:51:17,506 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:124, output treesize:96 [2019-11-23 20:51:17,684 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:17,692 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:17,694 INFO L172 IndexEqualityManager]: detected equality via solver [2019-11-23 20:51:17,696 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:17,698 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:17,699 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:17,701 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:17,701 INFO L172 IndexEqualityManager]: detected equality via solver [2019-11-23 20:51:17,702 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:17,703 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:17,706 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:17,707 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:17,708 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:17,709 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:17,711 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:17,713 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:17,714 INFO L172 IndexEqualityManager]: detected equality via solver [2019-11-23 20:51:17,716 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:17,717 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:17,718 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:17,720 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:17,720 INFO L172 IndexEqualityManager]: detected equality via solver [2019-11-23 20:51:17,724 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:17,725 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:17,726 INFO L172 IndexEqualityManager]: detected equality via solver [2019-11-23 20:51:18,193 WARN L192 SmtUtils]: Spent 465.00 ms on a formula simplification. DAG size of input: 132 DAG size of output: 120 [2019-11-23 20:51:18,194 INFO L343 Elim1Store]: treesize reduction 79, result has 84.8 percent of original size [2019-11-23 20:51:18,194 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 10 select indices, 10 select index equivalence classes, 12 disjoint index pairs (out of 45 index pairs), introduced 10 new quantified variables, introduced 51 case distinctions, treesize of input 115 treesize of output 518 [2019-11-23 20:51:18,196 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-23 20:51:18,197 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 3 terms [2019-11-23 20:51:18,197 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-23 20:51:18,198 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-23 20:51:18,198 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 3 terms [2019-11-23 20:51:18,198 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-23 20:51:18,201 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 3 terms [2019-11-23 20:51:18,201 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 3 terms [2019-11-23 20:51:18,201 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-23 20:51:18,202 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 3 terms [2019-11-23 20:51:18,202 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-23 20:51:18,203 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-23 20:51:18,206 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-23 20:51:18,677 WARN L192 SmtUtils]: Spent 470.00 ms on a formula simplification. DAG size of input: 149 DAG size of output: 53 [2019-11-23 20:51:18,678 INFO L567 ElimStorePlain]: treesize reduction 3316, result has 3.8 percent of original size [2019-11-23 20:51:18,678 INFO L496 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2019-11-23 20:51:18,679 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:160, output treesize:132 [2019-11-23 20:51:18,888 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:18,901 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:18,903 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:18,906 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:18,908 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:18,910 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:18,913 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:18,915 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:18,917 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:18,918 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:18,920 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:18,922 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:18,923 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:18,925 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:18,927 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:18,930 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:18,932 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:18,934 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:18,936 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:18,940 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:18,942 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:18,944 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:18,946 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:18,948 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:18,950 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:18,952 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:18,954 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:18,956 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:18,958 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:18,962 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:18,966 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:18,968 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:18,970 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:18,973 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:18,976 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:18,978 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:18,980 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:18,982 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:18,984 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:18,987 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:18,988 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:18,990 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:18,993 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:18,995 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:18,997 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:18,999 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,001 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,002 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,005 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,007 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,008 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,009 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,013 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,015 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,017 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,019 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,022 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,383 INFO L237 Elim1Store]: Index analysis took 489 ms [2019-11-23 20:51:19,386 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,397 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,400 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,401 INFO L172 IndexEqualityManager]: detected equality via solver [2019-11-23 20:51:19,403 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,406 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,410 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,410 INFO L172 IndexEqualityManager]: detected equality via solver [2019-11-23 20:51:19,413 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,413 INFO L172 IndexEqualityManager]: detected equality via solver [2019-11-23 20:51:19,417 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,419 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,420 INFO L172 IndexEqualityManager]: detected equality via solver [2019-11-23 20:51:19,423 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,423 INFO L172 IndexEqualityManager]: detected equality via solver [2019-11-23 20:51:19,424 INFO L172 IndexEqualityManager]: detected equality via solver [2019-11-23 20:51:19,424 INFO L172 IndexEqualityManager]: detected equality via solver [2019-11-23 20:51:19,497 INFO L343 Elim1Store]: treesize reduction 44, result has 63.0 percent of original size [2019-11-23 20:51:19,498 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 14 select indices, 14 select index equivalence classes, 41 disjoint index pairs (out of 91 index pairs), introduced 14 new quantified variables, introduced 50 case distinctions, treesize of input 173 treesize of output 263 [2019-11-23 20:51:19,499 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-23 20:51:19,503 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,507 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,508 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,508 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,509 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,510 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,512 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,513 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,514 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,516 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,517 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,518 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,519 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,521 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,522 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,523 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,525 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,526 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,527 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,529 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,530 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,531 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,532 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,534 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,535 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,536 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,538 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,539 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,540 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,541 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,542 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,544 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,545 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,546 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,548 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,549 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,550 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,552 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,553 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,554 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,555 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,557 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,558 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,560 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,561 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,562 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,564 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,565 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,566 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,567 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,569 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,570 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,571 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,573 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,574 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,575 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,577 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,578 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:19,582 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 14 select indices, 14 select index equivalence classes, 57 disjoint index pairs (out of 91 index pairs), introduced 14 new quantified variables, introduced 0 case distinctions, treesize of input 177 treesize of output 219 [2019-11-23 20:51:19,583 INFO L496 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2019-11-23 20:51:19,724 WARN L192 SmtUtils]: Spent 140.00 ms on a formula simplification. DAG size of input: 76 DAG size of output: 66 [2019-11-23 20:51:19,725 INFO L567 ElimStorePlain]: treesize reduction 221, result has 43.5 percent of original size [2019-11-23 20:51:19,725 INFO L496 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2019-11-23 20:51:19,725 INFO L221 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:407, output treesize:170 [2019-11-23 20:51:21,184 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-23 20:51:21,277 INFO L134 CoverageAnalysis]: Checked inductivity of 152 backedges. 81 proven. 22 refuted. 0 times theorem prover too weak. 49 trivial. 0 not checked. [2019-11-23 20:51:21,277 INFO L220 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-23 20:51:21,277 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [29, 23] total 50 [2019-11-23 20:51:21,277 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2088552906] [2019-11-23 20:51:21,278 INFO L442 AbstractCegarLoop]: Interpolant automaton has 50 states [2019-11-23 20:51:21,278 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-23 20:51:21,278 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 50 interpolants. [2019-11-23 20:51:21,278 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=239, Invalid=2211, Unknown=0, NotChecked=0, Total=2450 [2019-11-23 20:51:21,279 INFO L87 Difference]: Start difference. First operand 76 states and 79 transitions. Second operand 50 states. [2019-11-23 20:51:24,302 WARN L192 SmtUtils]: Spent 107.00 ms on a formula simplification. DAG size of input: 110 DAG size of output: 64 [2019-11-23 20:51:24,600 WARN L192 SmtUtils]: Spent 174.00 ms on a formula simplification. DAG size of input: 121 DAG size of output: 64 [2019-11-23 20:51:24,852 WARN L192 SmtUtils]: Spent 167.00 ms on a formula simplification. DAG size of input: 110 DAG size of output: 65 [2019-11-23 20:51:25,201 WARN L192 SmtUtils]: Spent 144.00 ms on a formula simplification. DAG size of input: 130 DAG size of output: 66 [2019-11-23 20:51:25,541 WARN L192 SmtUtils]: Spent 153.00 ms on a formula simplification. DAG size of input: 132 DAG size of output: 69 [2019-11-23 20:51:25,955 WARN L192 SmtUtils]: Spent 193.00 ms on a formula simplification. DAG size of input: 141 DAG size of output: 66 [2019-11-23 20:51:26,435 WARN L192 SmtUtils]: Spent 180.00 ms on a formula simplification. DAG size of input: 144 DAG size of output: 64 [2019-11-23 20:51:26,987 WARN L192 SmtUtils]: Spent 192.00 ms on a formula simplification. DAG size of input: 124 DAG size of output: 67 [2019-11-23 20:51:27,409 WARN L192 SmtUtils]: Spent 179.00 ms on a formula simplification. DAG size of input: 113 DAG size of output: 68 [2019-11-23 20:51:27,768 WARN L192 SmtUtils]: Spent 186.00 ms on a formula simplification. DAG size of input: 129 DAG size of output: 72 [2019-11-23 20:51:28,096 WARN L192 SmtUtils]: Spent 184.00 ms on a formula simplification. DAG size of input: 123 DAG size of output: 70 [2019-11-23 20:51:28,419 WARN L192 SmtUtils]: Spent 170.00 ms on a formula simplification. DAG size of input: 123 DAG size of output: 71 [2019-11-23 20:51:28,672 WARN L192 SmtUtils]: Spent 169.00 ms on a formula simplification. DAG size of input: 109 DAG size of output: 72 [2019-11-23 20:51:28,687 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-23 20:51:28,687 INFO L93 Difference]: Finished difference Result 111 states and 116 transitions. [2019-11-23 20:51:28,688 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 56 states. [2019-11-23 20:51:28,688 INFO L78 Accepts]: Start accepts. Automaton has 50 states. Word has length 58 [2019-11-23 20:51:28,688 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-23 20:51:28,689 INFO L225 Difference]: With dead ends: 111 [2019-11-23 20:51:28,689 INFO L226 Difference]: Without dead ends: 65 [2019-11-23 20:51:28,693 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 132 GetRequests, 38 SyntacticMatches, 1 SemanticMatches, 93 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2009 ImplicationChecksByTransitivity, 10.8s TimeCoverageRelationStatistics Valid=1173, Invalid=7757, Unknown=0, NotChecked=0, Total=8930 [2019-11-23 20:51:28,693 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 65 states. [2019-11-23 20:51:28,705 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 65 to 61. [2019-11-23 20:51:28,706 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 61 states. [2019-11-23 20:51:28,706 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 61 states to 61 states and 63 transitions. [2019-11-23 20:51:28,706 INFO L78 Accepts]: Start accepts. Automaton has 61 states and 63 transitions. Word has length 58 [2019-11-23 20:51:28,706 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-23 20:51:28,707 INFO L462 AbstractCegarLoop]: Abstraction has 61 states and 63 transitions. [2019-11-23 20:51:28,707 INFO L463 AbstractCegarLoop]: Interpolant automaton has 50 states. [2019-11-23 20:51:28,707 INFO L276 IsEmpty]: Start isEmpty. Operand 61 states and 63 transitions. [2019-11-23 20:51:28,711 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2019-11-23 20:51:28,711 INFO L402 BasicCegarLoop]: Found error trace [2019-11-23 20:51:28,711 INFO L410 BasicCegarLoop]: trace histogram [10, 10, 6, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-23 20:51:28,911 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 24 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-11-23 20:51:28,912 INFO L410 AbstractCegarLoop]: === Iteration 27 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-23 20:51:28,912 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-23 20:51:28,912 INFO L82 PathProgramCache]: Analyzing trace with hash -2114418039, now seen corresponding path program 22 times [2019-11-23 20:51:28,913 INFO L163 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-23 20:51:28,913 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [785218426] [2019-11-23 20:51:28,913 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-23 20:51:28,948 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-23 20:51:30,115 WARN L192 SmtUtils]: Spent 106.00 ms on a formula simplification. DAG size of input: 106 DAG size of output: 30 [2019-11-23 20:51:30,291 WARN L192 SmtUtils]: Spent 122.00 ms on a formula simplification. DAG size of input: 113 DAG size of output: 36 [2019-11-23 20:51:30,454 WARN L192 SmtUtils]: Spent 107.00 ms on a formula simplification. DAG size of input: 112 DAG size of output: 37 [2019-11-23 20:51:30,629 WARN L192 SmtUtils]: Spent 112.00 ms on a formula simplification. DAG size of input: 110 DAG size of output: 36 [2019-11-23 20:51:31,829 INFO L134 CoverageAnalysis]: Checked inductivity of 175 backedges. 6 proven. 169 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-11-23 20:51:31,829 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [785218426] [2019-11-23 20:51:31,829 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1705183131] [2019-11-23 20:51:31,829 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 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-23 20:51:31,894 INFO L249 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2019-11-23 20:51:31,894 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-23 20:51:31,895 INFO L255 TraceCheckSpWp]: Trace formula consists of 154 conjuncts, 54 conjunts are in the unsatisfiable core [2019-11-23 20:51:31,897 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2019-11-23 20:51:31,907 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 8 [2019-11-23 20:51:31,908 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-23 20:51:31,912 INFO L567 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-23 20:51:31,913 INFO L496 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2019-11-23 20:51:31,913 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:15, output treesize:11 [2019-11-23 20:51:32,666 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-23 20:51:32,667 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-23 20:51:32,672 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:32,677 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:32,679 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:32,684 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 57 treesize of output 63 [2019-11-23 20:51:32,685 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-23 20:51:32,687 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:32,692 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:32,694 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-23 20:51:32,696 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 61 treesize of output 67 [2019-11-23 20:51:32,697 INFO L496 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2019-11-23 20:51:32,749 INFO L567 ElimStorePlain]: treesize reduction 70, result has 41.2 percent of original size [2019-11-23 20:51:32,750 INFO L496 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2019-11-23 20:51:32,751 INFO L221 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:163, output treesize:49 [2019-11-23 20:51:33,374 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-23 20:51:33,440 INFO L134 CoverageAnalysis]: Checked inductivity of 175 backedges. 0 proven. 175 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-11-23 20:51:33,440 INFO L220 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-23 20:51:33,440 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [30, 27] total 55 [2019-11-23 20:51:33,441 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [827557936] [2019-11-23 20:51:33,441 INFO L442 AbstractCegarLoop]: Interpolant automaton has 55 states [2019-11-23 20:51:33,441 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-23 20:51:33,442 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 55 interpolants. [2019-11-23 20:51:33,442 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=268, Invalid=2702, Unknown=0, NotChecked=0, Total=2970 [2019-11-23 20:51:33,442 INFO L87 Difference]: Start difference. First operand 61 states and 63 transitions. Second operand 55 states.