/usr/bin/java -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data --core.log.level.for.class de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN -tc ../../../trunk/examples/toolchains/AutomizerC.xml -s ../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationQvasr_64.epf -i ../../../trunk/examples/svcomp/nla-digbench-scaling/hard2_unwindbound5.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-34549b5 [2022-04-06 23:18:48,821 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-06 23:18:48,823 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-06 23:18:48,849 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-06 23:18:48,850 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-06 23:18:48,851 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-06 23:18:48,856 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-06 23:18:48,860 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-06 23:18:48,861 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-06 23:18:48,865 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-06 23:18:48,866 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-06 23:18:48,867 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-06 23:18:48,867 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-06 23:18:48,869 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-06 23:18:48,869 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-06 23:18:48,871 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-06 23:18:48,871 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-06 23:18:48,871 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-06 23:18:48,874 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-06 23:18:48,878 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-06 23:18:48,880 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-06 23:18:48,881 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-06 23:18:48,881 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-06 23:18:48,882 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-06 23:18:48,883 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-06 23:18:48,888 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-06 23:18:48,888 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-06 23:18:48,888 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-06 23:18:48,889 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-06 23:18:48,890 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-06 23:18:48,891 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-06 23:18:48,891 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-06 23:18:48,892 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-06 23:18:48,893 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-06 23:18:48,893 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-06 23:18:48,893 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-06 23:18:48,894 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-06 23:18:48,894 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-06 23:18:48,894 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-06 23:18:48,894 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-06 23:18:48,895 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-06 23:18:48,896 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-06 23:18:48,896 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationQvasr_64.epf [2022-04-06 23:18:48,904 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-06 23:18:48,905 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-06 23:18:48,906 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-06 23:18:48,906 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-06 23:18:48,906 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-06 23:18:48,906 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-06 23:18:48,906 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-06 23:18:48,906 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-06 23:18:48,906 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-06 23:18:48,907 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-06 23:18:48,907 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-06 23:18:48,907 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-06 23:18:48,907 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-06 23:18:48,907 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-04-06 23:18:48,907 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-06 23:18:48,907 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-06 23:18:48,908 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-06 23:18:48,908 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_NestedInterpolation [2022-04-06 23:18:48,908 INFO L138 SettingsManager]: * Trace refinement strategy=ACCELERATED_INTERPOLATION [2022-04-06 23:18:48,908 INFO L138 SettingsManager]: * Trace refinement strategy used in Accelerated Interpolation=CAMEL [2022-04-06 23:18:48,908 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-04-06 23:18:48,908 INFO L138 SettingsManager]: * Loop acceleration method that is used by accelerated interpolation=QVASR [2022-04-06 23:18:48,908 INFO L138 SettingsManager]: * Use separate solver for trace checks=false WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.core: Log level for class -> de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN; [2022-04-06 23:18:49,128 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-06 23:18:49,152 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-06 23:18:49,154 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-06 23:18:49,155 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-06 23:18:49,155 INFO L275 PluginConnector]: CDTParser initialized [2022-04-06 23:18:49,156 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/hard2_unwindbound5.c [2022-04-06 23:18:49,204 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/644007fa0/a6db50a82b544b0585f22f1ae62dc868/FLAG747494dea [2022-04-06 23:18:49,580 INFO L306 CDTParser]: Found 1 translation units. [2022-04-06 23:18:49,581 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/hard2_unwindbound5.c [2022-04-06 23:18:49,591 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/644007fa0/a6db50a82b544b0585f22f1ae62dc868/FLAG747494dea [2022-04-06 23:18:49,606 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/644007fa0/a6db50a82b544b0585f22f1ae62dc868 [2022-04-06 23:18:49,607 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-06 23:18:49,609 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-04-06 23:18:49,611 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-06 23:18:49,611 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-06 23:18:49,614 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-06 23:18:49,614 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.04 11:18:49" (1/1) ... [2022-04-06 23:18:49,615 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@199f449d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:18:49, skipping insertion in model container [2022-04-06 23:18:49,615 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.04 11:18:49" (1/1) ... [2022-04-06 23:18:49,620 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-06 23:18:49,633 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-06 23:18:49,798 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/hard2_unwindbound5.c[526,539] [2022-04-06 23:18:49,815 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-06 23:18:49,821 INFO L203 MainTranslator]: Completed pre-run [2022-04-06 23:18:49,831 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/hard2_unwindbound5.c[526,539] [2022-04-06 23:18:49,843 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-06 23:18:49,855 INFO L208 MainTranslator]: Completed translation [2022-04-06 23:18:49,856 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:18:49 WrapperNode [2022-04-06 23:18:49,856 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-06 23:18:49,857 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-06 23:18:49,857 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-06 23:18:49,857 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-06 23:18:49,865 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:18:49" (1/1) ... [2022-04-06 23:18:49,866 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:18:49" (1/1) ... [2022-04-06 23:18:49,870 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:18:49" (1/1) ... [2022-04-06 23:18:49,871 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:18:49" (1/1) ... [2022-04-06 23:18:49,879 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:18:49" (1/1) ... [2022-04-06 23:18:49,884 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:18:49" (1/1) ... [2022-04-06 23:18:49,890 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:18:49" (1/1) ... [2022-04-06 23:18:49,893 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-06 23:18:49,894 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-06 23:18:49,894 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-06 23:18:49,894 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-06 23:18:49,895 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:18:49" (1/1) ... [2022-04-06 23:18:49,901 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-06 23:18:49,908 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 23:18:49,917 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2022-04-06 23:18:49,936 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2022-04-06 23:18:49,962 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-06 23:18:49,963 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-06 23:18:49,963 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-06 23:18:49,963 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-06 23:18:49,963 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-06 23:18:49,964 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-06 23:18:49,964 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-06 23:18:49,964 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-06 23:18:49,964 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-06 23:18:49,964 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-06 23:18:49,965 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2022-04-06 23:18:49,965 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-06 23:18:49,965 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-06 23:18:49,965 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-06 23:18:49,966 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-06 23:18:49,966 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-06 23:18:49,966 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-06 23:18:49,966 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-06 23:18:49,967 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-06 23:18:49,967 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-06 23:18:50,010 INFO L234 CfgBuilder]: Building ICFG [2022-04-06 23:18:50,011 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-06 23:18:50,113 INFO L275 CfgBuilder]: Performing block encoding [2022-04-06 23:18:50,118 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-06 23:18:50,118 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-04-06 23:18:50,119 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.04 11:18:50 BoogieIcfgContainer [2022-04-06 23:18:50,120 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-06 23:18:50,121 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-06 23:18:50,121 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-06 23:18:50,124 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-06 23:18:50,124 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 06.04 11:18:49" (1/3) ... [2022-04-06 23:18:50,124 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7ec1d385 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.04 11:18:50, skipping insertion in model container [2022-04-06 23:18:50,124 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:18:49" (2/3) ... [2022-04-06 23:18:50,125 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7ec1d385 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.04 11:18:50, skipping insertion in model container [2022-04-06 23:18:50,125 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.04 11:18:50" (3/3) ... [2022-04-06 23:18:50,126 INFO L111 eAbstractionObserver]: Analyzing ICFG hard2_unwindbound5.c [2022-04-06 23:18:50,129 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:Craig_NestedInterpolation Determinization: PREDICATE_ABSTRACTION [2022-04-06 23:18:50,129 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-06 23:18:50,157 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-06 23:18:50,162 INFO L340 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=Craig_NestedInterpolation, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=All, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP [2022-04-06 23:18:50,162 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-06 23:18:50,174 INFO L276 IsEmpty]: Start isEmpty. Operand has 31 states, 17 states have (on average 1.5294117647058822) internal successors, (26), 18 states have internal predecessors, (26), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-06 23:18:50,181 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2022-04-06 23:18:50,181 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:18:50,182 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:18:50,182 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:18:50,187 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:18:50,188 INFO L85 PathProgramCache]: Analyzing trace with hash -1682617676, now seen corresponding path program 1 times [2022-04-06 23:18:50,195 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:18:50,196 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [2111959698] [2022-04-06 23:18:50,220 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 23:18:50,220 INFO L85 PathProgramCache]: Analyzing trace with hash -1682617676, now seen corresponding path program 2 times [2022-04-06 23:18:50,223 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:18:50,223 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [532665594] [2022-04-06 23:18:50,223 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:18:50,224 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:18:50,337 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 23:18:50,409 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-06 23:18:50,414 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 23:18:50,427 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-06 23:18:50,427 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 23:18:50,428 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [532665594] [2022-04-06 23:18:50,428 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [532665594] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:18:50,428 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:18:50,428 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-06 23:18:50,430 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 23:18:50,430 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [2111959698] [2022-04-06 23:18:50,431 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [2111959698] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:18:50,431 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:18:50,431 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-06 23:18:50,431 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1858957315] [2022-04-06 23:18:50,434 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 23:18:50,437 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-06 23:18:50,438 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 23:18:50,459 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-06 23:18:50,460 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-06 23:18:50,462 INFO L87 Difference]: Start difference. First operand has 31 states, 17 states have (on average 1.5294117647058822) internal successors, (26), 18 states have internal predecessors, (26), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Second operand has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-06 23:18:50,560 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 23:18:50,560 INFO L93 Difference]: Finished difference Result 57 states and 91 transitions. [2022-04-06 23:18:50,561 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-06 23:18:50,562 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2022-04-06 23:18:50,562 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 23:18:50,567 INFO L225 Difference]: With dead ends: 57 [2022-04-06 23:18:50,567 INFO L226 Difference]: Without dead ends: 27 [2022-04-06 23:18:50,569 INFO L912 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 [2022-04-06 23:18:50,572 INFO L913 BasicCegarLoop]: 40 mSDtfsCounter, 6 mSDsluCounter, 4 mSDsCounter, 0 mSdLazyCounter, 23 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 44 SdHoareTripleChecker+Invalid, 31 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 23 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 23:18:50,572 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 44 Invalid, 31 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 23 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 23:18:50,583 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2022-04-06 23:18:50,600 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 26. [2022-04-06 23:18:50,601 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 14 states have (on average 1.4285714285714286) internal successors, (20), 15 states have internal predecessors, (20), 9 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-06 23:18:50,603 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 36 transitions. [2022-04-06 23:18:50,604 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 36 transitions. Word has length 12 [2022-04-06 23:18:50,604 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 23:18:50,604 INFO L478 AbstractCegarLoop]: Abstraction has 26 states and 36 transitions. [2022-04-06 23:18:50,604 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-06 23:18:50,604 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 36 transitions. [2022-04-06 23:18:50,605 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2022-04-06 23:18:50,605 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:18:50,605 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:18:50,606 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-06 23:18:50,606 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:18:50,609 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:18:50,609 INFO L85 PathProgramCache]: Analyzing trace with hash -2144676086, now seen corresponding path program 1 times [2022-04-06 23:18:50,609 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:18:50,609 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [534726012] [2022-04-06 23:18:50,611 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 23:18:50,611 INFO L85 PathProgramCache]: Analyzing trace with hash -2144676086, now seen corresponding path program 2 times [2022-04-06 23:18:50,612 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:18:50,613 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2039417872] [2022-04-06 23:18:50,613 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:18:50,613 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:18:50,638 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 23:18:50,704 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-06 23:18:50,707 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 23:18:50,718 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-06 23:18:50,719 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 23:18:50,719 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2039417872] [2022-04-06 23:18:50,719 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2039417872] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:18:50,720 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:18:50,720 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-06 23:18:50,720 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 23:18:50,720 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [534726012] [2022-04-06 23:18:50,720 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [534726012] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:18:50,720 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:18:50,720 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-06 23:18:50,721 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [136782225] [2022-04-06 23:18:50,721 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 23:18:50,721 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-06 23:18:50,721 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 23:18:50,722 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-06 23:18:50,722 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-04-06 23:18:50,722 INFO L87 Difference]: Start difference. First operand 26 states and 36 transitions. Second operand has 6 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-06 23:18:50,878 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 23:18:50,879 INFO L93 Difference]: Finished difference Result 41 states and 56 transitions. [2022-04-06 23:18:50,879 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-04-06 23:18:50,879 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2022-04-06 23:18:50,880 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 23:18:50,880 INFO L225 Difference]: With dead ends: 41 [2022-04-06 23:18:50,881 INFO L226 Difference]: Without dead ends: 39 [2022-04-06 23:18:50,881 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2022-04-06 23:18:50,882 INFO L913 BasicCegarLoop]: 34 mSDtfsCounter, 24 mSDsluCounter, 51 mSDsCounter, 0 mSdLazyCounter, 80 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 30 SdHoareTripleChecker+Valid, 85 SdHoareTripleChecker+Invalid, 93 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 80 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 23:18:50,882 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [30 Valid, 85 Invalid, 93 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 80 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 23:18:50,883 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2022-04-06 23:18:50,890 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 30. [2022-04-06 23:18:50,890 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 17 states have (on average 1.3529411764705883) internal successors, (23), 18 states have internal predecessors, (23), 9 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-06 23:18:50,891 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 39 transitions. [2022-04-06 23:18:50,891 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 39 transitions. Word has length 12 [2022-04-06 23:18:50,891 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 23:18:50,891 INFO L478 AbstractCegarLoop]: Abstraction has 30 states and 39 transitions. [2022-04-06 23:18:50,891 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-06 23:18:50,892 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 39 transitions. [2022-04-06 23:18:50,892 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2022-04-06 23:18:50,892 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:18:50,892 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:18:50,892 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-04-06 23:18:50,892 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:18:50,893 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:18:50,893 INFO L85 PathProgramCache]: Analyzing trace with hash 1842794081, now seen corresponding path program 1 times [2022-04-06 23:18:50,893 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:18:50,893 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [2121775777] [2022-04-06 23:18:50,894 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 23:18:50,894 INFO L85 PathProgramCache]: Analyzing trace with hash 1842794081, now seen corresponding path program 2 times [2022-04-06 23:18:50,894 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:18:50,894 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [206086378] [2022-04-06 23:18:50,894 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:18:50,895 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:18:50,905 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 23:18:50,958 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-06 23:18:50,966 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 23:18:50,972 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-06 23:18:50,972 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 23:18:50,973 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [206086378] [2022-04-06 23:18:50,973 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [206086378] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:18:50,973 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:18:50,973 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-04-06 23:18:50,973 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 23:18:50,973 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [2121775777] [2022-04-06 23:18:50,974 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [2121775777] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:18:50,974 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:18:50,974 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-04-06 23:18:50,974 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1261226428] [2022-04-06 23:18:50,974 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 23:18:50,974 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 23:18:50,974 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 23:18:50,975 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 23:18:50,975 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-06 23:18:50,975 INFO L87 Difference]: Start difference. First operand 30 states and 39 transitions. Second operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-06 23:18:51,035 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 23:18:51,035 INFO L93 Difference]: Finished difference Result 46 states and 61 transitions. [2022-04-06 23:18:51,036 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-04-06 23:18:51,036 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 14 [2022-04-06 23:18:51,036 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 23:18:51,038 INFO L225 Difference]: With dead ends: 46 [2022-04-06 23:18:51,038 INFO L226 Difference]: Without dead ends: 32 [2022-04-06 23:18:51,039 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-04-06 23:18:51,043 INFO L913 BasicCegarLoop]: 34 mSDtfsCounter, 6 mSDsluCounter, 39 mSDsCounter, 0 mSdLazyCounter, 51 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 73 SdHoareTripleChecker+Invalid, 59 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 51 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 23:18:51,047 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 73 Invalid, 59 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 51 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 23:18:51,049 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2022-04-06 23:18:51,057 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2022-04-06 23:18:51,057 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 19 states have (on average 1.3157894736842106) internal successors, (25), 20 states have internal predecessors, (25), 9 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-06 23:18:51,058 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 41 transitions. [2022-04-06 23:18:51,058 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 41 transitions. Word has length 14 [2022-04-06 23:18:51,058 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 23:18:51,058 INFO L478 AbstractCegarLoop]: Abstraction has 32 states and 41 transitions. [2022-04-06 23:18:51,058 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-06 23:18:51,059 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 41 transitions. [2022-04-06 23:18:51,059 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2022-04-06 23:18:51,059 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:18:51,059 INFO L499 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:18:51,059 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2022-04-06 23:18:51,059 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:18:51,060 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:18:51,060 INFO L85 PathProgramCache]: Analyzing trace with hash 311129497, now seen corresponding path program 1 times [2022-04-06 23:18:51,060 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:18:51,060 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1595740409] [2022-04-06 23:18:51,061 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 23:18:51,061 INFO L85 PathProgramCache]: Analyzing trace with hash 311129497, now seen corresponding path program 2 times [2022-04-06 23:18:51,061 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:18:51,061 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2032719066] [2022-04-06 23:18:51,061 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:18:51,062 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:18:51,076 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 23:18:51,108 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-06 23:18:51,110 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 23:18:51,114 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2022-04-06 23:18:51,115 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 23:18:51,119 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-06 23:18:51,119 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 23:18:51,119 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2032719066] [2022-04-06 23:18:51,119 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2032719066] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:18:51,119 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:18:51,119 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-06 23:18:51,120 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 23:18:51,120 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1595740409] [2022-04-06 23:18:51,120 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1595740409] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:18:51,120 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:18:51,120 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-06 23:18:51,120 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1274767065] [2022-04-06 23:18:51,120 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 23:18:51,121 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-06 23:18:51,121 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 23:18:51,121 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-06 23:18:51,121 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-04-06 23:18:51,121 INFO L87 Difference]: Start difference. First operand 32 states and 41 transitions. Second operand has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-06 23:18:51,245 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 23:18:51,246 INFO L93 Difference]: Finished difference Result 46 states and 60 transitions. [2022-04-06 23:18:51,246 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-04-06 23:18:51,246 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 17 [2022-04-06 23:18:51,247 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 23:18:51,247 INFO L225 Difference]: With dead ends: 46 [2022-04-06 23:18:51,247 INFO L226 Difference]: Without dead ends: 44 [2022-04-06 23:18:51,248 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2022-04-06 23:18:51,248 INFO L913 BasicCegarLoop]: 34 mSDtfsCounter, 19 mSDsluCounter, 44 mSDsCounter, 0 mSdLazyCounter, 93 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 78 SdHoareTripleChecker+Invalid, 106 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 93 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 23:18:51,248 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [24 Valid, 78 Invalid, 106 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 93 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 23:18:51,249 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2022-04-06 23:18:51,253 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 36. [2022-04-06 23:18:51,254 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 36 states, 22 states have (on average 1.2727272727272727) internal successors, (28), 23 states have internal predecessors, (28), 9 states have call successors, (9), 5 states have call predecessors, (9), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-06 23:18:51,254 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 44 transitions. [2022-04-06 23:18:51,255 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 44 transitions. Word has length 17 [2022-04-06 23:18:51,255 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 23:18:51,255 INFO L478 AbstractCegarLoop]: Abstraction has 36 states and 44 transitions. [2022-04-06 23:18:51,255 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-06 23:18:51,255 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 44 transitions. [2022-04-06 23:18:51,256 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2022-04-06 23:18:51,256 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:18:51,256 INFO L499 BasicCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:18:51,256 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2022-04-06 23:18:51,256 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:18:51,257 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:18:51,257 INFO L85 PathProgramCache]: Analyzing trace with hash -1912623062, now seen corresponding path program 1 times [2022-04-06 23:18:51,257 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:18:51,257 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1024138756] [2022-04-06 23:18:51,257 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 23:18:51,257 INFO L85 PathProgramCache]: Analyzing trace with hash -1912623062, now seen corresponding path program 2 times [2022-04-06 23:18:51,258 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:18:51,258 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [426329129] [2022-04-06 23:18:51,258 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:18:51,258 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:18:51,266 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 23:18:51,267 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [723326153] [2022-04-06 23:18:51,267 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 23:18:51,267 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:18:51,267 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 23:18:51,268 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 23:18:51,269 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2022-04-06 23:18:51,305 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 23:18:51,305 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 23:18:51,307 INFO L263 TraceCheckSpWp]: Trace formula consists of 93 conjuncts, 9 conjunts are in the unsatisfiable core [2022-04-06 23:18:51,310 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 23:18:51,425 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-06 23:18:51,426 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-06 23:18:51,426 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 23:18:51,426 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [426329129] [2022-04-06 23:18:51,426 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 23:18:51,426 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [723326153] [2022-04-06 23:18:51,426 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [723326153] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:18:51,427 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:18:51,427 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 23:18:51,427 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 23:18:51,427 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1024138756] [2022-04-06 23:18:51,427 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1024138756] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:18:51,427 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:18:51,428 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 23:18:51,428 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1815488761] [2022-04-06 23:18:51,428 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 23:18:51,428 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 23:18:51,428 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 23:18:51,428 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 23:18:51,429 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-06 23:18:51,429 INFO L87 Difference]: Start difference. First operand 36 states and 44 transitions. Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-06 23:18:51,470 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 23:18:51,470 INFO L93 Difference]: Finished difference Result 65 states and 87 transitions. [2022-04-06 23:18:51,471 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-06 23:18:51,471 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 22 [2022-04-06 23:18:51,471 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 23:18:51,472 INFO L225 Difference]: With dead ends: 65 [2022-04-06 23:18:51,472 INFO L226 Difference]: Without dead ends: 50 [2022-04-06 23:18:51,472 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 22 GetRequests, 18 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-04-06 23:18:51,473 INFO L913 BasicCegarLoop]: 38 mSDtfsCounter, 10 mSDsluCounter, 83 mSDsCounter, 0 mSdLazyCounter, 46 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 121 SdHoareTripleChecker+Invalid, 49 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 46 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 23:18:51,473 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 121 Invalid, 49 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 46 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 23:18:51,474 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2022-04-06 23:18:51,479 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 50. [2022-04-06 23:18:51,480 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 50 states, 29 states have (on average 1.2758620689655173) internal successors, (37), 31 states have internal predecessors, (37), 15 states have call successors, (15), 6 states have call predecessors, (15), 5 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-06 23:18:51,480 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 64 transitions. [2022-04-06 23:18:51,480 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 64 transitions. Word has length 22 [2022-04-06 23:18:51,481 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 23:18:51,481 INFO L478 AbstractCegarLoop]: Abstraction has 50 states and 64 transitions. [2022-04-06 23:18:51,481 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-06 23:18:51,481 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 64 transitions. [2022-04-06 23:18:51,482 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2022-04-06 23:18:51,482 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:18:51,482 INFO L499 BasicCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:18:51,502 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2022-04-06 23:18:51,702 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:18:51,702 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:18:51,703 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:18:51,703 INFO L85 PathProgramCache]: Analyzing trace with hash 214651490, now seen corresponding path program 1 times [2022-04-06 23:18:51,703 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:18:51,704 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1370631945] [2022-04-06 23:18:51,704 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 23:18:51,704 INFO L85 PathProgramCache]: Analyzing trace with hash 214651490, now seen corresponding path program 2 times [2022-04-06 23:18:51,704 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:18:51,704 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [433531779] [2022-04-06 23:18:51,704 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:18:51,705 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:18:51,715 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 23:18:51,715 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1470868474] [2022-04-06 23:18:51,716 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 23:18:51,716 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:18:51,716 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 23:18:51,717 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 23:18:51,718 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2022-04-06 23:18:51,750 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 23:18:51,750 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 23:18:51,751 INFO L263 TraceCheckSpWp]: Trace formula consists of 108 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-06 23:18:51,753 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 23:18:51,844 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-06 23:18:51,844 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-06 23:18:51,844 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 23:18:51,844 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [433531779] [2022-04-06 23:18:51,844 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 23:18:51,844 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1470868474] [2022-04-06 23:18:51,844 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1470868474] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:18:51,845 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:18:51,845 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 23:18:51,845 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 23:18:51,845 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1370631945] [2022-04-06 23:18:51,845 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1370631945] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:18:51,845 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:18:51,845 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 23:18:51,845 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1913404531] [2022-04-06 23:18:51,845 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 23:18:51,846 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 23:18:51,846 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 23:18:51,846 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 23:18:51,846 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-04-06 23:18:51,846 INFO L87 Difference]: Start difference. First operand 50 states and 64 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 4 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-06 23:18:51,881 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 23:18:51,881 INFO L93 Difference]: Finished difference Result 70 states and 80 transitions. [2022-04-06 23:18:51,882 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-06 23:18:51,882 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 4 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 30 [2022-04-06 23:18:51,882 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 23:18:51,883 INFO L225 Difference]: With dead ends: 70 [2022-04-06 23:18:51,884 INFO L226 Difference]: Without dead ends: 63 [2022-04-06 23:18:51,884 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 26 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-04-06 23:18:51,885 INFO L913 BasicCegarLoop]: 36 mSDtfsCounter, 3 mSDsluCounter, 88 mSDsCounter, 0 mSdLazyCounter, 19 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3 SdHoareTripleChecker+Valid, 124 SdHoareTripleChecker+Invalid, 22 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 19 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 23:18:51,886 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [3 Valid, 124 Invalid, 22 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 19 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 23:18:51,887 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2022-04-06 23:18:51,900 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 62. [2022-04-06 23:18:51,901 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 62 states, 38 states have (on average 1.1842105263157894) internal successors, (45), 40 states have internal predecessors, (45), 15 states have call successors, (15), 9 states have call predecessors, (15), 8 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-06 23:18:51,902 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 72 transitions. [2022-04-06 23:18:51,903 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 72 transitions. Word has length 30 [2022-04-06 23:18:51,903 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 23:18:51,905 INFO L478 AbstractCegarLoop]: Abstraction has 62 states and 72 transitions. [2022-04-06 23:18:51,906 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 4 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-06 23:18:51,906 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 72 transitions. [2022-04-06 23:18:51,907 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2022-04-06 23:18:51,908 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:18:51,908 INFO L499 BasicCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:18:51,929 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2022-04-06 23:18:52,127 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable5 [2022-04-06 23:18:52,129 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:18:52,129 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:18:52,129 INFO L85 PathProgramCache]: Analyzing trace with hash 216379368, now seen corresponding path program 1 times [2022-04-06 23:18:52,130 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:18:52,130 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [55126737] [2022-04-06 23:18:52,130 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 23:18:52,130 INFO L85 PathProgramCache]: Analyzing trace with hash 216379368, now seen corresponding path program 2 times [2022-04-06 23:18:52,130 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:18:52,130 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [904531470] [2022-04-06 23:18:52,130 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:18:52,131 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:18:52,139 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 23:18:52,139 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [522396335] [2022-04-06 23:18:52,139 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 23:18:52,139 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:18:52,140 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 23:18:52,144 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 23:18:52,145 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2022-04-06 23:18:52,182 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 23:18:52,182 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 23:18:52,183 INFO L263 TraceCheckSpWp]: Trace formula consists of 108 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-06 23:18:52,184 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 23:18:52,289 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-06 23:18:52,289 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-06 23:18:52,289 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 23:18:52,290 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [904531470] [2022-04-06 23:18:52,290 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 23:18:52,290 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [522396335] [2022-04-06 23:18:52,290 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [522396335] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:18:52,290 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:18:52,290 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 23:18:52,290 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 23:18:52,290 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [55126737] [2022-04-06 23:18:52,290 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [55126737] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:18:52,290 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:18:52,290 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 23:18:52,291 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1034052990] [2022-04-06 23:18:52,291 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 23:18:52,291 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 23:18:52,291 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 23:18:52,291 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 23:18:52,291 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-06 23:18:52,291 INFO L87 Difference]: Start difference. First operand 62 states and 72 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-06 23:18:52,337 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 23:18:52,337 INFO L93 Difference]: Finished difference Result 76 states and 91 transitions. [2022-04-06 23:18:52,337 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-06 23:18:52,337 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 30 [2022-04-06 23:18:52,338 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 23:18:52,338 INFO L225 Difference]: With dead ends: 76 [2022-04-06 23:18:52,338 INFO L226 Difference]: Without dead ends: 64 [2022-04-06 23:18:52,339 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 30 GetRequests, 26 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-04-06 23:18:52,339 INFO L913 BasicCegarLoop]: 29 mSDtfsCounter, 11 mSDsluCounter, 66 mSDsCounter, 0 mSdLazyCounter, 47 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 95 SdHoareTripleChecker+Invalid, 50 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 47 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 23:18:52,339 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 95 Invalid, 50 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 47 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 23:18:52,340 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2022-04-06 23:18:52,345 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 63. [2022-04-06 23:18:52,345 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 63 states, 39 states have (on average 1.2307692307692308) internal successors, (48), 41 states have internal predecessors, (48), 15 states have call successors, (15), 9 states have call predecessors, (15), 8 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-06 23:18:52,346 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 76 transitions. [2022-04-06 23:18:52,346 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 76 transitions. Word has length 30 [2022-04-06 23:18:52,346 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 23:18:52,346 INFO L478 AbstractCegarLoop]: Abstraction has 63 states and 76 transitions. [2022-04-06 23:18:52,346 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-06 23:18:52,346 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 76 transitions. [2022-04-06 23:18:52,347 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2022-04-06 23:18:52,347 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:18:52,347 INFO L499 BasicCegarLoop]: trace histogram [5, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:18:52,368 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2022-04-06 23:18:52,563 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:18:52,563 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:18:52,564 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:18:52,564 INFO L85 PathProgramCache]: Analyzing trace with hash -1255015940, now seen corresponding path program 1 times [2022-04-06 23:18:52,564 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:18:52,564 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1021474346] [2022-04-06 23:18:52,578 INFO L97 AcceleratorQvasr]: Qvasr could not accelerate loop because java.lang.UnsupportedOperationException: Cannot deal with arrays. [2022-04-06 23:18:52,578 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-06 23:18:52,578 INFO L85 PathProgramCache]: Analyzing trace with hash -1255015940, now seen corresponding path program 2 times [2022-04-06 23:18:52,579 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:18:52,579 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [9660339] [2022-04-06 23:18:52,579 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:18:52,579 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:18:52,595 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 23:18:52,596 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [82090825] [2022-04-06 23:18:52,596 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 23:18:52,596 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:18:52,596 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 23:18:52,604 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 23:18:52,616 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2022-04-06 23:18:52,647 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 23:18:52,647 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 23:18:52,648 INFO L263 TraceCheckSpWp]: Trace formula consists of 126 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-06 23:18:52,650 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 23:18:52,731 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 18 proven. 2 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2022-04-06 23:18:52,731 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 23:18:52,824 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-04-06 23:18:52,824 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 23:18:52,824 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [9660339] [2022-04-06 23:18:52,824 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 23:18:52,824 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [82090825] [2022-04-06 23:18:52,825 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [82090825] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 23:18:52,825 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 23:18:52,825 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2022-04-06 23:18:52,825 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 23:18:52,825 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1021474346] [2022-04-06 23:18:52,825 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1021474346] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:18:52,825 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:18:52,825 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 23:18:52,825 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1088727626] [2022-04-06 23:18:52,825 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 23:18:52,826 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 23:18:52,826 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 23:18:52,826 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 23:18:52,826 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2022-04-06 23:18:52,826 INFO L87 Difference]: Start difference. First operand 63 states and 76 transitions. Second operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 4 states have call successors, (7), 4 states have call predecessors, (7), 3 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2022-04-06 23:18:52,851 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 23:18:52,852 INFO L93 Difference]: Finished difference Result 90 states and 114 transitions. [2022-04-06 23:18:52,852 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-04-06 23:18:52,852 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 4 states have call successors, (7), 4 states have call predecessors, (7), 3 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) Word has length 37 [2022-04-06 23:18:52,852 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 23:18:52,854 INFO L225 Difference]: With dead ends: 90 [2022-04-06 23:18:52,854 INFO L226 Difference]: Without dead ends: 65 [2022-04-06 23:18:52,854 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 74 GetRequests, 67 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=27, Invalid=45, Unknown=0, NotChecked=0, Total=72 [2022-04-06 23:18:52,855 INFO L913 BasicCegarLoop]: 37 mSDtfsCounter, 2 mSDsluCounter, 89 mSDsCounter, 0 mSdLazyCounter, 17 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 126 SdHoareTripleChecker+Invalid, 20 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 17 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 23:18:52,855 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 126 Invalid, 20 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 17 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 23:18:52,855 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 65 states. [2022-04-06 23:18:52,860 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 65 to 65. [2022-04-06 23:18:52,861 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 65 states, 41 states have (on average 1.2195121951219512) internal successors, (50), 43 states have internal predecessors, (50), 15 states have call successors, (15), 9 states have call predecessors, (15), 8 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-06 23:18:52,861 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 65 states to 65 states and 78 transitions. [2022-04-06 23:18:52,862 INFO L78 Accepts]: Start accepts. Automaton has 65 states and 78 transitions. Word has length 37 [2022-04-06 23:18:52,862 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 23:18:52,862 INFO L478 AbstractCegarLoop]: Abstraction has 65 states and 78 transitions. [2022-04-06 23:18:52,862 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 4 states have call successors, (7), 4 states have call predecessors, (7), 3 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2022-04-06 23:18:52,862 INFO L276 IsEmpty]: Start isEmpty. Operand 65 states and 78 transitions. [2022-04-06 23:18:52,863 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2022-04-06 23:18:52,863 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:18:52,863 INFO L499 BasicCegarLoop]: trace histogram [6, 5, 5, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:18:52,880 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2022-04-06 23:18:53,080 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:18:53,080 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:18:53,081 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:18:53,081 INFO L85 PathProgramCache]: Analyzing trace with hash -1057559728, now seen corresponding path program 1 times [2022-04-06 23:18:53,081 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:18:53,081 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [829109934] [2022-04-06 23:18:53,085 INFO L97 AcceleratorQvasr]: Qvasr could not accelerate loop because java.lang.UnsupportedOperationException: Cannot deal with arrays. [2022-04-06 23:18:53,085 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-06 23:18:53,085 INFO L85 PathProgramCache]: Analyzing trace with hash -1057559728, now seen corresponding path program 2 times [2022-04-06 23:18:53,085 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:18:53,085 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [343245269] [2022-04-06 23:18:53,085 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:18:53,085 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:18:53,093 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 23:18:53,093 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1207754024] [2022-04-06 23:18:53,093 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 23:18:53,094 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:18:53,094 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 23:18:53,095 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 23:18:53,096 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2022-04-06 23:18:53,129 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 23:18:53,130 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 23:18:53,131 INFO L263 TraceCheckSpWp]: Trace formula consists of 130 conjuncts, 13 conjunts are in the unsatisfiable core [2022-04-06 23:18:53,132 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 23:18:53,259 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 10 proven. 5 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2022-04-06 23:18:53,259 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 23:18:53,353 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2022-04-06 23:18:53,353 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 23:18:53,353 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [343245269] [2022-04-06 23:18:53,353 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 23:18:53,354 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1207754024] [2022-04-06 23:18:53,354 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1207754024] provided 1 perfect and 1 imperfect interpolant sequences [2022-04-06 23:18:53,354 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-04-06 23:18:53,354 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2022-04-06 23:18:53,354 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 23:18:53,354 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [829109934] [2022-04-06 23:18:53,354 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [829109934] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:18:53,354 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:18:53,354 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 23:18:53,354 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1888574185] [2022-04-06 23:18:53,354 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 23:18:53,355 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 23:18:53,355 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 23:18:53,355 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 23:18:53,355 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2022-04-06 23:18:53,355 INFO L87 Difference]: Start difference. First operand 65 states and 78 transitions. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-06 23:18:53,394 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 23:18:53,394 INFO L93 Difference]: Finished difference Result 78 states and 95 transitions. [2022-04-06 23:18:53,394 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-06 23:18:53,395 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 40 [2022-04-06 23:18:53,395 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 23:18:53,395 INFO L225 Difference]: With dead ends: 78 [2022-04-06 23:18:53,395 INFO L226 Difference]: Without dead ends: 76 [2022-04-06 23:18:53,396 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 80 GetRequests, 72 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2022-04-06 23:18:53,396 INFO L913 BasicCegarLoop]: 34 mSDtfsCounter, 11 mSDsluCounter, 69 mSDsCounter, 0 mSdLazyCounter, 46 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 103 SdHoareTripleChecker+Invalid, 47 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 46 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 23:18:53,396 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 103 Invalid, 47 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 46 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 23:18:53,397 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 76 states. [2022-04-06 23:18:53,402 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 76 to 73. [2022-04-06 23:18:53,403 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 73 states, 46 states have (on average 1.2173913043478262) internal successors, (56), 49 states have internal predecessors, (56), 17 states have call successors, (17), 10 states have call predecessors, (17), 9 states have return successors, (15), 13 states have call predecessors, (15), 15 states have call successors, (15) [2022-04-06 23:18:53,418 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 73 states to 73 states and 88 transitions. [2022-04-06 23:18:53,418 INFO L78 Accepts]: Start accepts. Automaton has 73 states and 88 transitions. Word has length 40 [2022-04-06 23:18:53,419 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 23:18:53,419 INFO L478 AbstractCegarLoop]: Abstraction has 73 states and 88 transitions. [2022-04-06 23:18:53,419 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-06 23:18:53,419 INFO L276 IsEmpty]: Start isEmpty. Operand 73 states and 88 transitions. [2022-04-06 23:18:53,419 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 54 [2022-04-06 23:18:53,420 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:18:53,420 INFO L499 BasicCegarLoop]: trace histogram [8, 7, 7, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:18:53,437 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2022-04-06 23:18:53,634 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:18:53,635 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:18:53,635 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:18:53,635 INFO L85 PathProgramCache]: Analyzing trace with hash 529029787, now seen corresponding path program 1 times [2022-04-06 23:18:53,635 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:18:53,635 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [164965987] [2022-04-06 23:18:53,641 INFO L97 AcceleratorQvasr]: Qvasr could not accelerate loop because java.lang.UnsupportedOperationException: Cannot deal with arrays. [2022-04-06 23:18:53,641 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-06 23:18:53,641 INFO L85 PathProgramCache]: Analyzing trace with hash 529029787, now seen corresponding path program 2 times [2022-04-06 23:18:53,641 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:18:53,641 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1764790444] [2022-04-06 23:18:53,641 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:18:53,642 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:18:53,660 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 23:18:53,661 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [874770739] [2022-04-06 23:18:53,661 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 23:18:53,661 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:18:53,661 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 23:18:53,676 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 23:18:53,680 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2022-04-06 23:18:53,736 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 23:18:53,736 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 23:18:53,737 INFO L263 TraceCheckSpWp]: Trace formula consists of 154 conjuncts, 9 conjunts are in the unsatisfiable core [2022-04-06 23:18:53,746 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 23:18:53,847 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 36 proven. 42 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2022-04-06 23:18:53,847 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 23:18:53,979 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 14 proven. 6 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2022-04-06 23:18:53,980 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 23:18:53,980 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1764790444] [2022-04-06 23:18:53,980 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 23:18:53,980 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [874770739] [2022-04-06 23:18:53,980 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [874770739] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 23:18:53,980 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 23:18:53,980 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2022-04-06 23:18:53,981 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 23:18:53,981 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [164965987] [2022-04-06 23:18:53,981 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [164965987] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:18:53,981 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:18:53,981 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-06 23:18:53,981 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [453634913] [2022-04-06 23:18:53,981 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 23:18:53,982 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-06 23:18:53,982 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 23:18:53,982 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-06 23:18:53,982 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=46, Unknown=0, NotChecked=0, Total=72 [2022-04-06 23:18:53,982 INFO L87 Difference]: Start difference. First operand 73 states and 88 transitions. Second operand has 6 states, 6 states have (on average 3.6666666666666665) internal successors, (22), 5 states have internal predecessors, (22), 5 states have call successors, (10), 5 states have call predecessors, (10), 4 states have return successors, (8), 4 states have call predecessors, (8), 4 states have call successors, (8) [2022-04-06 23:18:54,030 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 23:18:54,030 INFO L93 Difference]: Finished difference Result 104 states and 120 transitions. [2022-04-06 23:18:54,031 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-04-06 23:18:54,031 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 3.6666666666666665) internal successors, (22), 5 states have internal predecessors, (22), 5 states have call successors, (10), 5 states have call predecessors, (10), 4 states have return successors, (8), 4 states have call predecessors, (8), 4 states have call successors, (8) Word has length 53 [2022-04-06 23:18:54,031 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 23:18:54,032 INFO L225 Difference]: With dead ends: 104 [2022-04-06 23:18:54,032 INFO L226 Difference]: Without dead ends: 92 [2022-04-06 23:18:54,033 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 105 GetRequests, 97 SyntacticMatches, 1 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=26, Invalid=46, Unknown=0, NotChecked=0, Total=72 [2022-04-06 23:18:54,033 INFO L913 BasicCegarLoop]: 39 mSDtfsCounter, 6 mSDsluCounter, 78 mSDsCounter, 0 mSdLazyCounter, 27 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 117 SdHoareTripleChecker+Invalid, 33 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 27 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 23:18:54,034 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 117 Invalid, 33 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 27 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 23:18:54,034 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 92 states. [2022-04-06 23:18:54,043 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 92 to 91. [2022-04-06 23:18:54,043 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 91 states, 58 states have (on average 1.1896551724137931) internal successors, (69), 61 states have internal predecessors, (69), 20 states have call successors, (20), 13 states have call predecessors, (20), 12 states have return successors, (18), 16 states have call predecessors, (18), 18 states have call successors, (18) [2022-04-06 23:18:54,044 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 91 states to 91 states and 107 transitions. [2022-04-06 23:18:54,044 INFO L78 Accepts]: Start accepts. Automaton has 91 states and 107 transitions. Word has length 53 [2022-04-06 23:18:54,044 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 23:18:54,045 INFO L478 AbstractCegarLoop]: Abstraction has 91 states and 107 transitions. [2022-04-06 23:18:54,045 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 3.6666666666666665) internal successors, (22), 5 states have internal predecessors, (22), 5 states have call successors, (10), 5 states have call predecessors, (10), 4 states have return successors, (8), 4 states have call predecessors, (8), 4 states have call successors, (8) [2022-04-06 23:18:54,045 INFO L276 IsEmpty]: Start isEmpty. Operand 91 states and 107 transitions. [2022-04-06 23:18:54,045 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2022-04-06 23:18:54,045 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:18:54,046 INFO L499 BasicCegarLoop]: trace histogram [8, 7, 7, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:18:54,071 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2022-04-06 23:18:54,271 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:18:54,272 INFO L403 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:18:54,272 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:18:54,272 INFO L85 PathProgramCache]: Analyzing trace with hash 1864650262, now seen corresponding path program 3 times [2022-04-06 23:18:54,272 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:18:54,272 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [403370500] [2022-04-06 23:18:54,276 INFO L97 AcceleratorQvasr]: Qvasr could not accelerate loop because java.lang.UnsupportedOperationException: Cannot deal with arrays. [2022-04-06 23:18:54,276 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-06 23:18:54,276 INFO L85 PathProgramCache]: Analyzing trace with hash 1864650262, now seen corresponding path program 4 times [2022-04-06 23:18:54,276 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:18:54,276 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1836934017] [2022-04-06 23:18:54,277 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:18:54,277 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:18:54,284 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 23:18:54,284 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1064922253] [2022-04-06 23:18:54,284 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-04-06 23:18:54,284 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:18:54,284 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 23:18:54,291 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 23:18:54,297 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2022-04-06 23:18:54,340 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-04-06 23:18:54,340 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 23:18:54,341 INFO L263 TraceCheckSpWp]: Trace formula consists of 163 conjuncts, 9 conjunts are in the unsatisfiable core [2022-04-06 23:18:54,342 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 23:18:54,644 INFO L134 CoverageAnalysis]: Checked inductivity of 108 backedges. 36 proven. 46 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2022-04-06 23:18:54,645 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 23:18:54,718 INFO L134 CoverageAnalysis]: Checked inductivity of 108 backedges. 14 proven. 10 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2022-04-06 23:18:54,718 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 23:18:54,718 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1836934017] [2022-04-06 23:18:54,718 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 23:18:54,718 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1064922253] [2022-04-06 23:18:54,718 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1064922253] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 23:18:54,719 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 23:18:54,719 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2022-04-06 23:18:54,721 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 23:18:54,721 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [403370500] [2022-04-06 23:18:54,721 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [403370500] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:18:54,721 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:18:54,721 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-06 23:18:54,721 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1920507019] [2022-04-06 23:18:54,721 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 23:18:54,722 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-06 23:18:54,722 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 23:18:54,735 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-06 23:18:54,735 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=46, Unknown=0, NotChecked=0, Total=72 [2022-04-06 23:18:54,736 INFO L87 Difference]: Start difference. First operand 91 states and 107 transitions. Second operand has 6 states, 6 states have (on average 4.0) internal successors, (24), 5 states have internal predecessors, (24), 5 states have call successors, (10), 5 states have call predecessors, (10), 4 states have return successors, (8), 4 states have call predecessors, (8), 4 states have call successors, (8) [2022-04-06 23:18:54,771 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 23:18:54,771 INFO L93 Difference]: Finished difference Result 126 states and 155 transitions. [2022-04-06 23:18:54,772 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-04-06 23:18:54,772 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 4.0) internal successors, (24), 5 states have internal predecessors, (24), 5 states have call successors, (10), 5 states have call predecessors, (10), 4 states have return successors, (8), 4 states have call predecessors, (8), 4 states have call successors, (8) Word has length 55 [2022-04-06 23:18:54,776 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 23:18:54,785 INFO L225 Difference]: With dead ends: 126 [2022-04-06 23:18:54,786 INFO L226 Difference]: Without dead ends: 93 [2022-04-06 23:18:54,786 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 111 GetRequests, 101 SyntacticMatches, 1 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=42, Invalid=68, Unknown=0, NotChecked=0, Total=110 [2022-04-06 23:18:54,787 INFO L913 BasicCegarLoop]: 39 mSDtfsCounter, 5 mSDsluCounter, 76 mSDsCounter, 0 mSdLazyCounter, 29 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 115 SdHoareTripleChecker+Invalid, 35 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 29 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 23:18:54,787 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [5 Valid, 115 Invalid, 35 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 29 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 23:18:54,787 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 93 states. [2022-04-06 23:18:54,810 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 93 to 93. [2022-04-06 23:18:54,811 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 93 states, 60 states have (on average 1.1833333333333333) internal successors, (71), 63 states have internal predecessors, (71), 20 states have call successors, (20), 13 states have call predecessors, (20), 12 states have return successors, (18), 16 states have call predecessors, (18), 18 states have call successors, (18) [2022-04-06 23:18:54,813 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 109 transitions. [2022-04-06 23:18:54,813 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 109 transitions. Word has length 55 [2022-04-06 23:18:54,813 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 23:18:54,814 INFO L478 AbstractCegarLoop]: Abstraction has 93 states and 109 transitions. [2022-04-06 23:18:54,814 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 4.0) internal successors, (24), 5 states have internal predecessors, (24), 5 states have call successors, (10), 5 states have call predecessors, (10), 4 states have return successors, (8), 4 states have call predecessors, (8), 4 states have call successors, (8) [2022-04-06 23:18:54,814 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 109 transitions. [2022-04-06 23:18:54,817 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 63 [2022-04-06 23:18:54,818 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:18:54,818 INFO L499 BasicCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:18:54,856 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2022-04-06 23:18:55,039 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:18:55,040 INFO L403 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:18:55,040 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:18:55,040 INFO L85 PathProgramCache]: Analyzing trace with hash -43330764, now seen corresponding path program 1 times [2022-04-06 23:18:55,040 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:18:55,040 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [325640272] [2022-04-06 23:18:55,043 INFO L97 AcceleratorQvasr]: Qvasr could not accelerate loop because java.lang.UnsupportedOperationException: Cannot deal with arrays. [2022-04-06 23:18:55,043 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-06 23:18:55,043 INFO L85 PathProgramCache]: Analyzing trace with hash -43330764, now seen corresponding path program 2 times [2022-04-06 23:18:55,044 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:18:55,044 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1803171246] [2022-04-06 23:18:55,044 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:18:55,044 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:18:55,049 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 23:18:55,050 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [798751898] [2022-04-06 23:18:55,050 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 23:18:55,050 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:18:55,050 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 23:18:55,051 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 23:18:55,052 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2022-04-06 23:18:55,089 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 23:18:55,089 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 23:18:55,090 INFO L263 TraceCheckSpWp]: Trace formula consists of 178 conjuncts, 11 conjunts are in the unsatisfiable core [2022-04-06 23:18:55,091 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 23:18:55,194 INFO L134 CoverageAnalysis]: Checked inductivity of 136 backedges. 16 proven. 92 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2022-04-06 23:18:55,194 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 23:18:55,299 INFO L134 CoverageAnalysis]: Checked inductivity of 136 backedges. 16 proven. 8 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2022-04-06 23:18:55,299 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 23:18:55,300 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1803171246] [2022-04-06 23:18:55,300 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 23:18:55,300 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [798751898] [2022-04-06 23:18:55,300 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [798751898] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 23:18:55,300 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 23:18:55,300 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 9 [2022-04-06 23:18:55,300 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 23:18:55,300 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [325640272] [2022-04-06 23:18:55,300 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [325640272] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:18:55,300 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:18:55,300 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2022-04-06 23:18:55,300 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2131352234] [2022-04-06 23:18:55,300 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 23:18:55,301 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-04-06 23:18:55,301 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 23:18:55,301 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-04-06 23:18:55,301 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=46, Unknown=0, NotChecked=0, Total=72 [2022-04-06 23:18:55,301 INFO L87 Difference]: Start difference. First operand 93 states and 109 transitions. Second operand has 7 states, 7 states have (on average 3.857142857142857) internal successors, (27), 6 states have internal predecessors, (27), 6 states have call successors, (11), 6 states have call predecessors, (11), 4 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) [2022-04-06 23:18:55,357 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 23:18:55,357 INFO L93 Difference]: Finished difference Result 145 states and 168 transitions. [2022-04-06 23:18:55,357 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-04-06 23:18:55,358 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 3.857142857142857) internal successors, (27), 6 states have internal predecessors, (27), 6 states have call successors, (11), 6 states have call predecessors, (11), 4 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) Word has length 62 [2022-04-06 23:18:55,358 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 23:18:55,359 INFO L225 Difference]: With dead ends: 145 [2022-04-06 23:18:55,359 INFO L226 Difference]: Without dead ends: 130 [2022-04-06 23:18:55,359 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 124 GetRequests, 115 SyntacticMatches, 1 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=32, Invalid=58, Unknown=0, NotChecked=0, Total=90 [2022-04-06 23:18:55,359 INFO L913 BasicCegarLoop]: 47 mSDtfsCounter, 23 mSDsluCounter, 125 mSDsCounter, 0 mSdLazyCounter, 52 mSolverCounterSat, 18 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 23 SdHoareTripleChecker+Valid, 172 SdHoareTripleChecker+Invalid, 70 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 18 IncrementalHoareTripleChecker+Valid, 52 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 23:18:55,359 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [23 Valid, 172 Invalid, 70 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [18 Valid, 52 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 23:18:55,360 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 130 states. [2022-04-06 23:18:55,380 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 130 to 127. [2022-04-06 23:18:55,380 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 127 states, 83 states have (on average 1.1686746987951808) internal successors, (97), 86 states have internal predecessors, (97), 27 states have call successors, (27), 18 states have call predecessors, (27), 16 states have return successors, (24), 22 states have call predecessors, (24), 24 states have call successors, (24) [2022-04-06 23:18:55,381 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 127 states to 127 states and 148 transitions. [2022-04-06 23:18:55,381 INFO L78 Accepts]: Start accepts. Automaton has 127 states and 148 transitions. Word has length 62 [2022-04-06 23:18:55,381 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 23:18:55,381 INFO L478 AbstractCegarLoop]: Abstraction has 127 states and 148 transitions. [2022-04-06 23:18:55,381 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 3.857142857142857) internal successors, (27), 6 states have internal predecessors, (27), 6 states have call successors, (11), 6 states have call predecessors, (11), 4 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) [2022-04-06 23:18:55,381 INFO L276 IsEmpty]: Start isEmpty. Operand 127 states and 148 transitions. [2022-04-06 23:18:55,382 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 63 [2022-04-06 23:18:55,382 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:18:55,382 INFO L499 BasicCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:18:55,402 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2022-04-06 23:18:55,599 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2022-04-06 23:18:55,600 INFO L403 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:18:55,600 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:18:55,600 INFO L85 PathProgramCache]: Analyzing trace with hash -41602886, now seen corresponding path program 1 times [2022-04-06 23:18:55,600 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:18:55,600 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1898996220] [2022-04-06 23:18:55,605 INFO L97 AcceleratorQvasr]: Qvasr could not accelerate loop because java.lang.UnsupportedOperationException: Cannot deal with arrays. [2022-04-06 23:18:55,605 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-06 23:18:55,605 INFO L85 PathProgramCache]: Analyzing trace with hash -41602886, now seen corresponding path program 2 times [2022-04-06 23:18:55,605 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:18:55,605 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [940373260] [2022-04-06 23:18:55,605 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:18:55,605 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:18:55,610 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 23:18:55,611 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [358461851] [2022-04-06 23:18:55,611 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 23:18:55,611 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:18:55,611 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 23:18:55,616 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 23:18:55,617 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2022-04-06 23:18:55,655 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 23:18:55,656 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 23:18:55,657 INFO L263 TraceCheckSpWp]: Trace formula consists of 178 conjuncts, 25 conjunts are in the unsatisfiable core [2022-04-06 23:18:55,663 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 23:18:55,966 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 16 proven. 9 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2022-04-06 23:18:55,966 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 23:18:56,763 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 16 proven. 9 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2022-04-06 23:18:56,763 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 23:18:56,763 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [940373260] [2022-04-06 23:18:56,763 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 23:18:56,763 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [358461851] [2022-04-06 23:18:56,763 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [358461851] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 23:18:56,763 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 23:18:56,763 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2022-04-06 23:18:56,764 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 23:18:56,764 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1898996220] [2022-04-06 23:18:56,764 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1898996220] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:18:56,764 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:18:56,764 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2022-04-06 23:18:56,764 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1577780237] [2022-04-06 23:18:56,764 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 23:18:56,764 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-04-06 23:18:56,764 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 23:18:56,765 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-04-06 23:18:56,765 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=66, Unknown=0, NotChecked=0, Total=90 [2022-04-06 23:18:56,765 INFO L87 Difference]: Start difference. First operand 127 states and 148 transitions. Second operand has 7 states, 7 states have (on average 3.0) internal successors, (21), 6 states have internal predecessors, (21), 4 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2022-04-06 23:18:56,890 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 23:18:56,890 INFO L93 Difference]: Finished difference Result 181 states and 219 transitions. [2022-04-06 23:18:56,890 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-04-06 23:18:56,890 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 3.0) internal successors, (21), 6 states have internal predecessors, (21), 4 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) Word has length 62 [2022-04-06 23:18:56,890 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 23:18:56,891 INFO L225 Difference]: With dead ends: 181 [2022-04-06 23:18:56,891 INFO L226 Difference]: Without dead ends: 137 [2022-04-06 23:18:56,892 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 124 GetRequests, 112 SyntacticMatches, 3 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=28, Invalid=82, Unknown=0, NotChecked=0, Total=110 [2022-04-06 23:18:56,892 INFO L913 BasicCegarLoop]: 50 mSDtfsCounter, 13 mSDsluCounter, 137 mSDsCounter, 0 mSdLazyCounter, 209 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 187 SdHoareTripleChecker+Invalid, 223 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 209 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 23:18:56,892 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [19 Valid, 187 Invalid, 223 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 209 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 23:18:56,893 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 137 states. [2022-04-06 23:18:56,899 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 137 to 135. [2022-04-06 23:18:56,900 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 135 states, 89 states have (on average 1.1685393258426966) internal successors, (104), 92 states have internal predecessors, (104), 27 states have call successors, (27), 19 states have call predecessors, (27), 18 states have return successors, (25), 23 states have call predecessors, (25), 25 states have call successors, (25) [2022-04-06 23:18:56,900 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 135 states to 135 states and 156 transitions. [2022-04-06 23:18:56,901 INFO L78 Accepts]: Start accepts. Automaton has 135 states and 156 transitions. Word has length 62 [2022-04-06 23:18:56,901 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 23:18:56,901 INFO L478 AbstractCegarLoop]: Abstraction has 135 states and 156 transitions. [2022-04-06 23:18:56,901 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 3.0) internal successors, (21), 6 states have internal predecessors, (21), 4 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2022-04-06 23:18:56,901 INFO L276 IsEmpty]: Start isEmpty. Operand 135 states and 156 transitions. [2022-04-06 23:18:56,901 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 68 [2022-04-06 23:18:56,902 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:18:56,902 INFO L499 BasicCegarLoop]: trace histogram [10, 9, 9, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:18:56,920 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2022-04-06 23:18:57,119 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2022-04-06 23:18:57,119 INFO L403 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:18:57,119 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:18:57,119 INFO L85 PathProgramCache]: Analyzing trace with hash -378736343, now seen corresponding path program 3 times [2022-04-06 23:18:57,120 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:18:57,120 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1782325971] [2022-04-06 23:18:57,123 INFO L97 AcceleratorQvasr]: Qvasr could not accelerate loop because java.lang.UnsupportedOperationException: Cannot deal with arrays. [2022-04-06 23:18:57,123 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-06 23:18:57,123 INFO L85 PathProgramCache]: Analyzing trace with hash -378736343, now seen corresponding path program 4 times [2022-04-06 23:18:57,124 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:18:57,124 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1806209566] [2022-04-06 23:18:57,124 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:18:57,124 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:18:57,130 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 23:18:57,130 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1122913972] [2022-04-06 23:18:57,131 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-04-06 23:18:57,131 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:18:57,131 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 23:18:57,132 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 23:18:57,163 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2022-04-06 23:18:57,172 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-04-06 23:18:57,172 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 23:18:57,173 INFO L263 TraceCheckSpWp]: Trace formula consists of 148 conjuncts, 37 conjunts are in the unsatisfiable core [2022-04-06 23:18:57,175 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 23:19:05,694 INFO L134 CoverageAnalysis]: Checked inductivity of 172 backedges. 59 proven. 29 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2022-04-06 23:19:05,694 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 23:19:06,242 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-04-06 23:20:35,854 WARN L232 SmtUtils]: Spent 7.06s on a formula simplification that was a NOOP. DAG size: 6 (called from [L1067] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify)