java -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerC.xml -s ../../../trunk/examples/settings/default/automizer/svcomp-Reach-32bit-Automizer_Default.epf -i ../../../trunk/examples/svcomp/array-crafted/zero_sum1.c -------------------------------------------------------------------------------- This is Ultimate 0.1.24-13a467a-m [2019-10-14 21:40:58,707 INFO L177 SettingsManager]: Resetting all preferences to default values... [2019-10-14 21:40:58,710 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2019-10-14 21:40:58,721 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2019-10-14 21:40:58,722 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2019-10-14 21:40:58,723 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2019-10-14 21:40:58,724 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2019-10-14 21:40:58,726 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2019-10-14 21:40:58,727 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2019-10-14 21:40:58,728 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2019-10-14 21:40:58,729 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2019-10-14 21:40:58,730 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2019-10-14 21:40:58,730 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2019-10-14 21:40:58,731 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2019-10-14 21:40:58,732 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2019-10-14 21:40:58,733 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2019-10-14 21:40:58,734 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2019-10-14 21:40:58,735 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2019-10-14 21:40:58,737 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2019-10-14 21:40:58,739 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2019-10-14 21:40:58,740 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2019-10-14 21:40:58,741 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2019-10-14 21:40:58,743 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2019-10-14 21:40:58,743 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2019-10-14 21:40:58,745 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2019-10-14 21:40:58,746 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2019-10-14 21:40:58,746 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2019-10-14 21:40:58,747 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2019-10-14 21:40:58,747 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2019-10-14 21:40:58,748 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2019-10-14 21:40:58,749 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2019-10-14 21:40:58,749 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2019-10-14 21:40:58,750 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2019-10-14 21:40:58,751 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2019-10-14 21:40:58,752 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2019-10-14 21:40:58,752 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2019-10-14 21:40:58,753 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2019-10-14 21:40:58,753 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2019-10-14 21:40:58,753 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2019-10-14 21:40:58,754 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2019-10-14 21:40:58,754 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2019-10-14 21:40:58,755 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-10-14 21:40:58,774 INFO L113 SettingsManager]: Loading preferences was successful [2019-10-14 21:40:58,774 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2019-10-14 21:40:58,776 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2019-10-14 21:40:58,776 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2019-10-14 21:40:58,776 INFO L138 SettingsManager]: * Use SBE=true [2019-10-14 21:40:58,777 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2019-10-14 21:40:58,777 INFO L138 SettingsManager]: * sizeof long=4 [2019-10-14 21:40:58,777 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2019-10-14 21:40:58,777 INFO L138 SettingsManager]: * sizeof POINTER=4 [2019-10-14 21:40:58,777 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2019-10-14 21:40:58,778 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2019-10-14 21:40:58,779 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2019-10-14 21:40:58,779 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2019-10-14 21:40:58,779 INFO L138 SettingsManager]: * sizeof long double=12 [2019-10-14 21:40:58,780 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2019-10-14 21:40:58,780 INFO L138 SettingsManager]: * Use constant arrays=true [2019-10-14 21:40:58,780 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2019-10-14 21:40:58,780 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2019-10-14 21:40:58,780 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2019-10-14 21:40:58,781 INFO L138 SettingsManager]: * To the following directory=./dump/ [2019-10-14 21:40:58,781 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2019-10-14 21:40:58,781 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2019-10-14 21:40:58,781 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2019-10-14 21:40:58,782 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2019-10-14 21:40:58,782 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2019-10-14 21:40:58,782 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2019-10-14 21:40:58,782 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2019-10-14 21:40:58,782 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2019-10-14 21:40:58,783 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2019-10-14 21:40:59,052 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2019-10-14 21:40:59,065 INFO L258 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2019-10-14 21:40:59,070 INFO L214 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2019-10-14 21:40:59,072 INFO L271 PluginConnector]: Initializing CDTParser... [2019-10-14 21:40:59,072 INFO L275 PluginConnector]: CDTParser initialized [2019-10-14 21:40:59,073 INFO L428 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/array-crafted/zero_sum1.c [2019-10-14 21:40:59,146 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/2ea7e8931/52749de013e4484281cb16322aaf2aca/FLAG1272ddd49 [2019-10-14 21:40:59,574 INFO L306 CDTParser]: Found 1 translation units. [2019-10-14 21:40:59,575 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/array-crafted/zero_sum1.c [2019-10-14 21:40:59,581 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/2ea7e8931/52749de013e4484281cb16322aaf2aca/FLAG1272ddd49 [2019-10-14 21:40:59,980 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/2ea7e8931/52749de013e4484281cb16322aaf2aca [2019-10-14 21:40:59,990 INFO L296 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2019-10-14 21:40:59,992 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2019-10-14 21:40:59,993 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2019-10-14 21:40:59,993 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2019-10-14 21:40:59,996 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2019-10-14 21:40:59,997 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.10 09:40:59" (1/1) ... [2019-10-14 21:41:00,000 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@bfc0887 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.10 09:40:59, skipping insertion in model container [2019-10-14 21:41:00,000 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.10 09:40:59" (1/1) ... [2019-10-14 21:41:00,007 INFO L142 MainTranslator]: Starting translation in SV-COMP mode [2019-10-14 21:41:00,020 INFO L173 MainTranslator]: Built tables and reachable declarations [2019-10-14 21:41:00,186 INFO L206 PostProcessor]: Analyzing one entry point: main [2019-10-14 21:41:00,190 INFO L188 MainTranslator]: Completed pre-run [2019-10-14 21:41:00,212 INFO L206 PostProcessor]: Analyzing one entry point: main [2019-10-14 21:41:00,231 INFO L192 MainTranslator]: Completed translation [2019-10-14 21:41:00,231 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.10 09:41:00 WrapperNode [2019-10-14 21:41:00,231 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2019-10-14 21:41:00,232 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2019-10-14 21:41:00,232 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2019-10-14 21:41:00,232 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2019-10-14 21:41:00,328 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.10 09:41:00" (1/1) ... [2019-10-14 21:41:00,328 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.10 09:41:00" (1/1) ... [2019-10-14 21:41:00,335 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.10 09:41:00" (1/1) ... [2019-10-14 21:41:00,335 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.10 09:41:00" (1/1) ... [2019-10-14 21:41:00,341 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.10 09:41:00" (1/1) ... [2019-10-14 21:41:00,346 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.10 09:41:00" (1/1) ... [2019-10-14 21:41:00,349 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.10 09:41:00" (1/1) ... [2019-10-14 21:41:00,354 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2019-10-14 21:41:00,355 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2019-10-14 21:41:00,355 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2019-10-14 21:41:00,355 INFO L275 PluginConnector]: RCFGBuilder initialized [2019-10-14 21:41:00,356 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.10 09:41: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-10-14 21:41:00,415 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2019-10-14 21:41:00,415 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2019-10-14 21:41:00,416 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2019-10-14 21:41:00,416 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2019-10-14 21:41:00,416 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_error [2019-10-14 21:41:00,416 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assume [2019-10-14 21:41:00,416 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2019-10-14 21:41:00,416 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_short [2019-10-14 21:41:00,417 INFO L130 BoogieDeclarations]: Found specification of procedure main [2019-10-14 21:41:00,417 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2019-10-14 21:41:00,417 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2019-10-14 21:41:00,417 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2019-10-14 21:41:00,417 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2019-10-14 21:41:00,417 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2019-10-14 21:41:00,418 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2019-10-14 21:41:00,694 INFO L279 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2019-10-14 21:41:00,695 INFO L284 CfgBuilder]: Removed 3 assume(true) statements. [2019-10-14 21:41:00,697 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.10 09:41:00 BoogieIcfgContainer [2019-10-14 21:41:00,698 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2019-10-14 21:41:00,699 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2019-10-14 21:41:00,699 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2019-10-14 21:41:00,707 INFO L275 PluginConnector]: TraceAbstraction initialized [2019-10-14 21:41:00,708 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 14.10 09:40:59" (1/3) ... [2019-10-14 21:41:00,709 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1d05f386 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.10 09:41:00, skipping insertion in model container [2019-10-14 21:41:00,709 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.10 09:41:00" (2/3) ... [2019-10-14 21:41:00,709 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1d05f386 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.10 09:41:00, skipping insertion in model container [2019-10-14 21:41:00,709 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.10 09:41:00" (3/3) ... [2019-10-14 21:41:00,717 INFO L109 eAbstractionObserver]: Analyzing ICFG zero_sum1.c [2019-10-14 21:41:00,731 INFO L152 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2019-10-14 21:41:00,741 INFO L164 ceAbstractionStarter]: Appying trace abstraction to program that has 1 error locations. [2019-10-14 21:41:00,754 INFO L249 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2019-10-14 21:41:00,780 INFO L373 AbstractCegarLoop]: Interprodecural is true [2019-10-14 21:41:00,780 INFO L374 AbstractCegarLoop]: Hoare is true [2019-10-14 21:41:00,780 INFO L375 AbstractCegarLoop]: Compute interpolants for FPandBP [2019-10-14 21:41:00,781 INFO L376 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2019-10-14 21:41:00,781 INFO L377 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2019-10-14 21:41:00,781 INFO L378 AbstractCegarLoop]: Difference is false [2019-10-14 21:41:00,781 INFO L379 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2019-10-14 21:41:00,781 INFO L383 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2019-10-14 21:41:00,796 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states. [2019-10-14 21:41:00,801 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2019-10-14 21:41:00,801 INFO L372 BasicCegarLoop]: Found error trace [2019-10-14 21:41:00,802 INFO L380 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-10-14 21:41:00,804 INFO L410 AbstractCegarLoop]: === Iteration 1 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-10-14 21:41:00,808 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-10-14 21:41:00,808 INFO L82 PathProgramCache]: Analyzing trace with hash -714575113, now seen corresponding path program 1 times [2019-10-14 21:41:00,815 INFO L157 tionRefinementEngine]: Executing refinement strategy CAMEL [2019-10-14 21:41:00,815 INFO L342 tionRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [396283663] [2019-10-14 21:41:00,815 INFO L116 rtionOrderModulation]: Craig_NestedInterpolation forces the order to NOT_INCREMENTALLY [2019-10-14 21:41:00,815 INFO L116 rtionOrderModulation]: Craig_NestedInterpolation forces the order to NOT_INCREMENTALLY [2019-10-14 21:41:00,816 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-10-14 21:41:00,905 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-10-14 21:41:00,988 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-10-14 21:41:00,998 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-10-14 21:41:00,999 INFO L342 tionRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [396283663] [2019-10-14 21:41:00,999 INFO L223 tionRefinementEngine]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2019-10-14 21:41:01,000 INFO L236 tionRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2019-10-14 21:41:01,000 INFO L342 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1537318818] [2019-10-14 21:41:01,004 INFO L442 AbstractCegarLoop]: Interpolant automaton has 3 states [2019-10-14 21:41:01,004 INFO L137 tionRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-10-14 21:41:01,014 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2019-10-14 21:41:01,014 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2019-10-14 21:41:01,017 INFO L87 Difference]: Start difference. First operand 28 states. Second operand 3 states. [2019-10-14 21:41:01,101 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-10-14 21:41:01,102 INFO L93 Difference]: Finished difference Result 47 states and 59 transitions. [2019-10-14 21:41:01,102 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2019-10-14 21:41:01,104 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 16 [2019-10-14 21:41:01,104 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-10-14 21:41:01,112 INFO L225 Difference]: With dead ends: 47 [2019-10-14 21:41:01,112 INFO L226 Difference]: Without dead ends: 20 [2019-10-14 21:41:01,116 INFO L600 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2019-10-14 21:41:01,134 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 20 states. [2019-10-14 21:41:01,159 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 20 to 20. [2019-10-14 21:41:01,161 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 20 states. [2019-10-14 21:41:01,164 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 22 transitions. [2019-10-14 21:41:01,166 INFO L78 Accepts]: Start accepts. Automaton has 20 states and 22 transitions. Word has length 16 [2019-10-14 21:41:01,166 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-10-14 21:41:01,167 INFO L462 AbstractCegarLoop]: Abstraction has 20 states and 22 transitions. [2019-10-14 21:41:01,167 INFO L463 AbstractCegarLoop]: Interpolant automaton has 3 states. [2019-10-14 21:41:01,167 INFO L276 IsEmpty]: Start isEmpty. Operand 20 states and 22 transitions. [2019-10-14 21:41:01,169 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2019-10-14 21:41:01,170 INFO L372 BasicCegarLoop]: Found error trace [2019-10-14 21:41:01,170 INFO L380 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-10-14 21:41:01,170 INFO L410 AbstractCegarLoop]: === Iteration 2 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-10-14 21:41:01,171 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-10-14 21:41:01,172 INFO L82 PathProgramCache]: Analyzing trace with hash 504621157, now seen corresponding path program 1 times [2019-10-14 21:41:01,172 INFO L157 tionRefinementEngine]: Executing refinement strategy CAMEL [2019-10-14 21:41:01,172 INFO L342 tionRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [675065815] [2019-10-14 21:41:01,172 INFO L116 rtionOrderModulation]: Craig_NestedInterpolation forces the order to NOT_INCREMENTALLY [2019-10-14 21:41:01,173 INFO L116 rtionOrderModulation]: Craig_NestedInterpolation forces the order to NOT_INCREMENTALLY [2019-10-14 21:41:01,173 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-10-14 21:41:01,230 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-10-14 21:41:01,313 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-10-14 21:41:01,325 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-10-14 21:41:01,326 INFO L342 tionRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [675065815] [2019-10-14 21:41:01,328 INFO L223 tionRefinementEngine]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2019-10-14 21:41:01,328 INFO L236 tionRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2019-10-14 21:41:01,328 INFO L342 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [116062336] [2019-10-14 21:41:01,331 INFO L442 AbstractCegarLoop]: Interpolant automaton has 6 states [2019-10-14 21:41:01,331 INFO L137 tionRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-10-14 21:41:01,331 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2019-10-14 21:41:01,332 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2019-10-14 21:41:01,332 INFO L87 Difference]: Start difference. First operand 20 states and 22 transitions. Second operand 6 states. [2019-10-14 21:41:01,467 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-10-14 21:41:01,467 INFO L93 Difference]: Finished difference Result 28 states and 31 transitions. [2019-10-14 21:41:01,468 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2019-10-14 21:41:01,468 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 16 [2019-10-14 21:41:01,468 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-10-14 21:41:01,470 INFO L225 Difference]: With dead ends: 28 [2019-10-14 21:41:01,470 INFO L226 Difference]: Without dead ends: 23 [2019-10-14 21:41:01,471 INFO L600 BasicCegarLoop]: 0 DeclaredPredicates, 9 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=19, Invalid=37, Unknown=0, NotChecked=0, Total=56 [2019-10-14 21:41:01,472 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states. [2019-10-14 21:41:01,480 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 23. [2019-10-14 21:41:01,480 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 23 states. [2019-10-14 21:41:01,481 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 26 transitions. [2019-10-14 21:41:01,482 INFO L78 Accepts]: Start accepts. Automaton has 23 states and 26 transitions. Word has length 16 [2019-10-14 21:41:01,482 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-10-14 21:41:01,482 INFO L462 AbstractCegarLoop]: Abstraction has 23 states and 26 transitions. [2019-10-14 21:41:01,483 INFO L463 AbstractCegarLoop]: Interpolant automaton has 6 states. [2019-10-14 21:41:01,483 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 26 transitions. [2019-10-14 21:41:01,484 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2019-10-14 21:41:01,484 INFO L372 BasicCegarLoop]: Found error trace [2019-10-14 21:41:01,485 INFO L380 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-10-14 21:41:01,486 INFO L410 AbstractCegarLoop]: === Iteration 3 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-10-14 21:41:01,487 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-10-14 21:41:01,487 INFO L82 PathProgramCache]: Analyzing trace with hash 626778659, now seen corresponding path program 1 times [2019-10-14 21:41:01,487 INFO L157 tionRefinementEngine]: Executing refinement strategy CAMEL [2019-10-14 21:41:01,487 INFO L342 tionRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1729490030] [2019-10-14 21:41:01,487 INFO L116 rtionOrderModulation]: Craig_NestedInterpolation forces the order to NOT_INCREMENTALLY [2019-10-14 21:41:01,488 INFO L116 rtionOrderModulation]: Craig_NestedInterpolation forces the order to NOT_INCREMENTALLY [2019-10-14 21:41:01,488 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-10-14 21:41:01,527 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-10-14 21:41:01,565 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-10-14 21:41:01,569 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2019-10-14 21:41:01,569 INFO L342 tionRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1729490030] [2019-10-14 21:41:01,570 INFO L223 tionRefinementEngine]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2019-10-14 21:41:01,570 INFO L236 tionRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2019-10-14 21:41:01,570 INFO L342 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2093017687] [2019-10-14 21:41:01,570 INFO L442 AbstractCegarLoop]: Interpolant automaton has 4 states [2019-10-14 21:41:01,571 INFO L137 tionRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-10-14 21:41:01,571 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2019-10-14 21:41:01,571 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2019-10-14 21:41:01,571 INFO L87 Difference]: Start difference. First operand 23 states and 26 transitions. Second operand 4 states. [2019-10-14 21:41:01,625 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-10-14 21:41:01,625 INFO L93 Difference]: Finished difference Result 39 states and 45 transitions. [2019-10-14 21:41:01,626 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2019-10-14 21:41:01,626 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 18 [2019-10-14 21:41:01,626 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-10-14 21:41:01,627 INFO L225 Difference]: With dead ends: 39 [2019-10-14 21:41:01,627 INFO L226 Difference]: Without dead ends: 25 [2019-10-14 21:41:01,628 INFO L600 BasicCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2019-10-14 21:41:01,628 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states. [2019-10-14 21:41:01,633 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 24. [2019-10-14 21:41:01,633 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 24 states. [2019-10-14 21:41:01,634 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 27 transitions. [2019-10-14 21:41:01,634 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 27 transitions. Word has length 18 [2019-10-14 21:41:01,635 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-10-14 21:41:01,635 INFO L462 AbstractCegarLoop]: Abstraction has 24 states and 27 transitions. [2019-10-14 21:41:01,635 INFO L463 AbstractCegarLoop]: Interpolant automaton has 4 states. [2019-10-14 21:41:01,635 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 27 transitions. [2019-10-14 21:41:01,636 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2019-10-14 21:41:01,636 INFO L372 BasicCegarLoop]: Found error trace [2019-10-14 21:41:01,636 INFO L380 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-10-14 21:41:01,637 INFO L410 AbstractCegarLoop]: === Iteration 4 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-10-14 21:41:01,637 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-10-14 21:41:01,637 INFO L82 PathProgramCache]: Analyzing trace with hash 1697854689, now seen corresponding path program 1 times [2019-10-14 21:41:01,637 INFO L157 tionRefinementEngine]: Executing refinement strategy CAMEL [2019-10-14 21:41:01,638 INFO L342 tionRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [173205432] [2019-10-14 21:41:01,638 INFO L116 rtionOrderModulation]: Craig_NestedInterpolation forces the order to NOT_INCREMENTALLY [2019-10-14 21:41:01,638 INFO L116 rtionOrderModulation]: Craig_NestedInterpolation forces the order to NOT_INCREMENTALLY [2019-10-14 21:41:01,638 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-10-14 21:41:01,662 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-10-14 21:41:01,734 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-10-14 21:41:01,738 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2019-10-14 21:41:01,738 INFO L342 tionRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [173205432] [2019-10-14 21:41:01,739 INFO L223 tionRefinementEngine]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2019-10-14 21:41:01,739 INFO L236 tionRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2019-10-14 21:41:01,739 INFO L342 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [501695485] [2019-10-14 21:41:01,740 INFO L442 AbstractCegarLoop]: Interpolant automaton has 5 states [2019-10-14 21:41:01,740 INFO L137 tionRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-10-14 21:41:01,740 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2019-10-14 21:41:01,741 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2019-10-14 21:41:01,741 INFO L87 Difference]: Start difference. First operand 24 states and 27 transitions. Second operand 5 states. [2019-10-14 21:41:01,839 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-10-14 21:41:01,839 INFO L93 Difference]: Finished difference Result 34 states and 38 transitions. [2019-10-14 21:41:01,840 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2019-10-14 21:41:01,840 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 20 [2019-10-14 21:41:01,840 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-10-14 21:41:01,841 INFO L225 Difference]: With dead ends: 34 [2019-10-14 21:41:01,841 INFO L226 Difference]: Without dead ends: 25 [2019-10-14 21:41:01,841 INFO L600 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2019-10-14 21:41:01,842 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states. [2019-10-14 21:41:01,846 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 23. [2019-10-14 21:41:01,846 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 23 states. [2019-10-14 21:41:01,847 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 25 transitions. [2019-10-14 21:41:01,847 INFO L78 Accepts]: Start accepts. Automaton has 23 states and 25 transitions. Word has length 20 [2019-10-14 21:41:01,847 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-10-14 21:41:01,848 INFO L462 AbstractCegarLoop]: Abstraction has 23 states and 25 transitions. [2019-10-14 21:41:01,848 INFO L463 AbstractCegarLoop]: Interpolant automaton has 5 states. [2019-10-14 21:41:01,848 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 25 transitions. [2019-10-14 21:41:01,848 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2019-10-14 21:41:01,849 INFO L372 BasicCegarLoop]: Found error trace [2019-10-14 21:41:01,849 INFO L380 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-10-14 21:41:01,849 INFO L410 AbstractCegarLoop]: === Iteration 5 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-10-14 21:41:01,849 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-10-14 21:41:01,850 INFO L82 PathProgramCache]: Analyzing trace with hash 661319647, now seen corresponding path program 1 times [2019-10-14 21:41:01,850 INFO L157 tionRefinementEngine]: Executing refinement strategy CAMEL [2019-10-14 21:41:01,850 INFO L342 tionRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [55599304] [2019-10-14 21:41:01,850 INFO L116 rtionOrderModulation]: Craig_NestedInterpolation forces the order to NOT_INCREMENTALLY [2019-10-14 21:41:01,850 INFO L116 rtionOrderModulation]: Craig_NestedInterpolation forces the order to NOT_INCREMENTALLY [2019-10-14 21:41:01,851 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-10-14 21:41:01,866 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-10-14 21:41:01,915 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-10-14 21:41:01,921 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2019-10-14 21:41:01,921 INFO L342 tionRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [55599304] [2019-10-14 21:41:01,922 INFO L342 tionRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1491412888] [2019-10-14 21:41:01,922 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-10-14 21:41:01,968 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-10-14 21:41:01,970 INFO L256 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 4 conjunts are in the unsatisfiable core [2019-10-14 21:41:01,976 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2019-10-14 21:41:02,033 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2019-10-14 21:41:02,034 INFO L223 tionRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-10-14 21:41:02,034 INFO L236 tionRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 4] total 7 [2019-10-14 21:41:02,034 INFO L342 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1279778457] [2019-10-14 21:41:02,035 INFO L442 AbstractCegarLoop]: Interpolant automaton has 7 states [2019-10-14 21:41:02,035 INFO L137 tionRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-10-14 21:41:02,035 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2019-10-14 21:41:02,036 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=25, Unknown=0, NotChecked=0, Total=42 [2019-10-14 21:41:02,036 INFO L87 Difference]: Start difference. First operand 23 states and 25 transitions. Second operand 7 states. [2019-10-14 21:41:02,114 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-10-14 21:41:02,114 INFO L93 Difference]: Finished difference Result 39 states and 43 transitions. [2019-10-14 21:41:02,115 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2019-10-14 21:41:02,115 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 22 [2019-10-14 21:41:02,115 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-10-14 21:41:02,116 INFO L225 Difference]: With dead ends: 39 [2019-10-14 21:41:02,116 INFO L226 Difference]: Without dead ends: 26 [2019-10-14 21:41:02,117 INFO L600 BasicCegarLoop]: 0 DeclaredPredicates, 27 GetRequests, 22 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=25, Unknown=0, NotChecked=0, Total=42 [2019-10-14 21:41:02,117 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26 states. [2019-10-14 21:41:02,125 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26 to 25. [2019-10-14 21:41:02,126 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 25 states. [2019-10-14 21:41:02,128 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 25 states to 25 states and 27 transitions. [2019-10-14 21:41:02,129 INFO L78 Accepts]: Start accepts. Automaton has 25 states and 27 transitions. Word has length 22 [2019-10-14 21:41:02,129 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-10-14 21:41:02,129 INFO L462 AbstractCegarLoop]: Abstraction has 25 states and 27 transitions. [2019-10-14 21:41:02,129 INFO L463 AbstractCegarLoop]: Interpolant automaton has 7 states. [2019-10-14 21:41:02,129 INFO L276 IsEmpty]: Start isEmpty. Operand 25 states and 27 transitions. [2019-10-14 21:41:02,131 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2019-10-14 21:41:02,131 INFO L372 BasicCegarLoop]: Found error trace [2019-10-14 21:41:02,131 INFO L380 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-10-14 21:41:02,332 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-10-14 21:41:02,333 INFO L410 AbstractCegarLoop]: === Iteration 6 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-10-14 21:41:02,333 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-10-14 21:41:02,333 INFO L82 PathProgramCache]: Analyzing trace with hash 834581405, now seen corresponding path program 2 times [2019-10-14 21:41:02,334 INFO L157 tionRefinementEngine]: Executing refinement strategy CAMEL [2019-10-14 21:41:02,334 INFO L342 tionRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2014630083] [2019-10-14 21:41:02,334 INFO L116 rtionOrderModulation]: Craig_NestedInterpolation forces the order to NOT_INCREMENTALLY [2019-10-14 21:41:02,335 INFO L116 rtionOrderModulation]: Craig_NestedInterpolation forces the order to NOT_INCREMENTALLY [2019-10-14 21:41:02,335 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-10-14 21:41:02,358 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-10-14 21:41:02,420 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-10-14 21:41:02,424 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2019-10-14 21:41:02,424 INFO L342 tionRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2014630083] [2019-10-14 21:41:02,424 INFO L342 tionRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [967195592] [2019-10-14 21:41:02,425 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-10-14 21:41:02,478 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2019-10-14 21:41:02,478 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-10-14 21:41:02,479 INFO L256 TraceCheckSpWp]: Trace formula consists of 92 conjuncts, 4 conjunts are in the unsatisfiable core [2019-10-14 21:41:02,481 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2019-10-14 21:41:02,515 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2019-10-14 21:41:02,515 INFO L223 tionRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-10-14 21:41:02,515 INFO L236 tionRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 5] total 8 [2019-10-14 21:41:02,516 INFO L342 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1432743653] [2019-10-14 21:41:02,520 INFO L442 AbstractCegarLoop]: Interpolant automaton has 8 states [2019-10-14 21:41:02,520 INFO L137 tionRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-10-14 21:41:02,521 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2019-10-14 21:41:02,521 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=34, Unknown=0, NotChecked=0, Total=56 [2019-10-14 21:41:02,521 INFO L87 Difference]: Start difference. First operand 25 states and 27 transitions. Second operand 8 states. [2019-10-14 21:41:02,630 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-10-14 21:41:02,631 INFO L93 Difference]: Finished difference Result 40 states and 44 transitions. [2019-10-14 21:41:02,631 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2019-10-14 21:41:02,631 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 24 [2019-10-14 21:41:02,631 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-10-14 21:41:02,632 INFO L225 Difference]: With dead ends: 40 [2019-10-14 21:41:02,632 INFO L226 Difference]: Without dead ends: 31 [2019-10-14 21:41:02,633 INFO L600 BasicCegarLoop]: 0 DeclaredPredicates, 32 GetRequests, 23 SyntacticMatches, 1 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2019-10-14 21:41:02,633 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2019-10-14 21:41:02,637 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 29. [2019-10-14 21:41:02,637 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 29 states. [2019-10-14 21:41:02,638 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 31 transitions. [2019-10-14 21:41:02,638 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 31 transitions. Word has length 24 [2019-10-14 21:41:02,638 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-10-14 21:41:02,639 INFO L462 AbstractCegarLoop]: Abstraction has 29 states and 31 transitions. [2019-10-14 21:41:02,639 INFO L463 AbstractCegarLoop]: Interpolant automaton has 8 states. [2019-10-14 21:41:02,639 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 31 transitions. [2019-10-14 21:41:02,639 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2019-10-14 21:41:02,640 INFO L372 BasicCegarLoop]: Found error trace [2019-10-14 21:41:02,640 INFO L380 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-10-14 21:41:02,843 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-10-14 21:41:02,844 INFO L410 AbstractCegarLoop]: === Iteration 7 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-10-14 21:41:02,844 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-10-14 21:41:02,844 INFO L82 PathProgramCache]: Analyzing trace with hash -1106988071, now seen corresponding path program 3 times [2019-10-14 21:41:02,845 INFO L157 tionRefinementEngine]: Executing refinement strategy CAMEL [2019-10-14 21:41:02,846 INFO L342 tionRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [297502442] [2019-10-14 21:41:02,846 INFO L116 rtionOrderModulation]: Craig_NestedInterpolation forces the order to NOT_INCREMENTALLY [2019-10-14 21:41:02,846 INFO L116 rtionOrderModulation]: Craig_NestedInterpolation forces the order to NOT_INCREMENTALLY [2019-10-14 21:41:02,846 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-10-14 21:41:02,882 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-10-14 21:41:03,456 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-10-14 21:41:03,463 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-10-14 21:41:03,463 INFO L342 tionRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [297502442] [2019-10-14 21:41:03,463 INFO L342 tionRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [152285153] [2019-10-14 21:41:03,464 INFO L92 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-10-14 21:41:03,512 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2019-10-14 21:41:03,512 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-10-14 21:41:03,513 INFO L256 TraceCheckSpWp]: Trace formula consists of 102 conjuncts, 33 conjunts are in the unsatisfiable core [2019-10-14 21:41:03,516 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2019-10-14 21:41:04,121 INFO L341 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2019-10-14 21:41:04,121 INFO L375 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 17 treesize of output 18 [2019-10-14 21:41:04,123 INFO L496 ElimStorePlain]: Start of recursive call 2: 1 dim-0 vars, End of recursive call: 1 dim-0 vars, and 2 xjuncts. [2019-10-14 21:41:04,134 INFO L567 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-10-14 21:41:04,136 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-10-14 21:41:04,140 INFO L496 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2019-10-14 21:41:04,141 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 3 variables, input treesize:32, output treesize:31 [2019-10-14 21:41:04,200 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-10-14 21:41:04,260 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-10-14 21:41:04,273 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-10-14 21:41:04,337 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-10-14 21:41:04,339 INFO L223 tionRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-10-14 21:41:04,339 INFO L236 tionRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 20] total 33 [2019-10-14 21:41:04,339 INFO L342 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1549772104] [2019-10-14 21:41:04,340 INFO L442 AbstractCegarLoop]: Interpolant automaton has 33 states [2019-10-14 21:41:04,340 INFO L137 tionRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-10-14 21:41:04,340 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2019-10-14 21:41:04,341 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=114, Invalid=942, Unknown=0, NotChecked=0, Total=1056 [2019-10-14 21:41:04,341 INFO L87 Difference]: Start difference. First operand 29 states and 31 transitions. Second operand 33 states. [2019-10-14 21:41:05,200 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-10-14 21:41:05,200 INFO L93 Difference]: Finished difference Result 60 states and 66 transitions. [2019-10-14 21:41:05,201 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2019-10-14 21:41:05,201 INFO L78 Accepts]: Start accepts. Automaton has 33 states. Word has length 28 [2019-10-14 21:41:05,201 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-10-14 21:41:05,202 INFO L225 Difference]: With dead ends: 60 [2019-10-14 21:41:05,202 INFO L226 Difference]: Without dead ends: 54 [2019-10-14 21:41:05,203 INFO L600 BasicCegarLoop]: 0 DeclaredPredicates, 58 GetRequests, 12 SyntacticMatches, 3 SemanticMatches, 43 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 493 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=201, Invalid=1779, Unknown=0, NotChecked=0, Total=1980 [2019-10-14 21:41:05,204 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2019-10-14 21:41:05,211 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 34. [2019-10-14 21:41:05,212 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 34 states. [2019-10-14 21:41:05,212 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 37 transitions. [2019-10-14 21:41:05,213 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 37 transitions. Word has length 28 [2019-10-14 21:41:05,213 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-10-14 21:41:05,213 INFO L462 AbstractCegarLoop]: Abstraction has 34 states and 37 transitions. [2019-10-14 21:41:05,213 INFO L463 AbstractCegarLoop]: Interpolant automaton has 33 states. [2019-10-14 21:41:05,213 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 37 transitions. [2019-10-14 21:41:05,214 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2019-10-14 21:41:05,214 INFO L372 BasicCegarLoop]: Found error trace [2019-10-14 21:41:05,214 INFO L380 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-10-14 21:41:05,415 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 4 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-10-14 21:41:05,416 INFO L410 AbstractCegarLoop]: === Iteration 8 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-10-14 21:41:05,416 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-10-14 21:41:05,417 INFO L82 PathProgramCache]: Analyzing trace with hash -1941462889, now seen corresponding path program 4 times [2019-10-14 21:41:05,417 INFO L157 tionRefinementEngine]: Executing refinement strategy CAMEL [2019-10-14 21:41:05,417 INFO L342 tionRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [277676293] [2019-10-14 21:41:05,418 INFO L116 rtionOrderModulation]: Craig_NestedInterpolation forces the order to NOT_INCREMENTALLY [2019-10-14 21:41:05,418 INFO L116 rtionOrderModulation]: Craig_NestedInterpolation forces the order to NOT_INCREMENTALLY [2019-10-14 21:41:05,418 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-10-14 21:41:05,431 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-10-14 21:41:05,496 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-10-14 21:41:05,506 INFO L134 CoverageAnalysis]: Checked inductivity of 17 backedges. 6 proven. 7 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2019-10-14 21:41:05,507 INFO L342 tionRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [277676293] [2019-10-14 21:41:05,507 INFO L342 tionRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1743912256] [2019-10-14 21:41:05,507 INFO L92 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-10-14 21:41:05,550 INFO L249 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2019-10-14 21:41:05,551 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-10-14 21:41:05,551 INFO L256 TraceCheckSpWp]: Trace formula consists of 95 conjuncts, 8 conjunts are in the unsatisfiable core [2019-10-14 21:41:05,553 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2019-10-14 21:41:05,611 INFO L134 CoverageAnalysis]: Checked inductivity of 17 backedges. 9 proven. 4 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2019-10-14 21:41:05,612 INFO L223 tionRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-10-14 21:41:05,612 INFO L236 tionRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 9] total 14 [2019-10-14 21:41:05,612 INFO L342 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1684894828] [2019-10-14 21:41:05,613 INFO L442 AbstractCegarLoop]: Interpolant automaton has 14 states [2019-10-14 21:41:05,614 INFO L137 tionRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-10-14 21:41:05,614 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2019-10-14 21:41:05,614 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=43, Invalid=139, Unknown=0, NotChecked=0, Total=182 [2019-10-14 21:41:05,614 INFO L87 Difference]: Start difference. First operand 34 states and 37 transitions. Second operand 14 states. [2019-10-14 21:41:05,805 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-10-14 21:41:05,805 INFO L93 Difference]: Finished difference Result 62 states and 68 transitions. [2019-10-14 21:41:05,807 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2019-10-14 21:41:05,808 INFO L78 Accepts]: Start accepts. Automaton has 14 states. Word has length 30 [2019-10-14 21:41:05,808 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-10-14 21:41:05,808 INFO L225 Difference]: With dead ends: 62 [2019-10-14 21:41:05,808 INFO L226 Difference]: Without dead ends: 37 [2019-10-14 21:41:05,809 INFO L600 BasicCegarLoop]: 0 DeclaredPredicates, 45 GetRequests, 28 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 54 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=77, Invalid=265, Unknown=0, NotChecked=0, Total=342 [2019-10-14 21:41:05,809 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2019-10-14 21:41:05,818 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 36. [2019-10-14 21:41:05,819 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 36 states. [2019-10-14 21:41:05,819 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 39 transitions. [2019-10-14 21:41:05,819 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 39 transitions. Word has length 30 [2019-10-14 21:41:05,820 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-10-14 21:41:05,820 INFO L462 AbstractCegarLoop]: Abstraction has 36 states and 39 transitions. [2019-10-14 21:41:05,820 INFO L463 AbstractCegarLoop]: Interpolant automaton has 14 states. [2019-10-14 21:41:05,820 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 39 transitions. [2019-10-14 21:41:05,821 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2019-10-14 21:41:05,821 INFO L372 BasicCegarLoop]: Found error trace [2019-10-14 21:41:05,821 INFO L380 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-10-14 21:41:06,026 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-10-14 21:41:06,027 INFO L410 AbstractCegarLoop]: === Iteration 9 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-10-14 21:41:06,027 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-10-14 21:41:06,028 INFO L82 PathProgramCache]: Analyzing trace with hash -1091385771, now seen corresponding path program 5 times [2019-10-14 21:41:06,028 INFO L157 tionRefinementEngine]: Executing refinement strategy CAMEL [2019-10-14 21:41:06,029 INFO L342 tionRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1479989135] [2019-10-14 21:41:06,029 INFO L116 rtionOrderModulation]: Craig_NestedInterpolation forces the order to NOT_INCREMENTALLY [2019-10-14 21:41:06,029 INFO L116 rtionOrderModulation]: Craig_NestedInterpolation forces the order to NOT_INCREMENTALLY [2019-10-14 21:41:06,029 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-10-14 21:41:06,041 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-10-14 21:41:06,103 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-10-14 21:41:06,106 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 1 proven. 12 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2019-10-14 21:41:06,107 INFO L342 tionRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1479989135] [2019-10-14 21:41:06,107 INFO L342 tionRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [762253037] [2019-10-14 21:41:06,107 INFO L92 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-10-14 21:41:06,190 INFO L249 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2019-10-14 21:41:06,190 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-10-14 21:41:06,191 INFO L256 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 8 conjunts are in the unsatisfiable core [2019-10-14 21:41:06,192 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2019-10-14 21:41:06,316 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 9 proven. 4 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2019-10-14 21:41:06,317 INFO L223 tionRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-10-14 21:41:06,317 INFO L236 tionRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 9] total 17 [2019-10-14 21:41:06,317 INFO L342 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1045378564] [2019-10-14 21:41:06,318 INFO L442 AbstractCegarLoop]: Interpolant automaton has 17 states [2019-10-14 21:41:06,318 INFO L137 tionRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-10-14 21:41:06,318 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2019-10-14 21:41:06,318 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=48, Invalid=224, Unknown=0, NotChecked=0, Total=272 [2019-10-14 21:41:06,319 INFO L87 Difference]: Start difference. First operand 36 states and 39 transitions. Second operand 17 states. [2019-10-14 21:41:06,562 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-10-14 21:41:06,562 INFO L93 Difference]: Finished difference Result 50 states and 54 transitions. [2019-10-14 21:41:06,562 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2019-10-14 21:41:06,562 INFO L78 Accepts]: Start accepts. Automaton has 17 states. Word has length 32 [2019-10-14 21:41:06,563 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-10-14 21:41:06,563 INFO L225 Difference]: With dead ends: 50 [2019-10-14 21:41:06,563 INFO L226 Difference]: Without dead ends: 37 [2019-10-14 21:41:06,564 INFO L600 BasicCegarLoop]: 0 DeclaredPredicates, 50 GetRequests, 28 SyntacticMatches, 0 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 87 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=104, Invalid=448, Unknown=0, NotChecked=0, Total=552 [2019-10-14 21:41:06,564 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2019-10-14 21:41:06,573 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 35. [2019-10-14 21:41:06,573 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 35 states. [2019-10-14 21:41:06,574 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 37 transitions. [2019-10-14 21:41:06,574 INFO L78 Accepts]: Start accepts. Automaton has 35 states and 37 transitions. Word has length 32 [2019-10-14 21:41:06,575 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-10-14 21:41:06,575 INFO L462 AbstractCegarLoop]: Abstraction has 35 states and 37 transitions. [2019-10-14 21:41:06,575 INFO L463 AbstractCegarLoop]: Interpolant automaton has 17 states. [2019-10-14 21:41:06,575 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 37 transitions. [2019-10-14 21:41:06,576 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2019-10-14 21:41:06,576 INFO L372 BasicCegarLoop]: Found error trace [2019-10-14 21:41:06,576 INFO L380 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-10-14 21:41:06,777 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-10-14 21:41:06,777 INFO L410 AbstractCegarLoop]: === Iteration 10 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-10-14 21:41:06,778 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-10-14 21:41:06,778 INFO L82 PathProgramCache]: Analyzing trace with hash 18469971, now seen corresponding path program 6 times [2019-10-14 21:41:06,778 INFO L157 tionRefinementEngine]: Executing refinement strategy CAMEL [2019-10-14 21:41:06,779 INFO L342 tionRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1619877889] [2019-10-14 21:41:06,779 INFO L116 rtionOrderModulation]: Craig_NestedInterpolation forces the order to NOT_INCREMENTALLY [2019-10-14 21:41:06,779 INFO L116 rtionOrderModulation]: Craig_NestedInterpolation forces the order to NOT_INCREMENTALLY [2019-10-14 21:41:06,780 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-10-14 21:41:06,798 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-10-14 21:41:08,008 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-10-14 21:41:08,017 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 2 proven. 25 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-10-14 21:41:08,018 INFO L342 tionRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1619877889] [2019-10-14 21:41:08,018 INFO L342 tionRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1188562058] [2019-10-14 21:41:08,018 INFO L92 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-10-14 21:41:08,078 INFO L249 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2019-10-14 21:41:08,079 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-10-14 21:41:08,080 INFO L256 TraceCheckSpWp]: Trace formula consists of 118 conjuncts, 43 conjunts are in the unsatisfiable core [2019-10-14 21:41:08,086 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2019-10-14 21:41:08,160 INFO L375 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 9 [2019-10-14 21:41:08,161 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-10-14 21:41:08,170 INFO L567 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-10-14 21:41:08,170 INFO L496 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2019-10-14 21:41:08,170 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 2 variables, input treesize:20, output treesize:7 [2019-10-14 21:41:08,557 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-10-14 21:41:08,559 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-10-14 21:41:08,575 INFO L341 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2019-10-14 21:41:08,575 INFO L375 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 30 treesize of output 41 [2019-10-14 21:41:08,577 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-10-14 21:41:08,577 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-10-14 21:41:08,579 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-10-14 21:41:08,580 INFO L496 ElimStorePlain]: Start of recursive call 2: 2 dim-0 vars, End of recursive call: 2 dim-0 vars, and 4 xjuncts. [2019-10-14 21:41:08,598 INFO L567 ElimStorePlain]: treesize reduction 35, result has 36.4 percent of original size [2019-10-14 21:41:08,599 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-10-14 21:41:08,600 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 2 variables, input treesize:37, output treesize:20 [2019-10-14 21:41:08,637 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-10-14 21:41:08,692 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-10-14 21:41:08,712 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-10-14 21:41:08,777 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 0 proven. 27 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-10-14 21:41:08,778 INFO L223 tionRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-10-14 21:41:08,778 INFO L236 tionRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [26, 22] total 44 [2019-10-14 21:41:08,778 INFO L342 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [150379411] [2019-10-14 21:41:08,779 INFO L442 AbstractCegarLoop]: Interpolant automaton has 44 states [2019-10-14 21:41:08,779 INFO L137 tionRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-10-14 21:41:08,779 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 44 interpolants. [2019-10-14 21:41:08,780 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=264, Invalid=1628, Unknown=0, NotChecked=0, Total=1892 [2019-10-14 21:41:08,781 INFO L87 Difference]: Start difference. First operand 35 states and 37 transitions. Second operand 44 states. [2019-10-14 21:41:10,057 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-10-14 21:41:10,057 INFO L93 Difference]: Finished difference Result 52 states and 55 transitions. [2019-10-14 21:41:10,057 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2019-10-14 21:41:10,058 INFO L78 Accepts]: Start accepts. Automaton has 44 states. Word has length 34 [2019-10-14 21:41:10,058 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-10-14 21:41:10,059 INFO L225 Difference]: With dead ends: 52 [2019-10-14 21:41:10,059 INFO L226 Difference]: Without dead ends: 47 [2019-10-14 21:41:10,061 INFO L600 BasicCegarLoop]: 0 DeclaredPredicates, 73 GetRequests, 17 SyntacticMatches, 1 SemanticMatches, 55 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1081 ImplicationChecksByTransitivity, 2.1s TimeCoverageRelationStatistics Valid=427, Invalid=2765, Unknown=0, NotChecked=0, Total=3192 [2019-10-14 21:41:10,062 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2019-10-14 21:41:10,068 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 40. [2019-10-14 21:41:10,068 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 40 states. [2019-10-14 21:41:10,068 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 40 states to 40 states and 43 transitions. [2019-10-14 21:41:10,069 INFO L78 Accepts]: Start accepts. Automaton has 40 states and 43 transitions. Word has length 34 [2019-10-14 21:41:10,069 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-10-14 21:41:10,069 INFO L462 AbstractCegarLoop]: Abstraction has 40 states and 43 transitions. [2019-10-14 21:41:10,069 INFO L463 AbstractCegarLoop]: Interpolant automaton has 44 states. [2019-10-14 21:41:10,069 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 43 transitions. [2019-10-14 21:41:10,070 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2019-10-14 21:41:10,070 INFO L372 BasicCegarLoop]: Found error trace [2019-10-14 21:41:10,070 INFO L380 BasicCegarLoop]: trace histogram [4, 4, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-10-14 21:41:10,274 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-10-14 21:41:10,274 INFO L410 AbstractCegarLoop]: === Iteration 11 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-10-14 21:41:10,275 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-10-14 21:41:10,275 INFO L82 PathProgramCache]: Analyzing trace with hash 1586924177, now seen corresponding path program 7 times [2019-10-14 21:41:10,275 INFO L157 tionRefinementEngine]: Executing refinement strategy CAMEL [2019-10-14 21:41:10,276 INFO L342 tionRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1884142473] [2019-10-14 21:41:10,276 INFO L116 rtionOrderModulation]: Craig_NestedInterpolation forces the order to NOT_INCREMENTALLY [2019-10-14 21:41:10,277 INFO L116 rtionOrderModulation]: Craig_NestedInterpolation forces the order to NOT_INCREMENTALLY [2019-10-14 21:41:10,277 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-10-14 21:41:10,287 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-10-14 21:41:10,354 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-10-14 21:41:10,357 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 11 proven. 14 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2019-10-14 21:41:10,358 INFO L342 tionRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1884142473] [2019-10-14 21:41:10,358 INFO L342 tionRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [331153404] [2019-10-14 21:41:10,358 INFO L92 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-10-14 21:41:10,409 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-10-14 21:41:10,410 INFO L256 TraceCheckSpWp]: Trace formula consists of 123 conjuncts, 10 conjunts are in the unsatisfiable core [2019-10-14 21:41:10,412 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2019-10-14 21:41:10,557 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 16 proven. 9 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2019-10-14 21:41:10,557 INFO L223 tionRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-10-14 21:41:10,558 INFO L236 tionRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11] total 17 [2019-10-14 21:41:10,558 INFO L342 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1112270607] [2019-10-14 21:41:10,559 INFO L442 AbstractCegarLoop]: Interpolant automaton has 17 states [2019-10-14 21:41:10,559 INFO L137 tionRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-10-14 21:41:10,559 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2019-10-14 21:41:10,560 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=62, Invalid=210, Unknown=0, NotChecked=0, Total=272 [2019-10-14 21:41:10,560 INFO L87 Difference]: Start difference. First operand 40 states and 43 transitions. Second operand 17 states. [2019-10-14 21:41:10,837 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-10-14 21:41:10,837 INFO L93 Difference]: Finished difference Result 74 states and 80 transitions. [2019-10-14 21:41:10,838 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2019-10-14 21:41:10,838 INFO L78 Accepts]: Start accepts. Automaton has 17 states. Word has length 36 [2019-10-14 21:41:10,839 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-10-14 21:41:10,839 INFO L225 Difference]: With dead ends: 74 [2019-10-14 21:41:10,839 INFO L226 Difference]: Without dead ends: 43 [2019-10-14 21:41:10,843 INFO L600 BasicCegarLoop]: 0 DeclaredPredicates, 54 GetRequests, 33 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 90 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=110, Invalid=396, Unknown=0, NotChecked=0, Total=506 [2019-10-14 21:41:10,843 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2019-10-14 21:41:10,857 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 42. [2019-10-14 21:41:10,857 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 42 states. [2019-10-14 21:41:10,861 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 42 states to 42 states and 45 transitions. [2019-10-14 21:41:10,861 INFO L78 Accepts]: Start accepts. Automaton has 42 states and 45 transitions. Word has length 36 [2019-10-14 21:41:10,861 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-10-14 21:41:10,862 INFO L462 AbstractCegarLoop]: Abstraction has 42 states and 45 transitions. [2019-10-14 21:41:10,862 INFO L463 AbstractCegarLoop]: Interpolant automaton has 17 states. [2019-10-14 21:41:10,862 INFO L276 IsEmpty]: Start isEmpty. Operand 42 states and 45 transitions. [2019-10-14 21:41:10,866 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2019-10-14 21:41:10,866 INFO L372 BasicCegarLoop]: Found error trace [2019-10-14 21:41:10,866 INFO L380 BasicCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-10-14 21:41:11,072 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-10-14 21:41:11,073 INFO L410 AbstractCegarLoop]: === Iteration 12 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-10-14 21:41:11,073 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-10-14 21:41:11,074 INFO L82 PathProgramCache]: Analyzing trace with hash 779217359, now seen corresponding path program 8 times [2019-10-14 21:41:11,074 INFO L157 tionRefinementEngine]: Executing refinement strategy CAMEL [2019-10-14 21:41:11,074 INFO L342 tionRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1459378593] [2019-10-14 21:41:11,075 INFO L116 rtionOrderModulation]: Craig_NestedInterpolation forces the order to NOT_INCREMENTALLY [2019-10-14 21:41:11,075 INFO L116 rtionOrderModulation]: Craig_NestedInterpolation forces the order to NOT_INCREMENTALLY [2019-10-14 21:41:11,075 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-10-14 21:41:11,085 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-10-14 21:41:11,153 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-10-14 21:41:11,156 INFO L134 CoverageAnalysis]: Checked inductivity of 41 backedges. 4 proven. 21 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2019-10-14 21:41:11,156 INFO L342 tionRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1459378593] [2019-10-14 21:41:11,157 INFO L342 tionRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1138213445] [2019-10-14 21:41:11,157 INFO L92 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-10-14 21:41:11,198 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2019-10-14 21:41:11,198 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-10-14 21:41:11,199 INFO L256 TraceCheckSpWp]: Trace formula consists of 129 conjuncts, 10 conjunts are in the unsatisfiable core [2019-10-14 21:41:11,201 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2019-10-14 21:41:11,269 INFO L134 CoverageAnalysis]: Checked inductivity of 41 backedges. 9 proven. 16 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2019-10-14 21:41:11,269 INFO L223 tionRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-10-14 21:41:11,269 INFO L236 tionRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11] total 17 [2019-10-14 21:41:11,270 INFO L342 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [666065855] [2019-10-14 21:41:11,270 INFO L442 AbstractCegarLoop]: Interpolant automaton has 17 states [2019-10-14 21:41:11,270 INFO L137 tionRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-10-14 21:41:11,270 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2019-10-14 21:41:11,271 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=68, Invalid=204, Unknown=0, NotChecked=0, Total=272 [2019-10-14 21:41:11,271 INFO L87 Difference]: Start difference. First operand 42 states and 45 transitions. Second operand 17 states. [2019-10-14 21:41:11,530 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-10-14 21:41:11,530 INFO L93 Difference]: Finished difference Result 58 states and 62 transitions. [2019-10-14 21:41:11,531 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2019-10-14 21:41:11,531 INFO L78 Accepts]: Start accepts. Automaton has 17 states. Word has length 38 [2019-10-14 21:41:11,531 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-10-14 21:41:11,532 INFO L225 Difference]: With dead ends: 58 [2019-10-14 21:41:11,532 INFO L226 Difference]: Without dead ends: 43 [2019-10-14 21:41:11,533 INFO L600 BasicCegarLoop]: 0 DeclaredPredicates, 57 GetRequests, 35 SyntacticMatches, 0 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 91 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=150, Invalid=402, Unknown=0, NotChecked=0, Total=552 [2019-10-14 21:41:11,533 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2019-10-14 21:41:11,539 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 41. [2019-10-14 21:41:11,539 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 41 states. [2019-10-14 21:41:11,540 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 43 transitions. [2019-10-14 21:41:11,540 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 43 transitions. Word has length 38 [2019-10-14 21:41:11,540 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-10-14 21:41:11,540 INFO L462 AbstractCegarLoop]: Abstraction has 41 states and 43 transitions. [2019-10-14 21:41:11,541 INFO L463 AbstractCegarLoop]: Interpolant automaton has 17 states. [2019-10-14 21:41:11,541 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 43 transitions. [2019-10-14 21:41:11,541 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2019-10-14 21:41:11,541 INFO L372 BasicCegarLoop]: Found error trace [2019-10-14 21:41:11,542 INFO L380 BasicCegarLoop]: trace histogram [4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-10-14 21:41:11,752 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-10-14 21:41:11,752 INFO L410 AbstractCegarLoop]: === Iteration 13 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-10-14 21:41:11,752 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-10-14 21:41:11,753 INFO L82 PathProgramCache]: Analyzing trace with hash 1089139021, now seen corresponding path program 9 times [2019-10-14 21:41:11,753 INFO L157 tionRefinementEngine]: Executing refinement strategy CAMEL [2019-10-14 21:41:11,753 INFO L342 tionRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2024035110] [2019-10-14 21:41:11,754 INFO L116 rtionOrderModulation]: Craig_NestedInterpolation forces the order to NOT_INCREMENTALLY [2019-10-14 21:41:11,754 INFO L116 rtionOrderModulation]: Craig_NestedInterpolation forces the order to NOT_INCREMENTALLY [2019-10-14 21:41:11,754 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-10-14 21:41:11,776 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-10-14 21:41:13,433 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-10-14 21:41:13,444 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 6 proven. 42 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-10-14 21:41:13,445 INFO L342 tionRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2024035110] [2019-10-14 21:41:13,445 INFO L342 tionRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1191251035] [2019-10-14 21:41:13,445 INFO L92 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-10-14 21:41:13,506 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2019-10-14 21:41:13,506 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-10-14 21:41:13,508 INFO L256 TraceCheckSpWp]: Trace formula consists of 134 conjuncts, 51 conjunts are in the unsatisfiable core [2019-10-14 21:41:13,511 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2019-10-14 21:41:13,542 INFO L375 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2019-10-14 21:41:13,543 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-10-14 21:41:13,549 INFO L567 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-10-14 21:41:13,550 INFO L496 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2019-10-14 21:41:13,550 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 2 variables, input treesize:25, output treesize:10 [2019-10-14 21:41:14,581 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-10-14 21:41:14,583 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-10-14 21:41:14,584 INFO L172 IndexEqualityManager]: detected equality via solver [2019-10-14 21:41:14,585 INFO L172 IndexEqualityManager]: detected equality via solver [2019-10-14 21:41:14,590 INFO L341 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2019-10-14 21:41:14,590 INFO L375 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 1 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 34 treesize of output 15 [2019-10-14 21:41:14,591 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-10-14 21:41:14,612 INFO L567 ElimStorePlain]: treesize reduction 3, result has 88.5 percent of original size [2019-10-14 21:41:14,613 INFO L496 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2019-10-14 21:41:14,613 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 4 variables, input treesize:57, output treesize:13 [2019-10-14 21:41:14,753 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-10-14 21:41:14,850 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 7 proven. 32 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2019-10-14 21:41:14,851 INFO L223 tionRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-10-14 21:41:14,851 INFO L236 tionRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [31, 27] total 55 [2019-10-14 21:41:14,851 INFO L342 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [986341509] [2019-10-14 21:41:14,852 INFO L442 AbstractCegarLoop]: Interpolant automaton has 55 states [2019-10-14 21:41:14,852 INFO L137 tionRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-10-14 21:41:14,852 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 55 interpolants. [2019-10-14 21:41:14,853 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=263, Invalid=2707, Unknown=0, NotChecked=0, Total=2970 [2019-10-14 21:41:14,853 INFO L87 Difference]: Start difference. First operand 41 states and 43 transitions. Second operand 55 states. [2019-10-14 21:41:18,174 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-10-14 21:41:18,175 INFO L93 Difference]: Finished difference Result 60 states and 63 transitions. [2019-10-14 21:41:18,175 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 34 states. [2019-10-14 21:41:18,175 INFO L78 Accepts]: Start accepts. Automaton has 55 states. Word has length 40 [2019-10-14 21:41:18,176 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-10-14 21:41:18,177 INFO L225 Difference]: With dead ends: 60 [2019-10-14 21:41:18,177 INFO L226 Difference]: Without dead ends: 55 [2019-10-14 21:41:18,187 INFO L600 BasicCegarLoop]: 0 DeclaredPredicates, 100 GetRequests, 17 SyntacticMatches, 1 SemanticMatches, 82 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1897 ImplicationChecksByTransitivity, 4.6s TimeCoverageRelationStatistics Valid=621, Invalid=6351, Unknown=0, NotChecked=0, Total=6972 [2019-10-14 21:41:18,188 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2019-10-14 21:41:18,193 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 46. [2019-10-14 21:41:18,194 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 46 states. [2019-10-14 21:41:18,194 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 49 transitions. [2019-10-14 21:41:18,194 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 49 transitions. Word has length 40 [2019-10-14 21:41:18,195 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-10-14 21:41:18,195 INFO L462 AbstractCegarLoop]: Abstraction has 46 states and 49 transitions. [2019-10-14 21:41:18,195 INFO L463 AbstractCegarLoop]: Interpolant automaton has 55 states. [2019-10-14 21:41:18,195 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 49 transitions. [2019-10-14 21:41:18,195 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2019-10-14 21:41:18,196 INFO L372 BasicCegarLoop]: Found error trace [2019-10-14 21:41:18,196 INFO L380 BasicCegarLoop]: trace histogram [5, 5, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-10-14 21:41:18,399 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-10-14 21:41:18,400 INFO L410 AbstractCegarLoop]: === Iteration 14 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-10-14 21:41:18,400 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-10-14 21:41:18,400 INFO L82 PathProgramCache]: Analyzing trace with hash -292269813, now seen corresponding path program 10 times [2019-10-14 21:41:18,401 INFO L157 tionRefinementEngine]: Executing refinement strategy CAMEL [2019-10-14 21:41:18,401 INFO L342 tionRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1137811214] [2019-10-14 21:41:18,402 INFO L116 rtionOrderModulation]: Craig_NestedInterpolation forces the order to NOT_INCREMENTALLY [2019-10-14 21:41:18,402 INFO L116 rtionOrderModulation]: Craig_NestedInterpolation forces the order to NOT_INCREMENTALLY [2019-10-14 21:41:18,402 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-10-14 21:41:18,412 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-10-14 21:41:18,508 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-10-14 21:41:18,511 INFO L134 CoverageAnalysis]: Checked inductivity of 57 backedges. 18 proven. 23 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2019-10-14 21:41:18,512 INFO L342 tionRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1137811214] [2019-10-14 21:41:18,512 INFO L342 tionRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [545150743] [2019-10-14 21:41:18,512 INFO L92 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-10-14 21:41:18,564 INFO L249 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2019-10-14 21:41:18,564 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-10-14 21:41:18,565 INFO L256 TraceCheckSpWp]: Trace formula consists of 119 conjuncts, 12 conjunts are in the unsatisfiable core [2019-10-14 21:41:18,567 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2019-10-14 21:41:18,673 INFO L134 CoverageAnalysis]: Checked inductivity of 57 backedges. 25 proven. 16 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2019-10-14 21:41:18,673 INFO L223 tionRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-10-14 21:41:18,673 INFO L236 tionRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 13] total 20 [2019-10-14 21:41:18,674 INFO L342 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [280308990] [2019-10-14 21:41:18,674 INFO L442 AbstractCegarLoop]: Interpolant automaton has 20 states [2019-10-14 21:41:18,674 INFO L137 tionRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-10-14 21:41:18,674 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2019-10-14 21:41:18,675 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=85, Invalid=295, Unknown=0, NotChecked=0, Total=380 [2019-10-14 21:41:18,675 INFO L87 Difference]: Start difference. First operand 46 states and 49 transitions. Second operand 20 states. [2019-10-14 21:41:18,953 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-10-14 21:41:18,953 INFO L93 Difference]: Finished difference Result 86 states and 92 transitions. [2019-10-14 21:41:18,954 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2019-10-14 21:41:18,954 INFO L78 Accepts]: Start accepts. Automaton has 20 states. Word has length 42 [2019-10-14 21:41:18,954 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-10-14 21:41:18,955 INFO L225 Difference]: With dead ends: 86 [2019-10-14 21:41:18,955 INFO L226 Difference]: Without dead ends: 49 [2019-10-14 21:41:18,956 INFO L600 BasicCegarLoop]: 0 DeclaredPredicates, 63 GetRequests, 38 SyntacticMatches, 0 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 133 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=150, Invalid=552, Unknown=0, NotChecked=0, Total=702 [2019-10-14 21:41:18,956 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2019-10-14 21:41:18,970 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 48. [2019-10-14 21:41:18,971 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 48 states. [2019-10-14 21:41:18,971 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 51 transitions. [2019-10-14 21:41:18,972 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 51 transitions. Word has length 42 [2019-10-14 21:41:18,972 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-10-14 21:41:18,975 INFO L462 AbstractCegarLoop]: Abstraction has 48 states and 51 transitions. [2019-10-14 21:41:18,975 INFO L463 AbstractCegarLoop]: Interpolant automaton has 20 states. [2019-10-14 21:41:18,976 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 51 transitions. [2019-10-14 21:41:18,976 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2019-10-14 21:41:18,976 INFO L372 BasicCegarLoop]: Found error trace [2019-10-14 21:41:18,977 INFO L380 BasicCegarLoop]: trace histogram [5, 5, 5, 5, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-10-14 21:41:19,181 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-10-14 21:41:19,182 INFO L410 AbstractCegarLoop]: === Iteration 15 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-10-14 21:41:19,182 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-10-14 21:41:19,182 INFO L82 PathProgramCache]: Analyzing trace with hash 1844365769, now seen corresponding path program 11 times [2019-10-14 21:41:19,183 INFO L157 tionRefinementEngine]: Executing refinement strategy CAMEL [2019-10-14 21:41:19,183 INFO L342 tionRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [413425011] [2019-10-14 21:41:19,183 INFO L116 rtionOrderModulation]: Craig_NestedInterpolation forces the order to NOT_INCREMENTALLY [2019-10-14 21:41:19,183 INFO L116 rtionOrderModulation]: Craig_NestedInterpolation forces the order to NOT_INCREMENTALLY [2019-10-14 21:41:19,183 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-10-14 21:41:19,193 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-10-14 21:41:19,310 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-10-14 21:41:19,313 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 9 proven. 32 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2019-10-14 21:41:19,313 INFO L342 tionRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [413425011] [2019-10-14 21:41:19,313 INFO L342 tionRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [730180497] [2019-10-14 21:41:19,314 INFO L92 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-10-14 21:41:19,376 INFO L249 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2019-10-14 21:41:19,376 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-10-14 21:41:19,377 INFO L256 TraceCheckSpWp]: Trace formula consists of 145 conjuncts, 12 conjunts are in the unsatisfiable core [2019-10-14 21:41:19,379 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2019-10-14 21:41:19,542 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 25 proven. 16 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2019-10-14 21:41:19,543 INFO L223 tionRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-10-14 21:41:19,543 INFO L236 tionRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 13] total 25 [2019-10-14 21:41:19,543 INFO L342 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [662168112] [2019-10-14 21:41:19,544 INFO L442 AbstractCegarLoop]: Interpolant automaton has 25 states [2019-10-14 21:41:19,544 INFO L137 tionRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-10-14 21:41:19,544 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2019-10-14 21:41:19,544 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=94, Invalid=506, Unknown=0, NotChecked=0, Total=600 [2019-10-14 21:41:19,545 INFO L87 Difference]: Start difference. First operand 48 states and 51 transitions. Second operand 25 states. [2019-10-14 21:41:19,972 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-10-14 21:41:19,973 INFO L93 Difference]: Finished difference Result 66 states and 70 transitions. [2019-10-14 21:41:19,973 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2019-10-14 21:41:19,973 INFO L78 Accepts]: Start accepts. Automaton has 25 states. Word has length 44 [2019-10-14 21:41:19,974 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-10-14 21:41:19,974 INFO L225 Difference]: With dead ends: 66 [2019-10-14 21:41:19,975 INFO L226 Difference]: Without dead ends: 49 [2019-10-14 21:41:19,976 INFO L600 BasicCegarLoop]: 0 DeclaredPredicates, 68 GetRequests, 36 SyntacticMatches, 0 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 224 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=203, Invalid=919, Unknown=0, NotChecked=0, Total=1122 [2019-10-14 21:41:19,976 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2019-10-14 21:41:19,982 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 47. [2019-10-14 21:41:19,982 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 47 states. [2019-10-14 21:41:19,982 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 49 transitions. [2019-10-14 21:41:19,983 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 49 transitions. Word has length 44 [2019-10-14 21:41:19,983 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-10-14 21:41:19,983 INFO L462 AbstractCegarLoop]: Abstraction has 47 states and 49 transitions. [2019-10-14 21:41:19,983 INFO L463 AbstractCegarLoop]: Interpolant automaton has 25 states. [2019-10-14 21:41:19,983 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 49 transitions. [2019-10-14 21:41:19,984 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2019-10-14 21:41:19,984 INFO L372 BasicCegarLoop]: Found error trace [2019-10-14 21:41:19,984 INFO L380 BasicCegarLoop]: trace histogram [5, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-10-14 21:41:20,194 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-10-14 21:41:20,195 INFO L410 AbstractCegarLoop]: === Iteration 16 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-10-14 21:41:20,195 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-10-14 21:41:20,195 INFO L82 PathProgramCache]: Analyzing trace with hash -1732203833, now seen corresponding path program 12 times [2019-10-14 21:41:20,195 INFO L157 tionRefinementEngine]: Executing refinement strategy CAMEL [2019-10-14 21:41:20,196 INFO L342 tionRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1525036698] [2019-10-14 21:41:20,196 INFO L116 rtionOrderModulation]: Craig_NestedInterpolation forces the order to NOT_INCREMENTALLY [2019-10-14 21:41:20,196 INFO L116 rtionOrderModulation]: Craig_NestedInterpolation forces the order to NOT_INCREMENTALLY [2019-10-14 21:41:20,197 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-10-14 21:41:20,214 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-10-14 21:41:22,370 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-10-14 21:41:22,384 INFO L134 CoverageAnalysis]: Checked inductivity of 75 backedges. 12 proven. 63 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-10-14 21:41:22,384 INFO L342 tionRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1525036698] [2019-10-14 21:41:22,384 INFO L342 tionRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1679000358] [2019-10-14 21:41:22,384 INFO L92 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-10-14 21:41:22,442 INFO L249 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 6 check-sat command(s) [2019-10-14 21:41:22,443 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-10-14 21:41:22,444 INFO L256 TraceCheckSpWp]: Trace formula consists of 150 conjuncts, 60 conjunts are in the unsatisfiable core [2019-10-14 21:41:22,446 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2019-10-14 21:41:22,489 INFO L375 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2019-10-14 21:41:22,490 INFO L496 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-10-14 21:41:22,504 INFO L567 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-10-14 21:41:22,505 INFO L496 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2019-10-14 21:41:22,505 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 2 variables, input treesize:25, output treesize:10 [2019-10-14 21:41:23,679 INFO L341 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2019-10-14 21:41:23,680 INFO L375 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 17 treesize of output 18 [2019-10-14 21:41:23,681 INFO L496 ElimStorePlain]: Start of recursive call 2: 1 dim-0 vars, End of recursive call: 1 dim-0 vars, and 2 xjuncts. [2019-10-14 21:41:23,692 INFO L567 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-10-14 21:41:23,692 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-10-14 21:41:23,694 INFO L496 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2019-10-14 21:41:23,694 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 3 variables, input treesize:29, output treesize:19 [2019-10-14 21:41:23,773 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-10-14 21:41:23,847 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-10-14 21:41:23,900 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-10-14 21:41:24,022 INFO L134 CoverageAnalysis]: Checked inductivity of 75 backedges. 9 proven. 50 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2019-10-14 21:41:24,023 INFO L223 tionRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-10-14 21:41:24,023 INFO L236 tionRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [36, 29] total 62 [2019-10-14 21:41:24,023 INFO L342 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [244867364] [2019-10-14 21:41:24,023 INFO L442 AbstractCegarLoop]: Interpolant automaton has 62 states [2019-10-14 21:41:24,024 INFO L137 tionRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-10-14 21:41:24,024 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 62 interpolants. [2019-10-14 21:41:24,025 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=345, Invalid=3437, Unknown=0, NotChecked=0, Total=3782 [2019-10-14 21:41:24,025 INFO L87 Difference]: Start difference. First operand 47 states and 49 transitions. Second operand 62 states. [2019-10-14 21:41:27,995 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-10-14 21:41:27,996 INFO L93 Difference]: Finished difference Result 67 states and 70 transitions. [2019-10-14 21:41:27,996 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 40 states. [2019-10-14 21:41:27,996 INFO L78 Accepts]: Start accepts. Automaton has 62 states. Word has length 46 [2019-10-14 21:41:27,997 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-10-14 21:41:27,997 INFO L225 Difference]: With dead ends: 67 [2019-10-14 21:41:27,998 INFO L226 Difference]: Without dead ends: 62 [2019-10-14 21:41:28,002 INFO L600 BasicCegarLoop]: 0 DeclaredPredicates, 117 GetRequests, 21 SyntacticMatches, 1 SemanticMatches, 95 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2432 ImplicationChecksByTransitivity, 5.8s TimeCoverageRelationStatistics Valid=880, Invalid=8432, Unknown=0, NotChecked=0, Total=9312 [2019-10-14 21:41:28,002 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 62 states. [2019-10-14 21:41:28,008 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 62 to 52. [2019-10-14 21:41:28,008 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 52 states. [2019-10-14 21:41:28,009 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52 states to 52 states and 55 transitions. [2019-10-14 21:41:28,009 INFO L78 Accepts]: Start accepts. Automaton has 52 states and 55 transitions. Word has length 46 [2019-10-14 21:41:28,009 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-10-14 21:41:28,009 INFO L462 AbstractCegarLoop]: Abstraction has 52 states and 55 transitions. [2019-10-14 21:41:28,010 INFO L463 AbstractCegarLoop]: Interpolant automaton has 62 states. [2019-10-14 21:41:28,010 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 55 transitions. [2019-10-14 21:41:28,010 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 49 [2019-10-14 21:41:28,010 INFO L372 BasicCegarLoop]: Found error trace [2019-10-14 21:41:28,011 INFO L380 BasicCegarLoop]: trace histogram [6, 6, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-10-14 21:41:28,214 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-10-14 21:41:28,214 INFO L410 AbstractCegarLoop]: === Iteration 17 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-10-14 21:41:28,215 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-10-14 21:41:28,215 INFO L82 PathProgramCache]: Analyzing trace with hash -1478388731, now seen corresponding path program 13 times [2019-10-14 21:41:28,215 INFO L157 tionRefinementEngine]: Executing refinement strategy CAMEL [2019-10-14 21:41:28,215 INFO L342 tionRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [554369733] [2019-10-14 21:41:28,216 INFO L116 rtionOrderModulation]: Craig_NestedInterpolation forces the order to NOT_INCREMENTALLY [2019-10-14 21:41:28,216 INFO L116 rtionOrderModulation]: Craig_NestedInterpolation forces the order to NOT_INCREMENTALLY [2019-10-14 21:41:28,216 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-10-14 21:41:28,227 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-10-14 21:41:28,350 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-10-14 21:41:28,356 INFO L134 CoverageAnalysis]: Checked inductivity of 86 backedges. 27 proven. 34 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2019-10-14 21:41:28,356 INFO L342 tionRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [554369733] [2019-10-14 21:41:28,356 INFO L342 tionRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [197967393] [2019-10-14 21:41:28,356 INFO L92 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-10-14 21:41:28,422 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-10-14 21:41:28,423 INFO L256 TraceCheckSpWp]: Trace formula consists of 155 conjuncts, 14 conjunts are in the unsatisfiable core [2019-10-14 21:41:28,425 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2019-10-14 21:41:28,552 INFO L134 CoverageAnalysis]: Checked inductivity of 86 backedges. 36 proven. 25 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2019-10-14 21:41:28,553 INFO L223 tionRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-10-14 21:41:28,553 INFO L236 tionRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 15] total 23 [2019-10-14 21:41:28,553 INFO L342 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [685389217] [2019-10-14 21:41:28,553 INFO L442 AbstractCegarLoop]: Interpolant automaton has 23 states [2019-10-14 21:41:28,553 INFO L137 tionRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-10-14 21:41:28,554 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2019-10-14 21:41:28,554 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=112, Invalid=394, Unknown=0, NotChecked=0, Total=506 [2019-10-14 21:41:28,554 INFO L87 Difference]: Start difference. First operand 52 states and 55 transitions. Second operand 23 states. [2019-10-14 21:41:28,889 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-10-14 21:41:28,889 INFO L93 Difference]: Finished difference Result 98 states and 104 transitions. [2019-10-14 21:41:28,890 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2019-10-14 21:41:28,890 INFO L78 Accepts]: Start accepts. Automaton has 23 states. Word has length 48 [2019-10-14 21:41:28,890 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-10-14 21:41:28,891 INFO L225 Difference]: With dead ends: 98 [2019-10-14 21:41:28,891 INFO L226 Difference]: Without dead ends: 55 [2019-10-14 21:41:28,892 INFO L600 BasicCegarLoop]: 0 DeclaredPredicates, 72 GetRequests, 43 SyntacticMatches, 0 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 183 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=197, Invalid=733, Unknown=0, NotChecked=0, Total=930 [2019-10-14 21:41:28,893 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2019-10-14 21:41:28,899 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 54. [2019-10-14 21:41:28,899 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 54 states. [2019-10-14 21:41:28,900 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 57 transitions. [2019-10-14 21:41:28,900 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 57 transitions. Word has length 48 [2019-10-14 21:41:28,900 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-10-14 21:41:28,901 INFO L462 AbstractCegarLoop]: Abstraction has 54 states and 57 transitions. [2019-10-14 21:41:28,901 INFO L463 AbstractCegarLoop]: Interpolant automaton has 23 states. [2019-10-14 21:41:28,901 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 57 transitions. [2019-10-14 21:41:28,901 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2019-10-14 21:41:28,901 INFO L372 BasicCegarLoop]: Found error trace [2019-10-14 21:41:28,902 INFO L380 BasicCegarLoop]: trace histogram [6, 6, 6, 6, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-10-14 21:41:29,105 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-10-14 21:41:29,106 INFO L410 AbstractCegarLoop]: === Iteration 18 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-10-14 21:41:29,106 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-10-14 21:41:29,106 INFO L82 PathProgramCache]: Analyzing trace with hash -362674621, now seen corresponding path program 14 times [2019-10-14 21:41:29,107 INFO L157 tionRefinementEngine]: Executing refinement strategy CAMEL [2019-10-14 21:41:29,107 INFO L342 tionRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1159824705] [2019-10-14 21:41:29,107 INFO L116 rtionOrderModulation]: Craig_NestedInterpolation forces the order to NOT_INCREMENTALLY [2019-10-14 21:41:29,108 INFO L116 rtionOrderModulation]: Craig_NestedInterpolation forces the order to NOT_INCREMENTALLY [2019-10-14 21:41:29,108 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-10-14 21:41:29,118 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-10-14 21:41:29,234 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-10-14 21:41:29,238 INFO L134 CoverageAnalysis]: Checked inductivity of 97 backedges. 16 proven. 45 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2019-10-14 21:41:29,238 INFO L342 tionRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1159824705] [2019-10-14 21:41:29,238 INFO L342 tionRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [917921596] [2019-10-14 21:41:29,239 INFO L92 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-10-14 21:41:29,300 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2019-10-14 21:41:29,301 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-10-14 21:41:29,301 INFO L256 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 14 conjunts are in the unsatisfiable core [2019-10-14 21:41:29,303 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2019-10-14 21:41:29,419 INFO L134 CoverageAnalysis]: Checked inductivity of 97 backedges. 25 proven. 36 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2019-10-14 21:41:29,420 INFO L223 tionRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-10-14 21:41:29,420 INFO L236 tionRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 15] total 23 [2019-10-14 21:41:29,420 INFO L342 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1603132770] [2019-10-14 21:41:29,420 INFO L442 AbstractCegarLoop]: Interpolant automaton has 23 states [2019-10-14 21:41:29,420 INFO L137 tionRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-10-14 21:41:29,420 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2019-10-14 21:41:29,421 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=122, Invalid=384, Unknown=0, NotChecked=0, Total=506 [2019-10-14 21:41:29,421 INFO L87 Difference]: Start difference. First operand 54 states and 57 transitions. Second operand 23 states. [2019-10-14 21:41:29,767 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-10-14 21:41:29,767 INFO L93 Difference]: Finished difference Result 74 states and 78 transitions. [2019-10-14 21:41:29,768 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2019-10-14 21:41:29,768 INFO L78 Accepts]: Start accepts. Automaton has 23 states. Word has length 50 [2019-10-14 21:41:29,768 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-10-14 21:41:29,769 INFO L225 Difference]: With dead ends: 74 [2019-10-14 21:41:29,769 INFO L226 Difference]: Without dead ends: 55 [2019-10-14 21:41:29,770 INFO L600 BasicCegarLoop]: 0 DeclaredPredicates, 75 GetRequests, 45 SyntacticMatches, 0 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 203 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=269, Invalid=723, Unknown=0, NotChecked=0, Total=992 [2019-10-14 21:41:29,770 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2019-10-14 21:41:29,776 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 53. [2019-10-14 21:41:29,776 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 53 states. [2019-10-14 21:41:29,776 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 55 transitions. [2019-10-14 21:41:29,777 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 55 transitions. Word has length 50 [2019-10-14 21:41:29,777 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-10-14 21:41:29,777 INFO L462 AbstractCegarLoop]: Abstraction has 53 states and 55 transitions. [2019-10-14 21:41:29,777 INFO L463 AbstractCegarLoop]: Interpolant automaton has 23 states. [2019-10-14 21:41:29,777 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 55 transitions. [2019-10-14 21:41:29,778 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 53 [2019-10-14 21:41:29,778 INFO L372 BasicCegarLoop]: Found error trace [2019-10-14 21:41:29,778 INFO L380 BasicCegarLoop]: trace histogram [6, 6, 6, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-10-14 21:41:29,981 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 15 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-10-14 21:41:29,982 INFO L410 AbstractCegarLoop]: === Iteration 19 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-10-14 21:41:29,982 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-10-14 21:41:29,982 INFO L82 PathProgramCache]: Analyzing trace with hash 149659841, now seen corresponding path program 15 times [2019-10-14 21:41:29,983 INFO L157 tionRefinementEngine]: Executing refinement strategy CAMEL [2019-10-14 21:41:29,983 INFO L342 tionRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1752013063] [2019-10-14 21:41:29,983 INFO L116 rtionOrderModulation]: Craig_NestedInterpolation forces the order to NOT_INCREMENTALLY [2019-10-14 21:41:29,984 INFO L116 rtionOrderModulation]: Craig_NestedInterpolation forces the order to NOT_INCREMENTALLY [2019-10-14 21:41:29,984 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-10-14 21:41:30,004 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-10-14 21:41:32,893 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-10-14 21:41:32,914 INFO L134 CoverageAnalysis]: Checked inductivity of 108 backedges. 20 proven. 88 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-10-14 21:41:32,915 INFO L342 tionRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1752013063] [2019-10-14 21:41:32,915 INFO L342 tionRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2024714684] [2019-10-14 21:41:32,915 INFO L92 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-10-14 21:41:33,021 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) [2019-10-14 21:41:33,021 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-10-14 21:41:33,023 INFO L256 TraceCheckSpWp]: Trace formula consists of 166 conjuncts, 68 conjunts are in the unsatisfiable core [2019-10-14 21:41:33,026 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2019-10-14 21:41:34,798 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-10-14 21:41:34,801 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-10-14 21:41:34,802 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-10-14 21:41:34,804 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-10-14 21:41:34,810 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-10-14 21:41:34,812 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-10-14 21:41:34,813 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-10-14 21:41:34,814 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-10-14 21:41:34,815 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-10-14 21:41:34,816 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-10-14 21:41:34,817 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-10-14 21:41:34,818 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-10-14 21:41:34,819 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-10-14 21:41:34,820 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-10-14 21:41:34,821 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-10-14 21:41:34,828 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-10-14 21:41:34,829 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-10-14 21:41:34,830 INFO L172 IndexEqualityManager]: detected equality via solver [2019-10-14 21:41:34,831 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-10-14 21:41:34,832 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-10-14 21:41:34,833 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-10-14 21:41:34,835 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-10-14 21:41:34,839 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-10-14 21:41:34,840 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-10-14 21:41:34,841 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-10-14 21:41:34,842 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-10-14 21:41:34,842 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-10-14 21:41:34,843 INFO L172 IndexEqualityManager]: detected equality via solver [2019-10-14 21:41:34,844 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-10-14 21:41:34,845 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-10-14 21:41:34,846 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-10-14 21:41:34,847 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-10-14 21:41:34,848 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-10-14 21:41:34,849 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-10-14 21:41:34,850 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-10-14 21:41:34,851 INFO L172 IndexEqualityManager]: detected equality via solver [2019-10-14 21:41:34,853 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-10-14 21:41:34,857 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-10-14 21:41:34,858 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-10-14 21:41:34,885 INFO L341 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2019-10-14 21:41:34,886 INFO L375 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 12 select indices, 12 select index equivalence classes, 30 disjoint index pairs (out of 66 index pairs), introduced 12 new quantified variables, introduced 66 case distinctions, treesize of input 96 treesize of output 114 [2019-10-14 21:41:34,887 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-10-14 21:41:34,888 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-10-14 21:41:34,888 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-10-14 21:41:34,888 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-10-14 21:41:34,889 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-10-14 21:41:34,890 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-10-14 21:41:34,891 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-10-14 21:41:34,892 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-10-14 21:41:34,892 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-10-14 21:41:34,897 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-10-14 21:41:34,898 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-10-14 21:41:34,898 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-10-14 21:41:34,899 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-10-14 21:41:34,900 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-10-14 21:41:34,901 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-10-14 21:41:34,902 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-10-14 21:41:34,903 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-10-14 21:41:34,904 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-10-14 21:41:34,905 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-10-14 21:41:34,905 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-10-14 21:41:34,906 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-10-14 21:41:34,907 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-10-14 21:41:34,907 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-10-14 21:41:34,908 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-10-14 21:41:34,909 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-10-14 21:41:34,909 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-10-14 21:41:34,910 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-10-14 21:41:34,910 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-10-14 21:41:34,911 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-10-14 21:41:34,914 INFO L496 ElimStorePlain]: Start of recursive call 2: 8 dim-0 vars, End of recursive call: 8 dim-0 vars, and 6 xjuncts. [2019-10-14 21:41:34,952 INFO L567 ElimStorePlain]: treesize reduction 317, result has 9.7 percent of original size [2019-10-14 21:41:34,953 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-10-14 21:41:34,954 INFO L496 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2019-10-14 21:41:34,954 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 3 variables, input treesize:111, output treesize:22 [2019-10-14 21:41:35,101 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-10-14 21:41:35,118 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-10-14 21:41:35,239 INFO L134 CoverageAnalysis]: Checked inductivity of 108 backedges. 11 proven. 72 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2019-10-14 21:41:35,239 INFO L223 tionRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-10-14 21:41:35,239 INFO L236 tionRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [41, 34] total 72 [2019-10-14 21:41:35,240 INFO L342 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1132077908] [2019-10-14 21:41:35,240 INFO L442 AbstractCegarLoop]: Interpolant automaton has 72 states [2019-10-14 21:41:35,240 INFO L137 tionRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-10-14 21:41:35,241 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 72 interpolants. [2019-10-14 21:41:35,242 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=492, Invalid=4620, Unknown=0, NotChecked=0, Total=5112 [2019-10-14 21:41:35,243 INFO L87 Difference]: Start difference. First operand 53 states and 55 transitions. Second operand 72 states. [2019-10-14 21:41:40,759 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-10-14 21:41:40,759 INFO L93 Difference]: Finished difference Result 76 states and 79 transitions. [2019-10-14 21:41:40,760 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 47 states. [2019-10-14 21:41:40,760 INFO L78 Accepts]: Start accepts. Automaton has 72 states. Word has length 52 [2019-10-14 21:41:40,760 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-10-14 21:41:40,761 INFO L225 Difference]: With dead ends: 76 [2019-10-14 21:41:40,761 INFO L226 Difference]: Without dead ends: 71 [2019-10-14 21:41:40,764 INFO L600 BasicCegarLoop]: 0 DeclaredPredicates, 134 GetRequests, 22 SyntacticMatches, 1 SemanticMatches, 111 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3886 ImplicationChecksByTransitivity, 7.9s TimeCoverageRelationStatistics Valid=1126, Invalid=11530, Unknown=0, NotChecked=0, Total=12656 [2019-10-14 21:41:40,765 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 71 states. [2019-10-14 21:41:40,771 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 71 to 58. [2019-10-14 21:41:40,771 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 58 states. [2019-10-14 21:41:40,771 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 61 transitions. [2019-10-14 21:41:40,771 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 61 transitions. Word has length 52 [2019-10-14 21:41:40,772 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-10-14 21:41:40,772 INFO L462 AbstractCegarLoop]: Abstraction has 58 states and 61 transitions. [2019-10-14 21:41:40,772 INFO L463 AbstractCegarLoop]: Interpolant automaton has 72 states. [2019-10-14 21:41:40,772 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 61 transitions. [2019-10-14 21:41:40,772 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2019-10-14 21:41:40,772 INFO L372 BasicCegarLoop]: Found error trace [2019-10-14 21:41:40,773 INFO L380 BasicCegarLoop]: trace histogram [7, 7, 6, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-10-14 21:41:40,978 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-10-14 21:41:40,978 INFO L410 AbstractCegarLoop]: === Iteration 20 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-10-14 21:41:40,978 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-10-14 21:41:40,979 INFO L82 PathProgramCache]: Analyzing trace with hash -1188629633, now seen corresponding path program 16 times [2019-10-14 21:41:40,979 INFO L157 tionRefinementEngine]: Executing refinement strategy CAMEL [2019-10-14 21:41:40,980 INFO L342 tionRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1133529184] [2019-10-14 21:41:40,980 INFO L116 rtionOrderModulation]: Craig_NestedInterpolation forces the order to NOT_INCREMENTALLY [2019-10-14 21:41:40,980 INFO L116 rtionOrderModulation]: Craig_NestedInterpolation forces the order to NOT_INCREMENTALLY [2019-10-14 21:41:40,981 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-10-14 21:41:40,992 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-10-14 21:41:41,130 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-10-14 21:41:41,135 INFO L134 CoverageAnalysis]: Checked inductivity of 121 backedges. 38 proven. 47 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2019-10-14 21:41:41,135 INFO L342 tionRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1133529184] [2019-10-14 21:41:41,135 INFO L342 tionRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1153081159] [2019-10-14 21:41:41,135 INFO L92 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 17 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 17 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-10-14 21:41:41,204 INFO L249 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2019-10-14 21:41:41,204 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-10-14 21:41:41,205 INFO L256 TraceCheckSpWp]: Trace formula consists of 143 conjuncts, 16 conjunts are in the unsatisfiable core [2019-10-14 21:41:41,207 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2019-10-14 21:41:41,345 INFO L134 CoverageAnalysis]: Checked inductivity of 121 backedges. 49 proven. 36 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2019-10-14 21:41:41,345 INFO L223 tionRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-10-14 21:41:41,345 INFO L236 tionRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 17] total 26 [2019-10-14 21:41:41,345 INFO L342 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [156833279] [2019-10-14 21:41:41,346 INFO L442 AbstractCegarLoop]: Interpolant automaton has 26 states [2019-10-14 21:41:41,346 INFO L137 tionRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-10-14 21:41:41,346 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2019-10-14 21:41:41,346 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=143, Invalid=507, Unknown=0, NotChecked=0, Total=650 [2019-10-14 21:41:41,347 INFO L87 Difference]: Start difference. First operand 58 states and 61 transitions. Second operand 26 states. [2019-10-14 21:41:41,763 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-10-14 21:41:41,763 INFO L93 Difference]: Finished difference Result 110 states and 116 transitions. [2019-10-14 21:41:41,764 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2019-10-14 21:41:41,764 INFO L78 Accepts]: Start accepts. Automaton has 26 states. Word has length 54 [2019-10-14 21:41:41,764 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-10-14 21:41:41,765 INFO L225 Difference]: With dead ends: 110 [2019-10-14 21:41:41,765 INFO L226 Difference]: Without dead ends: 61 [2019-10-14 21:41:41,766 INFO L600 BasicCegarLoop]: 0 DeclaredPredicates, 81 GetRequests, 48 SyntacticMatches, 0 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 240 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=251, Invalid=939, Unknown=0, NotChecked=0, Total=1190 [2019-10-14 21:41:41,766 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 61 states. [2019-10-14 21:41:41,773 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 61 to 60. [2019-10-14 21:41:41,773 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 60 states. [2019-10-14 21:41:41,774 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 60 states to 60 states and 63 transitions. [2019-10-14 21:41:41,774 INFO L78 Accepts]: Start accepts. Automaton has 60 states and 63 transitions. Word has length 54 [2019-10-14 21:41:41,774 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-10-14 21:41:41,774 INFO L462 AbstractCegarLoop]: Abstraction has 60 states and 63 transitions. [2019-10-14 21:41:41,774 INFO L463 AbstractCegarLoop]: Interpolant automaton has 26 states. [2019-10-14 21:41:41,774 INFO L276 IsEmpty]: Start isEmpty. Operand 60 states and 63 transitions. [2019-10-14 21:41:41,775 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2019-10-14 21:41:41,775 INFO L372 BasicCegarLoop]: Found error trace [2019-10-14 21:41:41,775 INFO L380 BasicCegarLoop]: trace histogram [7, 7, 7, 7, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-10-14 21:41:41,975 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-10-14 21:41:41,976 INFO L410 AbstractCegarLoop]: === Iteration 21 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-10-14 21:41:41,976 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-10-14 21:41:41,976 INFO L82 PathProgramCache]: Analyzing trace with hash 1909210941, now seen corresponding path program 17 times [2019-10-14 21:41:41,977 INFO L157 tionRefinementEngine]: Executing refinement strategy CAMEL [2019-10-14 21:41:41,977 INFO L342 tionRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2137929328] [2019-10-14 21:41:41,977 INFO L116 rtionOrderModulation]: Craig_NestedInterpolation forces the order to NOT_INCREMENTALLY [2019-10-14 21:41:41,977 INFO L116 rtionOrderModulation]: Craig_NestedInterpolation forces the order to NOT_INCREMENTALLY [2019-10-14 21:41:41,977 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-10-14 21:41:41,989 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-10-14 21:41:42,105 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-10-14 21:41:42,112 INFO L134 CoverageAnalysis]: Checked inductivity of 134 backedges. 25 proven. 60 refuted. 0 times theorem prover too weak. 49 trivial. 0 not checked. [2019-10-14 21:41:42,112 INFO L342 tionRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2137929328] [2019-10-14 21:41:42,113 INFO L342 tionRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [164374844] [2019-10-14 21:41:42,113 INFO L92 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 18 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 18 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-10-14 21:41:42,214 INFO L249 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 8 check-sat command(s) [2019-10-14 21:41:42,214 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-10-14 21:41:42,215 INFO L256 TraceCheckSpWp]: Trace formula consists of 177 conjuncts, 16 conjunts are in the unsatisfiable core [2019-10-14 21:41:42,217 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2019-10-14 21:41:42,431 INFO L134 CoverageAnalysis]: Checked inductivity of 134 backedges. 49 proven. 36 refuted. 0 times theorem prover too weak. 49 trivial. 0 not checked. [2019-10-14 21:41:42,431 INFO L223 tionRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-10-14 21:41:42,432 INFO L236 tionRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 17] total 33 [2019-10-14 21:41:42,432 INFO L342 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1314245842] [2019-10-14 21:41:42,432 INFO L442 AbstractCegarLoop]: Interpolant automaton has 33 states [2019-10-14 21:41:42,432 INFO L137 tionRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-10-14 21:41:42,433 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2019-10-14 21:41:42,433 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=156, Invalid=900, Unknown=0, NotChecked=0, Total=1056 [2019-10-14 21:41:42,433 INFO L87 Difference]: Start difference. First operand 60 states and 63 transitions. Second operand 33 states. [2019-10-14 21:41:43,047 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-10-14 21:41:43,048 INFO L93 Difference]: Finished difference Result 82 states and 86 transitions. [2019-10-14 21:41:43,048 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2019-10-14 21:41:43,048 INFO L78 Accepts]: Start accepts. Automaton has 33 states. Word has length 56 [2019-10-14 21:41:43,048 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-10-14 21:41:43,049 INFO L225 Difference]: With dead ends: 82 [2019-10-14 21:41:43,049 INFO L226 Difference]: Without dead ends: 61 [2019-10-14 21:41:43,049 INFO L600 BasicCegarLoop]: 0 DeclaredPredicates, 86 GetRequests, 44 SyntacticMatches, 0 SemanticMatches, 42 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 421 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=338, Invalid=1554, Unknown=0, NotChecked=0, Total=1892 [2019-10-14 21:41:43,050 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 61 states. [2019-10-14 21:41:43,056 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 61 to 59. [2019-10-14 21:41:43,056 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 59 states. [2019-10-14 21:41:43,056 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 59 states to 59 states and 61 transitions. [2019-10-14 21:41:43,056 INFO L78 Accepts]: Start accepts. Automaton has 59 states and 61 transitions. Word has length 56 [2019-10-14 21:41:43,056 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-10-14 21:41:43,056 INFO L462 AbstractCegarLoop]: Abstraction has 59 states and 61 transitions. [2019-10-14 21:41:43,057 INFO L463 AbstractCegarLoop]: Interpolant automaton has 33 states. [2019-10-14 21:41:43,057 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 61 transitions. [2019-10-14 21:41:43,057 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2019-10-14 21:41:43,057 INFO L372 BasicCegarLoop]: Found error trace [2019-10-14 21:41:43,057 INFO L380 BasicCegarLoop]: trace histogram [7, 7, 7, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-10-14 21:41:43,258 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 18 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2019-10-14 21:41:43,258 INFO L410 AbstractCegarLoop]: === Iteration 22 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-10-14 21:41:43,258 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-10-14 21:41:43,259 INFO L82 PathProgramCache]: Analyzing trace with hash 281310011, now seen corresponding path program 18 times [2019-10-14 21:41:43,259 INFO L157 tionRefinementEngine]: Executing refinement strategy CAMEL [2019-10-14 21:41:43,259 INFO L342 tionRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2036367763] [2019-10-14 21:41:43,259 INFO L116 rtionOrderModulation]: Craig_NestedInterpolation forces the order to NOT_INCREMENTALLY [2019-10-14 21:41:43,260 INFO L116 rtionOrderModulation]: Craig_NestedInterpolation forces the order to NOT_INCREMENTALLY [2019-10-14 21:41:43,260 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-10-14 21:41:43,283 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-10-14 21:41:44,302 WARN L191 SmtUtils]: Spent 105.00 ms on a formula simplification. DAG size of input: 62 DAG size of output: 42 [2019-10-14 21:41:44,456 WARN L191 SmtUtils]: Spent 111.00 ms on a formula simplification. DAG size of input: 65 DAG size of output: 45 [2019-10-14 21:41:44,608 WARN L191 SmtUtils]: Spent 105.00 ms on a formula simplification. DAG size of input: 64 DAG size of output: 44