/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/ps6-ll_unwindbound10.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-34549b5 [2022-04-07 00:33:16,046 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-07 00:33:16,048 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-07 00:33:16,085 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-07 00:33:16,085 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-07 00:33:16,086 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-07 00:33:16,088 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-07 00:33:16,090 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-07 00:33:16,091 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-07 00:33:16,095 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-07 00:33:16,096 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-07 00:33:16,097 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-07 00:33:16,097 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-07 00:33:16,098 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-07 00:33:16,099 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-07 00:33:16,101 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-07 00:33:16,102 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-07 00:33:16,102 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-07 00:33:16,104 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-07 00:33:16,108 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-07 00:33:16,110 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-07 00:33:16,111 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-07 00:33:16,111 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-07 00:33:16,112 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-07 00:33:16,113 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-07 00:33:16,128 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-07 00:33:16,128 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-07 00:33:16,128 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-07 00:33:16,129 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-07 00:33:16,129 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-07 00:33:16,130 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-07 00:33:16,130 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-07 00:33:16,130 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-07 00:33:16,131 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-07 00:33:16,131 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-07 00:33:16,132 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-07 00:33:16,132 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-07 00:33:16,132 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-07 00:33:16,132 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-07 00:33:16,133 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-07 00:33:16,133 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-07 00:33:16,134 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-07 00:33:16,135 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationQvasr_64.epf [2022-04-07 00:33:16,140 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-07 00:33:16,140 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-07 00:33:16,141 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-07 00:33:16,141 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-07 00:33:16,141 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-07 00:33:16,142 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-07 00:33:16,142 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-07 00:33:16,142 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-07 00:33:16,142 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-07 00:33:16,142 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-07 00:33:16,142 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-07 00:33:16,142 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-07 00:33:16,142 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-07 00:33:16,142 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-04-07 00:33:16,143 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-07 00:33:16,143 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-07 00:33:16,143 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-07 00:33:16,145 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_NestedInterpolation [2022-04-07 00:33:16,146 INFO L138 SettingsManager]: * Trace refinement strategy=ACCELERATED_INTERPOLATION [2022-04-07 00:33:16,146 INFO L138 SettingsManager]: * Trace refinement strategy used in Accelerated Interpolation=CAMEL [2022-04-07 00:33:16,146 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-04-07 00:33:16,146 INFO L138 SettingsManager]: * Loop acceleration method that is used by accelerated interpolation=QVASR [2022-04-07 00:33:16,146 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-07 00:33:16,356 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-07 00:33:16,384 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-07 00:33:16,386 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-07 00:33:16,387 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-07 00:33:16,388 INFO L275 PluginConnector]: CDTParser initialized [2022-04-07 00:33:16,389 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/ps6-ll_unwindbound10.c [2022-04-07 00:33:16,434 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/40942b7a7/5885d710c0f54042b03f9f60a7afa61d/FLAGce29cc410 [2022-04-07 00:33:16,805 INFO L306 CDTParser]: Found 1 translation units. [2022-04-07 00:33:16,806 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/ps6-ll_unwindbound10.c [2022-04-07 00:33:16,810 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/40942b7a7/5885d710c0f54042b03f9f60a7afa61d/FLAGce29cc410 [2022-04-07 00:33:16,819 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/40942b7a7/5885d710c0f54042b03f9f60a7afa61d [2022-04-07 00:33:16,821 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-07 00:33:16,821 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-04-07 00:33:16,823 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-07 00:33:16,823 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-07 00:33:16,825 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-07 00:33:16,826 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 07.04 12:33:16" (1/1) ... [2022-04-07 00:33:16,826 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@134d75a6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.04 12:33:16, skipping insertion in model container [2022-04-07 00:33:16,826 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 07.04 12:33:16" (1/1) ... [2022-04-07 00:33:16,856 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-07 00:33:16,869 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-07 00:33:17,031 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/ps6-ll_unwindbound10.c[458,471] [2022-04-07 00:33:17,054 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-07 00:33:17,061 INFO L203 MainTranslator]: Completed pre-run [2022-04-07 00:33:17,070 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/ps6-ll_unwindbound10.c[458,471] [2022-04-07 00:33:17,090 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-07 00:33:17,101 INFO L208 MainTranslator]: Completed translation [2022-04-07 00:33:17,102 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.04 12:33:17 WrapperNode [2022-04-07 00:33:17,102 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-07 00:33:17,103 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-07 00:33:17,103 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-07 00:33:17,103 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-07 00:33:17,111 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.04 12:33:17" (1/1) ... [2022-04-07 00:33:17,111 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.04 12:33:17" (1/1) ... [2022-04-07 00:33:17,116 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.04 12:33:17" (1/1) ... [2022-04-07 00:33:17,116 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.04 12:33:17" (1/1) ... [2022-04-07 00:33:17,126 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.04 12:33:17" (1/1) ... [2022-04-07 00:33:17,129 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.04 12:33:17" (1/1) ... [2022-04-07 00:33:17,131 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.04 12:33:17" (1/1) ... [2022-04-07 00:33:17,135 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-07 00:33:17,137 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-07 00:33:17,137 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-07 00:33:17,137 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-07 00:33:17,138 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.04 12:33:17" (1/1) ... [2022-04-07 00:33:17,143 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-07 00:33:17,150 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-07 00:33:17,187 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-07 00:33:17,202 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-07 00:33:17,221 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-07 00:33:17,221 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-07 00:33:17,221 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-07 00:33:17,222 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-07 00:33:17,222 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-07 00:33:17,222 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-07 00:33:17,222 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-07 00:33:17,222 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-07 00:33:17,222 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-07 00:33:17,223 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-07 00:33:17,223 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_short [2022-04-07 00:33:17,224 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-07 00:33:17,224 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-07 00:33:17,224 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-07 00:33:17,225 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-07 00:33:17,225 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-07 00:33:17,226 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-07 00:33:17,226 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-07 00:33:17,226 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-07 00:33:17,226 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-07 00:33:17,266 INFO L234 CfgBuilder]: Building ICFG [2022-04-07 00:33:17,268 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-07 00:33:17,351 INFO L275 CfgBuilder]: Performing block encoding [2022-04-07 00:33:17,355 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-07 00:33:17,355 INFO L299 CfgBuilder]: Removed 1 assume(true) statements. [2022-04-07 00:33:17,356 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 07.04 12:33:17 BoogieIcfgContainer [2022-04-07 00:33:17,356 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-07 00:33:17,357 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-07 00:33:17,357 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-07 00:33:17,360 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-07 00:33:17,360 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 07.04 12:33:16" (1/3) ... [2022-04-07 00:33:17,360 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@443a339 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 07.04 12:33:17, skipping insertion in model container [2022-04-07 00:33:17,361 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.04 12:33:17" (2/3) ... [2022-04-07 00:33:17,361 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@443a339 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 07.04 12:33:17, skipping insertion in model container [2022-04-07 00:33:17,361 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 07.04 12:33:17" (3/3) ... [2022-04-07 00:33:17,362 INFO L111 eAbstractionObserver]: Analyzing ICFG ps6-ll_unwindbound10.c [2022-04-07 00:33:17,365 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:Craig_NestedInterpolation Determinization: PREDICATE_ABSTRACTION [2022-04-07 00:33:17,365 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-07 00:33:17,406 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-07 00:33:17,411 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-07 00:33:17,411 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-07 00:33:17,420 INFO L276 IsEmpty]: Start isEmpty. Operand has 29 states, 17 states have (on average 1.3529411764705883) internal successors, (23), 18 states have internal predecessors, (23), 6 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-07 00:33:17,425 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2022-04-07 00:33:17,425 INFO L491 BasicCegarLoop]: Found error trace [2022-04-07 00:33:17,425 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-07 00:33:17,437 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-07 00:33:17,450 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-07 00:33:17,451 INFO L85 PathProgramCache]: Analyzing trace with hash 21872251, now seen corresponding path program 1 times [2022-04-07 00:33:17,472 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-07 00:33:17,472 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1167246896] [2022-04-07 00:33:17,480 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-07 00:33:17,480 INFO L85 PathProgramCache]: Analyzing trace with hash 21872251, now seen corresponding path program 2 times [2022-04-07 00:33:17,482 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-07 00:33:17,482 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [966771532] [2022-04-07 00:33:17,482 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-07 00:33:17,483 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-07 00:33:17,594 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 00:33:17,656 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-07 00:33:17,668 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 00:33:17,680 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-07 00:33:17,682 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 00:33:17,690 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-07 00:33:17,691 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-07 00:33:17,692 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [966771532] [2022-04-07 00:33:17,692 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [966771532] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-07 00:33:17,692 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-07 00:33:17,693 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-07 00:33:17,695 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-07 00:33:17,696 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1167246896] [2022-04-07 00:33:17,696 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1167246896] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-07 00:33:17,697 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-07 00:33:17,697 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-07 00:33:17,697 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1716964403] [2022-04-07 00:33:17,698 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-07 00:33:17,701 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-07 00:33:17,701 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-07 00:33:17,720 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-07 00:33:17,721 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-07 00:33:17,722 INFO L87 Difference]: Start difference. First operand has 29 states, 17 states have (on average 1.3529411764705883) internal successors, (23), 18 states have internal predecessors, (23), 6 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Second operand has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-07 00:33:17,807 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 00:33:17,808 INFO L93 Difference]: Finished difference Result 50 states and 65 transitions. [2022-04-07 00:33:17,809 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-07 00:33:17,809 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 17 [2022-04-07 00:33:17,810 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-07 00:33:17,815 INFO L225 Difference]: With dead ends: 50 [2022-04-07 00:33:17,815 INFO L226 Difference]: Without dead ends: 25 [2022-04-07 00:33:17,820 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 6 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-07 00:33:17,825 INFO L913 BasicCegarLoop]: 30 mSDtfsCounter, 10 mSDsluCounter, 4 mSDsCounter, 0 mSdLazyCounter, 13 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 34 SdHoareTripleChecker+Invalid, 18 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 13 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-07 00:33:17,826 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 34 Invalid, 18 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 13 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-07 00:33:17,837 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states. [2022-04-07 00:33:17,854 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 24. [2022-04-07 00:33:17,855 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24 states, 14 states have (on average 1.2142857142857142) internal successors, (17), 15 states have internal predecessors, (17), 6 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2022-04-07 00:33:17,857 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 27 transitions. [2022-04-07 00:33:17,858 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 27 transitions. Word has length 17 [2022-04-07 00:33:17,858 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-07 00:33:17,859 INFO L478 AbstractCegarLoop]: Abstraction has 24 states and 27 transitions. [2022-04-07 00:33:17,859 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-07 00:33:17,859 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 27 transitions. [2022-04-07 00:33:17,860 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2022-04-07 00:33:17,860 INFO L491 BasicCegarLoop]: Found error trace [2022-04-07 00:33:17,860 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-07 00:33:17,860 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-07 00:33:17,860 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-07 00:33:17,862 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-07 00:33:17,862 INFO L85 PathProgramCache]: Analyzing trace with hash -119968982, now seen corresponding path program 1 times [2022-04-07 00:33:17,862 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-07 00:33:17,862 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1315568527] [2022-04-07 00:33:17,870 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-07 00:33:17,870 INFO L85 PathProgramCache]: Analyzing trace with hash -119968982, now seen corresponding path program 2 times [2022-04-07 00:33:17,870 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-07 00:33:17,871 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1863282537] [2022-04-07 00:33:17,871 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-07 00:33:17,871 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-07 00:33:17,894 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-07 00:33:17,897 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [376387267] [2022-04-07 00:33:17,898 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-07 00:33:17,899 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-07 00:33:17,899 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-07 00:33:17,904 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-07 00:33:17,905 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-07 00:33:17,953 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2022-04-07 00:33:17,954 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-07 00:33:17,955 INFO L263 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 5 conjunts are in the unsatisfiable core [2022-04-07 00:33:17,959 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-07 00:33:18,019 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-07 00:33:18,019 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-07 00:33:18,020 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-07 00:33:18,020 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1863282537] [2022-04-07 00:33:18,020 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-07 00:33:18,020 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [376387267] [2022-04-07 00:33:18,020 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [376387267] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-07 00:33:18,020 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-07 00:33:18,020 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-04-07 00:33:18,021 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-07 00:33:18,021 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1315568527] [2022-04-07 00:33:18,021 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1315568527] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-07 00:33:18,022 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-07 00:33:18,022 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-04-07 00:33:18,022 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1063313187] [2022-04-07 00:33:18,022 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-07 00:33:18,022 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2022-04-07 00:33:18,022 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-07 00:33:18,023 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2022-04-07 00:33:18,023 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-04-07 00:33:18,023 INFO L87 Difference]: Start difference. First operand 24 states and 27 transitions. Second operand has 4 states, 4 states have (on average 3.0) internal successors, (12), 3 states have internal predecessors, (12), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-07 00:33:18,032 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 00:33:18,033 INFO L93 Difference]: Finished difference Result 34 states and 38 transitions. [2022-04-07 00:33:18,033 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2022-04-07 00:33:18,033 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 3.0) internal successors, (12), 3 states have internal predecessors, (12), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Word has length 18 [2022-04-07 00:33:18,033 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-07 00:33:18,034 INFO L225 Difference]: With dead ends: 34 [2022-04-07 00:33:18,034 INFO L226 Difference]: Without dead ends: 26 [2022-04-07 00:33:18,034 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 15 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-04-07 00:33:18,035 INFO L913 BasicCegarLoop]: 25 mSDtfsCounter, 0 mSDsluCounter, 38 mSDsCounter, 0 mSdLazyCounter, 7 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 63 SdHoareTripleChecker+Invalid, 7 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 7 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-07 00:33:18,035 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 63 Invalid, 7 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 7 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-07 00:33:18,036 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26 states. [2022-04-07 00:33:18,040 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26 to 26. [2022-04-07 00:33:18,040 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 16 states have (on average 1.1875) internal successors, (19), 17 states have internal predecessors, (19), 6 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2022-04-07 00:33:18,041 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 29 transitions. [2022-04-07 00:33:18,041 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 29 transitions. Word has length 18 [2022-04-07 00:33:18,041 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-07 00:33:18,041 INFO L478 AbstractCegarLoop]: Abstraction has 26 states and 29 transitions. [2022-04-07 00:33:18,041 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 3.0) internal successors, (12), 3 states have internal predecessors, (12), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-07 00:33:18,041 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 29 transitions. [2022-04-07 00:33:18,042 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2022-04-07 00:33:18,042 INFO L491 BasicCegarLoop]: Found error trace [2022-04-07 00:33:18,042 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-07 00:33:18,059 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2022-04-07 00:33:18,256 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-07 00:33:18,256 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-07 00:33:18,256 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-07 00:33:18,256 INFO L85 PathProgramCache]: Analyzing trace with hash -118181522, now seen corresponding path program 1 times [2022-04-07 00:33:18,257 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-07 00:33:18,257 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1004455920] [2022-04-07 00:33:18,257 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-07 00:33:18,257 INFO L85 PathProgramCache]: Analyzing trace with hash -118181522, now seen corresponding path program 2 times [2022-04-07 00:33:18,257 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-07 00:33:18,257 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2019573436] [2022-04-07 00:33:18,258 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-07 00:33:18,258 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-07 00:33:18,265 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-07 00:33:18,266 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [478122013] [2022-04-07 00:33:18,266 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-07 00:33:18,266 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-07 00:33:18,266 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-07 00:33:18,267 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-07 00:33:18,268 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-07 00:33:18,305 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2022-04-07 00:33:18,305 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-07 00:33:18,318 INFO L263 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-07 00:33:18,320 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-07 00:33:18,413 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-07 00:33:18,414 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-07 00:33:18,414 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-07 00:33:18,414 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2019573436] [2022-04-07 00:33:18,414 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-07 00:33:18,414 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [478122013] [2022-04-07 00:33:18,414 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [478122013] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-07 00:33:18,414 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-07 00:33:18,415 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-07 00:33:18,415 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-07 00:33:18,415 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1004455920] [2022-04-07 00:33:18,415 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1004455920] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-07 00:33:18,415 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-07 00:33:18,415 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-07 00:33:18,415 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1952958496] [2022-04-07 00:33:18,415 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-07 00:33:18,416 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-07 00:33:18,416 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-07 00:33:18,416 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-07 00:33:18,416 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-07 00:33:18,417 INFO L87 Difference]: Start difference. First operand 26 states and 29 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, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-07 00:33:18,482 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 00:33:18,483 INFO L93 Difference]: Finished difference Result 36 states and 41 transitions. [2022-04-07 00:33:18,483 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-07 00:33:18,483 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, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 18 [2022-04-07 00:33:18,483 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-07 00:33:18,484 INFO L225 Difference]: With dead ends: 36 [2022-04-07 00:33:18,484 INFO L226 Difference]: Without dead ends: 32 [2022-04-07 00:33:18,484 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 18 GetRequests, 14 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-07 00:33:18,485 INFO L913 BasicCegarLoop]: 25 mSDtfsCounter, 6 mSDsluCounter, 62 mSDsCounter, 0 mSdLazyCounter, 29 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 87 SdHoareTripleChecker+Invalid, 31 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 29 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-07 00:33:18,485 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [8 Valid, 87 Invalid, 31 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 29 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-07 00:33:18,486 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2022-04-07 00:33:18,491 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2022-04-07 00:33:18,491 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 20 states have (on average 1.15) internal successors, (23), 21 states have internal predecessors, (23), 7 states have call successors, (7), 5 states have call predecessors, (7), 4 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-07 00:33:18,492 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 35 transitions. [2022-04-07 00:33:18,492 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 35 transitions. Word has length 18 [2022-04-07 00:33:18,492 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-07 00:33:18,492 INFO L478 AbstractCegarLoop]: Abstraction has 32 states and 35 transitions. [2022-04-07 00:33:18,492 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, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-07 00:33:18,493 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 35 transitions. [2022-04-07 00:33:18,493 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2022-04-07 00:33:18,493 INFO L491 BasicCegarLoop]: Found error trace [2022-04-07 00:33:18,493 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-07 00:33:18,512 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2022-04-07 00:33:18,694 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,SelfDestructingSolverStorable2 [2022-04-07 00:33:18,698 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-07 00:33:18,698 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-07 00:33:18,698 INFO L85 PathProgramCache]: Analyzing trace with hash -1364840471, now seen corresponding path program 1 times [2022-04-07 00:33:18,699 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-07 00:33:18,699 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [584458558] [2022-04-07 00:33:18,723 INFO L97 AcceleratorQvasr]: Qvasr could not accelerate loop because java.lang.UnsupportedOperationException: Cannot deal with arrays. [2022-04-07 00:33:18,728 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-07 00:33:18,728 INFO L85 PathProgramCache]: Analyzing trace with hash -1364840471, now seen corresponding path program 2 times [2022-04-07 00:33:18,728 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-07 00:33:18,729 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2139185405] [2022-04-07 00:33:18,729 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-07 00:33:18,730 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-07 00:33:18,768 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-07 00:33:18,768 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1221136382] [2022-04-07 00:33:18,769 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-07 00:33:18,769 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-07 00:33:18,769 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-07 00:33:18,786 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-07 00:33:18,796 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-07 00:33:19,020 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-07 00:33:19,020 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-07 00:33:19,022 INFO L263 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-07 00:33:19,023 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-07 00:33:19,100 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-07 00:33:19,101 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-07 00:33:19,191 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-07 00:33:19,191 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-07 00:33:19,192 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2139185405] [2022-04-07 00:33:19,192 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-07 00:33:19,192 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1221136382] [2022-04-07 00:33:19,192 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1221136382] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-07 00:33:19,192 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-07 00:33:19,192 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2022-04-07 00:33:19,192 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-07 00:33:19,192 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [584458558] [2022-04-07 00:33:19,193 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [584458558] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-07 00:33:19,193 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-07 00:33:19,193 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-07 00:33:19,193 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1379936150] [2022-04-07 00:33:19,193 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-07 00:33:19,193 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-07 00:33:19,193 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-07 00:33:19,194 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-07 00:33:19,194 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2022-04-07 00:33:19,194 INFO L87 Difference]: Start difference. First operand 32 states and 35 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, (5), 4 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 3 states have call successors, (3) [2022-04-07 00:33:19,224 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 00:33:19,224 INFO L93 Difference]: Finished difference Result 42 states and 46 transitions. [2022-04-07 00:33:19,224 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-04-07 00:33:19,224 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, (5), 4 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 3 states have call successors, (3) Word has length 26 [2022-04-07 00:33:19,225 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-07 00:33:19,225 INFO L225 Difference]: With dead ends: 42 [2022-04-07 00:33:19,225 INFO L226 Difference]: Without dead ends: 34 [2022-04-07 00:33:19,226 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 52 GetRequests, 45 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-07 00:33:19,226 INFO L913 BasicCegarLoop]: 26 mSDtfsCounter, 6 mSDsluCounter, 43 mSDsCounter, 0 mSdLazyCounter, 11 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 69 SdHoareTripleChecker+Invalid, 16 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 11 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-07 00:33:19,227 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 69 Invalid, 16 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 11 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-07 00:33:19,227 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 34 states. [2022-04-07 00:33:19,231 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 34 to 34. [2022-04-07 00:33:19,231 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 34 states, 22 states have (on average 1.1363636363636365) internal successors, (25), 23 states have internal predecessors, (25), 7 states have call successors, (7), 5 states have call predecessors, (7), 4 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-07 00:33:19,232 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 37 transitions. [2022-04-07 00:33:19,232 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 37 transitions. Word has length 26 [2022-04-07 00:33:19,232 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-07 00:33:19,232 INFO L478 AbstractCegarLoop]: Abstraction has 34 states and 37 transitions. [2022-04-07 00:33:19,232 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, (5), 4 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 3 states have call successors, (3) [2022-04-07 00:33:19,232 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 37 transitions. [2022-04-07 00:33:19,233 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2022-04-07 00:33:19,233 INFO L491 BasicCegarLoop]: Found error trace [2022-04-07 00:33:19,233 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-07 00:33:19,250 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2022-04-07 00:33:19,438 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-07 00:33:19,438 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-07 00:33:19,439 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-07 00:33:19,439 INFO L85 PathProgramCache]: Analyzing trace with hash -1363053011, now seen corresponding path program 1 times [2022-04-07 00:33:19,439 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-07 00:33:19,439 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1946057163] [2022-04-07 00:33:19,443 INFO L97 AcceleratorQvasr]: Qvasr could not accelerate loop because java.lang.UnsupportedOperationException: Cannot deal with arrays. [2022-04-07 00:33:19,443 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-07 00:33:19,443 INFO L85 PathProgramCache]: Analyzing trace with hash -1363053011, now seen corresponding path program 2 times [2022-04-07 00:33:19,443 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-07 00:33:19,443 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [293431608] [2022-04-07 00:33:19,443 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-07 00:33:19,443 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-07 00:33:19,452 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-07 00:33:19,452 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1192943295] [2022-04-07 00:33:19,452 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-07 00:33:19,452 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-07 00:33:19,452 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-07 00:33:19,476 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-07 00:33:19,511 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-07 00:33:19,558 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-07 00:33:19,558 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-07 00:33:19,559 INFO L263 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 11 conjunts are in the unsatisfiable core [2022-04-07 00:33:19,561 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-07 00:33:19,637 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 2 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-07 00:33:19,637 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-07 00:33:19,829 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2022-04-07 00:33:19,829 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-07 00:33:19,829 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [293431608] [2022-04-07 00:33:19,829 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-07 00:33:19,830 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1192943295] [2022-04-07 00:33:19,830 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1192943295] provided 1 perfect and 1 imperfect interpolant sequences [2022-04-07 00:33:19,830 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-04-07 00:33:19,830 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2022-04-07 00:33:19,830 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-07 00:33:19,830 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1946057163] [2022-04-07 00:33:19,830 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1946057163] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-07 00:33:19,830 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-07 00:33:19,830 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-07 00:33:19,830 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1475894673] [2022-04-07 00:33:19,831 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-07 00:33:19,831 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-07 00:33:19,831 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-07 00:33:19,831 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-07 00:33:19,831 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2022-04-07 00:33:19,831 INFO L87 Difference]: Start difference. First operand 34 states and 37 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 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-07 00:33:19,864 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 00:33:19,864 INFO L93 Difference]: Finished difference Result 40 states and 42 transitions. [2022-04-07 00:33:19,864 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-07 00:33:19,864 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 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 26 [2022-04-07 00:33:19,865 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-07 00:33:19,865 INFO L225 Difference]: With dead ends: 40 [2022-04-07 00:33:19,865 INFO L226 Difference]: Without dead ends: 36 [2022-04-07 00:33:19,865 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 52 GetRequests, 44 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2022-04-07 00:33:19,866 INFO L913 BasicCegarLoop]: 22 mSDtfsCounter, 7 mSDsluCounter, 51 mSDsCounter, 0 mSdLazyCounter, 25 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 73 SdHoareTripleChecker+Invalid, 26 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 25 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-07 00:33:19,866 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [8 Valid, 73 Invalid, 26 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 25 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-07 00:33:19,867 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36 states. [2022-04-07 00:33:19,872 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36 to 36. [2022-04-07 00:33:19,872 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 36 states, 24 states have (on average 1.0833333333333333) internal successors, (26), 24 states have internal predecessors, (26), 7 states have call successors, (7), 6 states have call predecessors, (7), 4 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-07 00:33:19,873 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 38 transitions. [2022-04-07 00:33:19,873 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 38 transitions. Word has length 26 [2022-04-07 00:33:19,873 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-07 00:33:19,873 INFO L478 AbstractCegarLoop]: Abstraction has 36 states and 38 transitions. [2022-04-07 00:33:19,873 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 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-07 00:33:19,873 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 38 transitions. [2022-04-07 00:33:19,874 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2022-04-07 00:33:19,874 INFO L491 BasicCegarLoop]: Found error trace [2022-04-07 00:33:19,874 INFO L499 BasicCegarLoop]: trace histogram [4, 3, 3, 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-07 00:33:19,892 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2022-04-07 00:33:20,087 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-07 00:33:20,088 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-07 00:33:20,088 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-07 00:33:20,088 INFO L85 PathProgramCache]: Analyzing trace with hash -1559147673, now seen corresponding path program 1 times [2022-04-07 00:33:20,088 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-07 00:33:20,088 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [920938847] [2022-04-07 00:33:20,091 INFO L97 AcceleratorQvasr]: Qvasr could not accelerate loop because java.lang.UnsupportedOperationException: Cannot deal with arrays. [2022-04-07 00:33:20,091 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-07 00:33:20,092 INFO L85 PathProgramCache]: Analyzing trace with hash -1559147673, now seen corresponding path program 2 times [2022-04-07 00:33:20,092 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-07 00:33:20,092 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1035913990] [2022-04-07 00:33:20,092 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-07 00:33:20,092 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-07 00:33:20,099 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-07 00:33:20,099 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [785182503] [2022-04-07 00:33:20,099 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-07 00:33:20,099 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-07 00:33:20,100 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-07 00:33:20,116 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-07 00:33:20,117 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-07 00:33:20,151 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-07 00:33:20,151 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-07 00:33:20,152 INFO L263 TraceCheckSpWp]: Trace formula consists of 120 conjuncts, 12 conjunts are in the unsatisfiable core [2022-04-07 00:33:20,153 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-07 00:33:20,299 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 6 proven. 4 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-07 00:33:20,299 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-07 00:33:20,497 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-07 00:33:20,497 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1035913990] [2022-04-07 00:33:20,498 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-07 00:33:20,498 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [785182503] [2022-04-07 00:33:20,498 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [785182503] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-07 00:33:20,498 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-07 00:33:20,498 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2022-04-07 00:33:20,498 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-07 00:33:20,498 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [920938847] [2022-04-07 00:33:20,498 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [920938847] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-07 00:33:20,498 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-07 00:33:20,499 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2022-04-07 00:33:20,499 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [400005306] [2022-04-07 00:33:20,499 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-07 00:33:20,499 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-04-07 00:33:20,499 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-07 00:33:20,499 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-04-07 00:33:20,500 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=66, Unknown=0, NotChecked=0, Total=90 [2022-04-07 00:33:20,500 INFO L87 Difference]: Start difference. First operand 36 states and 38 transitions. Second operand has 7 states, 6 states have (on average 3.1666666666666665) internal successors, (19), 6 states have internal predecessors, (19), 4 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) [2022-04-07 00:33:20,565 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 00:33:20,565 INFO L93 Difference]: Finished difference Result 44 states and 48 transitions. [2022-04-07 00:33:20,565 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-04-07 00:33:20,566 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 3.1666666666666665) internal successors, (19), 6 states have internal predecessors, (19), 4 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) Word has length 37 [2022-04-07 00:33:20,566 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-07 00:33:20,566 INFO L225 Difference]: With dead ends: 44 [2022-04-07 00:33:20,566 INFO L226 Difference]: Without dead ends: 38 [2022-04-07 00:33:20,567 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 57 GetRequests, 46 SyntacticMatches, 1 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=34, Invalid=98, Unknown=0, NotChecked=0, Total=132 [2022-04-07 00:33:20,567 INFO L913 BasicCegarLoop]: 31 mSDtfsCounter, 2 mSDsluCounter, 110 mSDsCounter, 0 mSdLazyCounter, 57 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 141 SdHoareTripleChecker+Invalid, 58 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 57 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-07 00:33:20,567 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 141 Invalid, 58 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 57 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-07 00:33:20,568 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 38 states. [2022-04-07 00:33:20,574 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 38 to 38. [2022-04-07 00:33:20,574 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 38 states, 25 states have (on average 1.08) internal successors, (27), 25 states have internal predecessors, (27), 8 states have call successors, (8), 6 states have call predecessors, (8), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-07 00:33:20,575 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 38 states to 38 states and 41 transitions. [2022-04-07 00:33:20,575 INFO L78 Accepts]: Start accepts. Automaton has 38 states and 41 transitions. Word has length 37 [2022-04-07 00:33:20,575 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-07 00:33:20,575 INFO L478 AbstractCegarLoop]: Abstraction has 38 states and 41 transitions. [2022-04-07 00:33:20,575 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 3.1666666666666665) internal successors, (19), 6 states have internal predecessors, (19), 4 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) [2022-04-07 00:33:20,576 INFO L276 IsEmpty]: Start isEmpty. Operand 38 states and 41 transitions. [2022-04-07 00:33:20,576 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2022-04-07 00:33:20,576 INFO L491 BasicCegarLoop]: Found error trace [2022-04-07 00:33:20,576 INFO L499 BasicCegarLoop]: trace histogram [4, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-07 00:33:20,593 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2022-04-07 00:33:20,793 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-07 00:33:20,794 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-07 00:33:20,794 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-07 00:33:20,794 INFO L85 PathProgramCache]: Analyzing trace with hash -951509150, now seen corresponding path program 1 times [2022-04-07 00:33:20,794 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-07 00:33:20,794 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1169216303] [2022-04-07 00:33:20,798 INFO L97 AcceleratorQvasr]: Qvasr could not accelerate loop because java.lang.UnsupportedOperationException: Cannot deal with arrays. [2022-04-07 00:33:20,798 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-07 00:33:20,798 INFO L85 PathProgramCache]: Analyzing trace with hash -951509150, now seen corresponding path program 2 times [2022-04-07 00:33:20,798 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-07 00:33:20,799 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1107119330] [2022-04-07 00:33:20,799 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-07 00:33:20,799 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-07 00:33:20,806 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-07 00:33:20,806 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [318616558] [2022-04-07 00:33:20,806 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-07 00:33:20,806 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-07 00:33:20,807 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-07 00:33:20,836 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-07 00:33:20,837 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-07 00:33:20,869 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-07 00:33:20,870 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-07 00:33:20,871 INFO L263 TraceCheckSpWp]: Trace formula consists of 131 conjuncts, 9 conjunts are in the unsatisfiable core [2022-04-07 00:33:20,872 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-07 00:33:20,936 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 12 proven. 12 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2022-04-07 00:33:20,936 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-07 00:33:21,013 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 6 proven. 8 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-07 00:33:21,014 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-07 00:33:21,014 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1107119330] [2022-04-07 00:33:21,014 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-07 00:33:21,014 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [318616558] [2022-04-07 00:33:21,014 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [318616558] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-07 00:33:21,014 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-07 00:33:21,014 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 10 [2022-04-07 00:33:21,014 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-07 00:33:21,014 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1169216303] [2022-04-07 00:33:21,014 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1169216303] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-07 00:33:21,014 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-07 00:33:21,015 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-07 00:33:21,015 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [263736895] [2022-04-07 00:33:21,015 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-07 00:33:21,015 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-07 00:33:21,015 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-07 00:33:21,015 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-07 00:33:21,016 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2022-04-07 00:33:21,016 INFO L87 Difference]: Start difference. First operand 38 states and 41 transitions. Second operand has 6 states, 6 states have (on average 4.333333333333333) internal successors, (26), 5 states have internal predecessors, (26), 5 states have call successors, (7), 5 states have call predecessors, (7), 4 states have return successors, (5), 4 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-07 00:33:21,046 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 00:33:21,046 INFO L93 Difference]: Finished difference Result 54 states and 56 transitions. [2022-04-07 00:33:21,046 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-04-07 00:33:21,046 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 4.333333333333333) internal successors, (26), 5 states have internal predecessors, (26), 5 states have call successors, (7), 5 states have call predecessors, (7), 4 states have return successors, (5), 4 states have call predecessors, (5), 5 states have call successors, (5) Word has length 39 [2022-04-07 00:33:21,046 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-07 00:33:21,047 INFO L225 Difference]: With dead ends: 54 [2022-04-07 00:33:21,047 INFO L226 Difference]: Without dead ends: 44 [2022-04-07 00:33:21,047 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 79 GetRequests, 69 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=51, Invalid=81, Unknown=0, NotChecked=0, Total=132 [2022-04-07 00:33:21,048 INFO L913 BasicCegarLoop]: 27 mSDtfsCounter, 6 mSDsluCounter, 66 mSDsCounter, 0 mSdLazyCounter, 16 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 93 SdHoareTripleChecker+Invalid, 21 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 16 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-07 00:33:21,048 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 93 Invalid, 21 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 16 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-07 00:33:21,048 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2022-04-07 00:33:21,053 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 44. [2022-04-07 00:33:21,054 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 44 states, 30 states have (on average 1.0666666666666667) internal successors, (32), 30 states have internal predecessors, (32), 8 states have call successors, (8), 7 states have call predecessors, (8), 5 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-07 00:33:21,054 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 46 transitions. [2022-04-07 00:33:21,054 INFO L78 Accepts]: Start accepts. Automaton has 44 states and 46 transitions. Word has length 39 [2022-04-07 00:33:21,054 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-07 00:33:21,055 INFO L478 AbstractCegarLoop]: Abstraction has 44 states and 46 transitions. [2022-04-07 00:33:21,055 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 4.333333333333333) internal successors, (26), 5 states have internal predecessors, (26), 5 states have call successors, (7), 5 states have call predecessors, (7), 4 states have return successors, (5), 4 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-07 00:33:21,055 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 46 transitions. [2022-04-07 00:33:21,055 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2022-04-07 00:33:21,056 INFO L491 BasicCegarLoop]: Found error trace [2022-04-07 00:33:21,056 INFO L499 BasicCegarLoop]: trace histogram [5, 4, 4, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-07 00:33:21,073 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-07 00:33:21,271 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-07 00:33:21,271 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-07 00:33:21,271 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-07 00:33:21,272 INFO L85 PathProgramCache]: Analyzing trace with hash 1537538120, now seen corresponding path program 3 times [2022-04-07 00:33:21,272 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-07 00:33:21,272 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1152257714] [2022-04-07 00:33:21,274 INFO L97 AcceleratorQvasr]: Qvasr could not accelerate loop because java.lang.UnsupportedOperationException: Cannot deal with arrays. [2022-04-07 00:33:21,274 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-07 00:33:21,274 INFO L85 PathProgramCache]: Analyzing trace with hash 1537538120, now seen corresponding path program 4 times [2022-04-07 00:33:21,274 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-07 00:33:21,275 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1394841263] [2022-04-07 00:33:21,275 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-07 00:33:21,275 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-07 00:33:21,281 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-07 00:33:21,281 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [995399285] [2022-04-07 00:33:21,281 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-04-07 00:33:21,282 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-07 00:33:21,282 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-07 00:33:21,283 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-07 00:33:21,284 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-07 00:33:21,313 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-04-07 00:33:21,313 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-07 00:33:21,314 INFO L263 TraceCheckSpWp]: Trace formula consists of 92 conjuncts, 16 conjunts are in the unsatisfiable core [2022-04-07 00:33:21,315 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-07 00:33:21,458 INFO L134 CoverageAnalysis]: Checked inductivity of 44 backedges. 8 proven. 12 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-04-07 00:33:21,458 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-07 00:33:21,567 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-07 00:33:21,568 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1394841263] [2022-04-07 00:33:21,568 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-07 00:33:21,568 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [995399285] [2022-04-07 00:33:21,568 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [995399285] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-07 00:33:21,568 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-07 00:33:21,568 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8] total 8 [2022-04-07 00:33:21,568 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-07 00:33:21,569 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1152257714] [2022-04-07 00:33:21,569 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1152257714] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-07 00:33:21,569 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-07 00:33:21,569 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2022-04-07 00:33:21,569 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [660086363] [2022-04-07 00:33:21,569 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-07 00:33:21,569 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-04-07 00:33:21,569 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-07 00:33:21,570 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-04-07 00:33:21,570 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2022-04-07 00:33:21,570 INFO L87 Difference]: Start difference. First operand 44 states and 46 transitions. Second operand has 8 states, 7 states have (on average 3.142857142857143) internal successors, (22), 7 states have internal predecessors, (22), 5 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) [2022-04-07 00:33:21,656 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 00:33:21,656 INFO L93 Difference]: Finished difference Result 52 states and 56 transitions. [2022-04-07 00:33:21,656 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-04-07 00:33:21,657 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 3.142857142857143) internal successors, (22), 7 states have internal predecessors, (22), 5 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) Word has length 45 [2022-04-07 00:33:21,657 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-07 00:33:21,657 INFO L225 Difference]: With dead ends: 52 [2022-04-07 00:33:21,657 INFO L226 Difference]: Without dead ends: 46 [2022-04-07 00:33:21,658 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 65 GetRequests, 53 SyntacticMatches, 1 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=37, Invalid=119, Unknown=0, NotChecked=0, Total=156 [2022-04-07 00:33:21,658 INFO L913 BasicCegarLoop]: 35 mSDtfsCounter, 2 mSDsluCounter, 144 mSDsCounter, 0 mSdLazyCounter, 85 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 179 SdHoareTripleChecker+Invalid, 86 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 85 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-07 00:33:21,658 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 179 Invalid, 86 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 85 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-07 00:33:21,659 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 46 states. [2022-04-07 00:33:21,664 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 46 to 46. [2022-04-07 00:33:21,664 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 46 states, 31 states have (on average 1.064516129032258) internal successors, (33), 31 states have internal predecessors, (33), 9 states have call successors, (9), 7 states have call predecessors, (9), 5 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-07 00:33:21,665 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 49 transitions. [2022-04-07 00:33:21,665 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 49 transitions. Word has length 45 [2022-04-07 00:33:21,665 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-07 00:33:21,665 INFO L478 AbstractCegarLoop]: Abstraction has 46 states and 49 transitions. [2022-04-07 00:33:21,666 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 3.142857142857143) internal successors, (22), 7 states have internal predecessors, (22), 5 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) [2022-04-07 00:33:21,666 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 49 transitions. [2022-04-07 00:33:21,666 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2022-04-07 00:33:21,666 INFO L491 BasicCegarLoop]: Found error trace [2022-04-07 00:33:21,666 INFO L499 BasicCegarLoop]: trace histogram [5, 4, 4, 4, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-07 00:33:21,698 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-07 00:33:21,884 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-07 00:33:21,884 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-07 00:33:21,884 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-07 00:33:21,884 INFO L85 PathProgramCache]: Analyzing trace with hash -1448798205, now seen corresponding path program 3 times [2022-04-07 00:33:21,885 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-07 00:33:21,885 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [981229927] [2022-04-07 00:33:21,887 INFO L97 AcceleratorQvasr]: Qvasr could not accelerate loop because java.lang.UnsupportedOperationException: Cannot deal with arrays. [2022-04-07 00:33:21,887 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-07 00:33:21,887 INFO L85 PathProgramCache]: Analyzing trace with hash -1448798205, now seen corresponding path program 4 times [2022-04-07 00:33:21,887 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-07 00:33:21,888 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1573634104] [2022-04-07 00:33:21,888 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-07 00:33:21,888 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-07 00:33:21,894 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-07 00:33:21,894 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1223359437] [2022-04-07 00:33:21,894 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-04-07 00:33:21,894 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-07 00:33:21,895 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-07 00:33:21,900 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-07 00:33:21,901 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-07 00:33:21,936 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-04-07 00:33:21,936 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-07 00:33:21,937 INFO L263 TraceCheckSpWp]: Trace formula consists of 152 conjuncts, 11 conjunts are in the unsatisfiable core [2022-04-07 00:33:21,938 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-07 00:33:22,013 INFO L134 CoverageAnalysis]: Checked inductivity of 50 backedges. 18 proven. 30 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2022-04-07 00:33:22,014 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-07 00:33:22,111 INFO L134 CoverageAnalysis]: Checked inductivity of 50 backedges. 8 proven. 18 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-04-07 00:33:22,112 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-07 00:33:22,112 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1573634104] [2022-04-07 00:33:22,112 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-07 00:33:22,112 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1223359437] [2022-04-07 00:33:22,112 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1223359437] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-07 00:33:22,112 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-07 00:33:22,112 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 12 [2022-04-07 00:33:22,112 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-07 00:33:22,112 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [981229927] [2022-04-07 00:33:22,112 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [981229927] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-07 00:33:22,113 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-07 00:33:22,113 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2022-04-07 00:33:22,113 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [478415869] [2022-04-07 00:33:22,113 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-07 00:33:22,113 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-04-07 00:33:22,113 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-07 00:33:22,113 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-04-07 00:33:22,113 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=50, Invalid=82, Unknown=0, NotChecked=0, Total=132 [2022-04-07 00:33:22,114 INFO L87 Difference]: Start difference. First operand 46 states and 49 transitions. Second operand has 7 states, 7 states have (on average 4.571428571428571) internal successors, (32), 6 states have internal predecessors, (32), 6 states have call successors, (8), 6 states have call predecessors, (8), 5 states have return successors, (6), 5 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-07 00:33:22,153 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 00:33:22,154 INFO L93 Difference]: Finished difference Result 62 states and 64 transitions. [2022-04-07 00:33:22,154 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-04-07 00:33:22,154 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 4.571428571428571) internal successors, (32), 6 states have internal predecessors, (32), 6 states have call successors, (8), 6 states have call predecessors, (8), 5 states have return successors, (6), 5 states have call predecessors, (6), 6 states have call successors, (6) Word has length 47 [2022-04-07 00:33:22,154 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-07 00:33:22,155 INFO L225 Difference]: With dead ends: 62 [2022-04-07 00:33:22,155 INFO L226 Difference]: Without dead ends: 52 [2022-04-07 00:33:22,155 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 96 GetRequests, 83 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=83, Invalid=127, Unknown=0, NotChecked=0, Total=210 [2022-04-07 00:33:22,155 INFO L913 BasicCegarLoop]: 28 mSDtfsCounter, 6 mSDsluCounter, 62 mSDsCounter, 0 mSdLazyCounter, 20 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 90 SdHoareTripleChecker+Invalid, 25 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 20 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-07 00:33:22,156 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 90 Invalid, 25 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 20 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-07 00:33:22,156 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 52 states. [2022-04-07 00:33:22,161 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 52 to 52. [2022-04-07 00:33:22,162 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 52 states, 36 states have (on average 1.0555555555555556) internal successors, (38), 36 states have internal predecessors, (38), 9 states have call successors, (9), 8 states have call predecessors, (9), 6 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-07 00:33:22,162 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52 states to 52 states and 54 transitions. [2022-04-07 00:33:22,162 INFO L78 Accepts]: Start accepts. Automaton has 52 states and 54 transitions. Word has length 47 [2022-04-07 00:33:22,163 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-07 00:33:22,163 INFO L478 AbstractCegarLoop]: Abstraction has 52 states and 54 transitions. [2022-04-07 00:33:22,163 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 4.571428571428571) internal successors, (32), 6 states have internal predecessors, (32), 6 states have call successors, (8), 6 states have call predecessors, (8), 5 states have return successors, (6), 5 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-07 00:33:22,163 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 54 transitions. [2022-04-07 00:33:22,163 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 54 [2022-04-07 00:33:22,163 INFO L491 BasicCegarLoop]: Found error trace [2022-04-07 00:33:22,164 INFO L499 BasicCegarLoop]: trace histogram [6, 5, 5, 4, 4, 4, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-07 00:33:22,202 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-07 00:33:22,373 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,SelfDestructingSolverStorable8 [2022-04-07 00:33:22,373 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-07 00:33:22,374 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-07 00:33:22,374 INFO L85 PathProgramCache]: Analyzing trace with hash 468857897, now seen corresponding path program 5 times [2022-04-07 00:33:22,374 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-07 00:33:22,374 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [60464485] [2022-04-07 00:33:22,376 INFO L97 AcceleratorQvasr]: Qvasr could not accelerate loop because java.lang.UnsupportedOperationException: Cannot deal with arrays. [2022-04-07 00:33:22,377 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-07 00:33:22,377 INFO L85 PathProgramCache]: Analyzing trace with hash 468857897, now seen corresponding path program 6 times [2022-04-07 00:33:22,377 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-07 00:33:22,377 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1219066852] [2022-04-07 00:33:22,377 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-07 00:33:22,377 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-07 00:33:22,383 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-07 00:33:22,383 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1567770347] [2022-04-07 00:33:22,383 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-04-07 00:33:22,383 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-07 00:33:22,383 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-07 00:33:22,388 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-07 00:33:22,389 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-07 00:33:28,994 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2022-04-07 00:33:28,994 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-07 00:33:28,997 INFO L263 TraceCheckSpWp]: Trace formula consists of 162 conjuncts, 20 conjunts are in the unsatisfiable core [2022-04-07 00:33:28,998 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-07 00:33:29,167 INFO L134 CoverageAnalysis]: Checked inductivity of 74 backedges. 10 proven. 24 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2022-04-07 00:33:29,167 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-07 00:33:29,270 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-07 00:33:29,271 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1219066852] [2022-04-07 00:33:29,271 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-07 00:33:29,271 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1567770347] [2022-04-07 00:33:29,271 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1567770347] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-07 00:33:29,271 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-07 00:33:29,271 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2022-04-07 00:33:29,271 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-07 00:33:29,271 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [60464485] [2022-04-07 00:33:29,271 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [60464485] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-07 00:33:29,271 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-07 00:33:29,272 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2022-04-07 00:33:29,272 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1233778340] [2022-04-07 00:33:29,272 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-07 00:33:29,272 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-04-07 00:33:29,272 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-07 00:33:29,272 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-04-07 00:33:29,272 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2022-04-07 00:33:29,273 INFO L87 Difference]: Start difference. First operand 52 states and 54 transitions. Second operand has 9 states, 8 states have (on average 3.125) internal successors, (25), 8 states have internal predecessors, (25), 6 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 6 states have call predecessors, (7), 6 states have call successors, (7) [2022-04-07 00:33:29,366 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 00:33:29,366 INFO L93 Difference]: Finished difference Result 60 states and 64 transitions. [2022-04-07 00:33:29,367 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-04-07 00:33:29,367 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 3.125) internal successors, (25), 8 states have internal predecessors, (25), 6 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 6 states have call predecessors, (7), 6 states have call successors, (7) Word has length 53 [2022-04-07 00:33:29,367 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-07 00:33:29,368 INFO L225 Difference]: With dead ends: 60 [2022-04-07 00:33:29,368 INFO L226 Difference]: Without dead ends: 54 [2022-04-07 00:33:29,368 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 73 GetRequests, 60 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=40, Invalid=142, Unknown=0, NotChecked=0, Total=182 [2022-04-07 00:33:29,368 INFO L913 BasicCegarLoop]: 39 mSDtfsCounter, 2 mSDsluCounter, 182 mSDsCounter, 0 mSdLazyCounter, 119 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 221 SdHoareTripleChecker+Invalid, 120 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 119 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-07 00:33:29,369 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 221 Invalid, 120 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 119 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-07 00:33:29,369 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2022-04-07 00:33:29,375 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 54. [2022-04-07 00:33:29,375 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 37 states have (on average 1.054054054054054) internal successors, (39), 37 states have internal predecessors, (39), 10 states have call successors, (10), 8 states have call predecessors, (10), 6 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-07 00:33:29,375 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 57 transitions. [2022-04-07 00:33:29,376 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 57 transitions. Word has length 53 [2022-04-07 00:33:29,376 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-07 00:33:29,376 INFO L478 AbstractCegarLoop]: Abstraction has 54 states and 57 transitions. [2022-04-07 00:33:29,376 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 3.125) internal successors, (25), 8 states have internal predecessors, (25), 6 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 6 states have call predecessors, (7), 6 states have call successors, (7) [2022-04-07 00:33:29,376 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 57 transitions. [2022-04-07 00:33:29,377 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2022-04-07 00:33:29,377 INFO L491 BasicCegarLoop]: Found error trace [2022-04-07 00:33:29,377 INFO L499 BasicCegarLoop]: trace histogram [6, 5, 5, 5, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-07 00:33:29,383 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2022-04-07 00:33:29,583 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,SelfDestructingSolverStorable9 [2022-04-07 00:33:29,583 INFO L403 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-07 00:33:29,584 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-07 00:33:29,584 INFO L85 PathProgramCache]: Analyzing trace with hash -1953308764, now seen corresponding path program 5 times [2022-04-07 00:33:29,584 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-07 00:33:29,584 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [172334834] [2022-04-07 00:33:29,587 INFO L97 AcceleratorQvasr]: Qvasr could not accelerate loop because java.lang.UnsupportedOperationException: Cannot deal with arrays. [2022-04-07 00:33:29,587 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-07 00:33:29,587 INFO L85 PathProgramCache]: Analyzing trace with hash -1953308764, now seen corresponding path program 6 times [2022-04-07 00:33:29,587 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-07 00:33:29,587 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1257217052] [2022-04-07 00:33:29,587 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-07 00:33:29,587 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-07 00:33:29,593 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-07 00:33:29,593 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [712711037] [2022-04-07 00:33:29,593 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-04-07 00:33:29,594 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-07 00:33:29,594 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-07 00:33:29,594 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-07 00:33:29,601 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-07 00:33:29,998 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 5 check-sat command(s) [2022-04-07 00:33:29,998 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-07 00:33:29,999 INFO L263 TraceCheckSpWp]: Trace formula consists of 173 conjuncts, 13 conjunts are in the unsatisfiable core [2022-04-07 00:33:30,001 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-07 00:33:30,118 INFO L134 CoverageAnalysis]: Checked inductivity of 82 backedges. 24 proven. 56 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2022-04-07 00:33:30,118 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-07 00:33:30,234 INFO L134 CoverageAnalysis]: Checked inductivity of 82 backedges. 10 proven. 32 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2022-04-07 00:33:30,234 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-07 00:33:30,234 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1257217052] [2022-04-07 00:33:30,234 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-07 00:33:30,234 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [712711037] [2022-04-07 00:33:30,234 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [712711037] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-07 00:33:30,234 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-07 00:33:30,235 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 14 [2022-04-07 00:33:30,235 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-07 00:33:30,235 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [172334834] [2022-04-07 00:33:30,235 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [172334834] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-07 00:33:30,235 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-07 00:33:30,235 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2022-04-07 00:33:30,235 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [346996269] [2022-04-07 00:33:30,235 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-07 00:33:30,236 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-04-07 00:33:30,236 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-07 00:33:30,236 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-04-07 00:33:30,236 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=111, Unknown=0, NotChecked=0, Total=182 [2022-04-07 00:33:30,237 INFO L87 Difference]: Start difference. First operand 54 states and 57 transitions. Second operand has 8 states, 8 states have (on average 4.75) internal successors, (38), 7 states have internal predecessors, (38), 7 states have call successors, (9), 7 states have call predecessors, (9), 6 states have return successors, (7), 6 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-07 00:33:30,294 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 00:33:30,294 INFO L93 Difference]: Finished difference Result 70 states and 72 transitions. [2022-04-07 00:33:30,294 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-04-07 00:33:30,294 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 4.75) internal successors, (38), 7 states have internal predecessors, (38), 7 states have call successors, (9), 7 states have call predecessors, (9), 6 states have return successors, (7), 6 states have call predecessors, (7), 7 states have call successors, (7) Word has length 55 [2022-04-07 00:33:30,295 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-07 00:33:30,296 INFO L225 Difference]: With dead ends: 70 [2022-04-07 00:33:30,297 INFO L226 Difference]: Without dead ends: 60 [2022-04-07 00:33:30,298 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 113 GetRequests, 97 SyntacticMatches, 0 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 19 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=123, Invalid=183, Unknown=0, NotChecked=0, Total=306 [2022-04-07 00:33:30,298 INFO L913 BasicCegarLoop]: 29 mSDtfsCounter, 12 mSDsluCounter, 76 mSDsCounter, 0 mSdLazyCounter, 25 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 105 SdHoareTripleChecker+Invalid, 35 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 25 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-07 00:33:30,298 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [12 Valid, 105 Invalid, 35 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 25 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-07 00:33:30,298 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 60 states. [2022-04-07 00:33:30,306 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 60 to 60. [2022-04-07 00:33:30,306 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 60 states, 42 states have (on average 1.0476190476190477) internal successors, (44), 42 states have internal predecessors, (44), 10 states have call successors, (10), 9 states have call predecessors, (10), 7 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-07 00:33:30,308 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 60 states to 60 states and 62 transitions. [2022-04-07 00:33:30,308 INFO L78 Accepts]: Start accepts. Automaton has 60 states and 62 transitions. Word has length 55 [2022-04-07 00:33:30,308 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-07 00:33:30,308 INFO L478 AbstractCegarLoop]: Abstraction has 60 states and 62 transitions. [2022-04-07 00:33:30,309 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 4.75) internal successors, (38), 7 states have internal predecessors, (38), 7 states have call successors, (9), 7 states have call predecessors, (9), 6 states have return successors, (7), 6 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-07 00:33:30,309 INFO L276 IsEmpty]: Start isEmpty. Operand 60 states and 62 transitions. [2022-04-07 00:33:30,309 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 62 [2022-04-07 00:33:30,309 INFO L491 BasicCegarLoop]: Found error trace [2022-04-07 00:33:30,310 INFO L499 BasicCegarLoop]: trace histogram [7, 6, 6, 5, 5, 5, 5, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-07 00:33:30,329 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2022-04-07 00:33:30,516 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2022-04-07 00:33:30,517 INFO L403 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-07 00:33:30,517 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-07 00:33:30,517 INFO L85 PathProgramCache]: Analyzing trace with hash 1425669898, now seen corresponding path program 7 times [2022-04-07 00:33:30,517 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-07 00:33:30,517 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [635613100] [2022-04-07 00:33:30,520 INFO L97 AcceleratorQvasr]: Qvasr could not accelerate loop because java.lang.UnsupportedOperationException: Cannot deal with arrays. [2022-04-07 00:33:30,520 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-07 00:33:30,520 INFO L85 PathProgramCache]: Analyzing trace with hash 1425669898, now seen corresponding path program 8 times [2022-04-07 00:33:30,520 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-07 00:33:30,520 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1481150289] [2022-04-07 00:33:30,520 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-07 00:33:30,520 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-07 00:33:30,541 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-07 00:33:30,541 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1239948174] [2022-04-07 00:33:30,541 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-07 00:33:30,541 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-07 00:33:30,542 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-07 00:33:30,552 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-07 00:33:30,554 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2022-04-07 00:33:31,068 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-07 00:33:31,068 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-07 00:33:31,070 INFO L263 TraceCheckSpWp]: Trace formula consists of 183 conjuncts, 25 conjunts are in the unsatisfiable core [2022-04-07 00:33:31,071 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-07 00:33:31,327 INFO L134 CoverageAnalysis]: Checked inductivity of 112 backedges. 12 proven. 40 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2022-04-07 00:33:31,327 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-07 00:33:31,634 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-07 00:33:31,634 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1481150289] [2022-04-07 00:33:31,634 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-07 00:33:31,635 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1239948174] [2022-04-07 00:33:31,635 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1239948174] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-07 00:33:31,635 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-07 00:33:31,635 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2022-04-07 00:33:31,635 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-07 00:33:31,635 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [635613100] [2022-04-07 00:33:31,635 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [635613100] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-07 00:33:31,635 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-07 00:33:31,635 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [] total 10 [2022-04-07 00:33:31,635 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1377638576] [2022-04-07 00:33:31,635 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-07 00:33:31,636 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-04-07 00:33:31,636 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-07 00:33:31,636 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-04-07 00:33:31,636 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=52, Invalid=188, Unknown=0, NotChecked=0, Total=240 [2022-04-07 00:33:31,636 INFO L87 Difference]: Start difference. First operand 60 states and 62 transitions. Second operand has 10 states, 9 states have (on average 3.111111111111111) internal successors, (28), 9 states have internal predecessors, (28), 7 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 7 states have call predecessors, (8), 7 states have call successors, (8) [2022-04-07 00:33:31,768 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 00:33:31,769 INFO L93 Difference]: Finished difference Result 68 states and 72 transitions. [2022-04-07 00:33:31,769 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-04-07 00:33:31,769 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 3.111111111111111) internal successors, (28), 9 states have internal predecessors, (28), 7 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 7 states have call predecessors, (8), 7 states have call successors, (8) Word has length 61 [2022-04-07 00:33:31,769 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-07 00:33:31,770 INFO L225 Difference]: With dead ends: 68 [2022-04-07 00:33:31,770 INFO L226 Difference]: Without dead ends: 62 [2022-04-07 00:33:31,770 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 105 GetRequests, 88 SyntacticMatches, 1 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=62, Invalid=244, Unknown=0, NotChecked=0, Total=306 [2022-04-07 00:33:31,770 INFO L913 BasicCegarLoop]: 44 mSDtfsCounter, 2 mSDsluCounter, 222 mSDsCounter, 0 mSdLazyCounter, 168 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 266 SdHoareTripleChecker+Invalid, 169 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 168 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-07 00:33:31,771 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 266 Invalid, 169 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 168 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-07 00:33:31,771 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 62 states. [2022-04-07 00:33:31,777 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 62 to 62. [2022-04-07 00:33:31,777 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 62 states, 43 states have (on average 1.0465116279069768) internal successors, (45), 43 states have internal predecessors, (45), 11 states have call successors, (11), 9 states have call predecessors, (11), 7 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-07 00:33:31,777 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 65 transitions. [2022-04-07 00:33:31,777 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 65 transitions. Word has length 61 [2022-04-07 00:33:31,778 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-07 00:33:31,778 INFO L478 AbstractCegarLoop]: Abstraction has 62 states and 65 transitions. [2022-04-07 00:33:31,778 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 3.111111111111111) internal successors, (28), 9 states have internal predecessors, (28), 7 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 7 states have call predecessors, (8), 7 states have call successors, (8) [2022-04-07 00:33:31,778 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 65 transitions. [2022-04-07 00:33:31,778 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 64 [2022-04-07 00:33:31,778 INFO L491 BasicCegarLoop]: Found error trace [2022-04-07 00:33:31,779 INFO L499 BasicCegarLoop]: trace histogram [7, 6, 6, 6, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-07 00:33:31,793 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2022-04-07 00:33:31,986 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2022-04-07 00:33:31,987 INFO L403 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-07 00:33:31,987 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-07 00:33:31,987 INFO L85 PathProgramCache]: Analyzing trace with hash -1579977147, now seen corresponding path program 7 times [2022-04-07 00:33:31,987 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-07 00:33:31,987 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1478390951] [2022-04-07 00:33:31,991 INFO L97 AcceleratorQvasr]: Qvasr could not accelerate loop because java.lang.UnsupportedOperationException: Cannot deal with arrays. [2022-04-07 00:33:31,991 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-07 00:33:31,991 INFO L85 PathProgramCache]: Analyzing trace with hash -1579977147, now seen corresponding path program 8 times [2022-04-07 00:33:31,991 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-07 00:33:31,991 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [758374954] [2022-04-07 00:33:31,991 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-07 00:33:31,991 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-07 00:33:31,997 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-07 00:33:31,998 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [567122780] [2022-04-07 00:33:31,998 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-07 00:33:31,998 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-07 00:33:31,998 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-07 00:33:31,999 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-07 00:33:32,000 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2022-04-07 00:33:32,039 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-07 00:33:32,039 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-07 00:33:32,040 INFO L263 TraceCheckSpWp]: Trace formula consists of 194 conjuncts, 15 conjunts are in the unsatisfiable core [2022-04-07 00:33:32,042 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-07 00:33:32,147 INFO L134 CoverageAnalysis]: Checked inductivity of 122 backedges. 30 proven. 90 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2022-04-07 00:33:32,148 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-07 00:33:32,268 INFO L134 CoverageAnalysis]: Checked inductivity of 122 backedges. 12 proven. 50 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2022-04-07 00:33:32,269 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-07 00:33:32,269 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [758374954] [2022-04-07 00:33:32,269 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-07 00:33:32,269 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [567122780] [2022-04-07 00:33:32,269 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [567122780] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-07 00:33:32,269 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-07 00:33:32,269 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 14 [2022-04-07 00:33:32,269 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-07 00:33:32,269 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1478390951] [2022-04-07 00:33:32,269 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1478390951] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-07 00:33:32,270 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-07 00:33:32,270 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2022-04-07 00:33:32,270 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1157107074] [2022-04-07 00:33:32,270 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-07 00:33:32,270 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-04-07 00:33:32,270 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-07 00:33:32,270 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-04-07 00:33:32,270 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=111, Unknown=0, NotChecked=0, Total=182 [2022-04-07 00:33:32,271 INFO L87 Difference]: Start difference. First operand 62 states and 65 transitions. Second operand has 9 states, 9 states have (on average 4.888888888888889) internal successors, (44), 8 states have internal predecessors, (44), 8 states have call successors, (10), 8 states have call predecessors, (10), 7 states have return successors, (8), 7 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-07 00:33:32,335 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 00:33:32,335 INFO L93 Difference]: Finished difference Result 78 states and 80 transitions. [2022-04-07 00:33:32,335 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2022-04-07 00:33:32,336 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 4.888888888888889) internal successors, (44), 8 states have internal predecessors, (44), 8 states have call successors, (10), 8 states have call predecessors, (10), 7 states have return successors, (8), 7 states have call predecessors, (8), 8 states have call successors, (8) Word has length 63 [2022-04-07 00:33:32,336 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-07 00:33:32,336 INFO L225 Difference]: With dead ends: 78 [2022-04-07 00:33:32,336 INFO L226 Difference]: Without dead ends: 68 [2022-04-07 00:33:32,337 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 130 GetRequests, 112 SyntacticMatches, 1 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 28 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=136, Invalid=206, Unknown=0, NotChecked=0, Total=342 [2022-04-07 00:33:32,337 INFO L913 BasicCegarLoop]: 30 mSDtfsCounter, 6 mSDsluCounter, 81 mSDsCounter, 0 mSdLazyCounter, 31 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 111 SdHoareTripleChecker+Invalid, 36 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 31 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-07 00:33:32,337 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 111 Invalid, 36 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 31 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-07 00:33:32,337 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 68 states. [2022-04-07 00:33:32,344 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 68 to 68. [2022-04-07 00:33:32,344 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 68 states, 48 states have (on average 1.0416666666666667) internal successors, (50), 48 states have internal predecessors, (50), 11 states have call successors, (11), 10 states have call predecessors, (11), 8 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-07 00:33:32,344 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 68 states to 68 states and 70 transitions. [2022-04-07 00:33:32,344 INFO L78 Accepts]: Start accepts. Automaton has 68 states and 70 transitions. Word has length 63 [2022-04-07 00:33:32,345 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-07 00:33:32,345 INFO L478 AbstractCegarLoop]: Abstraction has 68 states and 70 transitions. [2022-04-07 00:33:32,345 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 4.888888888888889) internal successors, (44), 8 states have internal predecessors, (44), 8 states have call successors, (10), 8 states have call predecessors, (10), 7 states have return successors, (8), 7 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-07 00:33:32,345 INFO L276 IsEmpty]: Start isEmpty. Operand 68 states and 70 transitions. [2022-04-07 00:33:32,345 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 70 [2022-04-07 00:33:32,345 INFO L491 BasicCegarLoop]: Found error trace [2022-04-07 00:33:32,345 INFO L499 BasicCegarLoop]: trace histogram [8, 7, 7, 6, 6, 6, 6, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-07 00:33:32,387 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2022-04-07 00:33:32,563 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2022-04-07 00:33:32,563 INFO L403 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-07 00:33:32,563 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-07 00:33:32,564 INFO L85 PathProgramCache]: Analyzing trace with hash -423798549, now seen corresponding path program 9 times [2022-04-07 00:33:32,564 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-07 00:33:32,564 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1901863247] [2022-04-07 00:33:32,566 INFO L97 AcceleratorQvasr]: Qvasr could not accelerate loop because java.lang.UnsupportedOperationException: Cannot deal with arrays. [2022-04-07 00:33:32,566 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-07 00:33:32,566 INFO L85 PathProgramCache]: Analyzing trace with hash -423798549, now seen corresponding path program 10 times [2022-04-07 00:33:32,566 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-07 00:33:32,566 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2038344627] [2022-04-07 00:33:32,566 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-07 00:33:32,566 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-07 00:33:32,574 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-07 00:33:32,574 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [972610651] [2022-04-07 00:33:32,574 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-04-07 00:33:32,574 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-07 00:33:32,574 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-07 00:33:32,575 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-07 00:33:32,602 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2022-04-07 00:33:32,619 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-04-07 00:33:32,619 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-07 00:33:32,620 INFO L263 TraceCheckSpWp]: Trace formula consists of 143 conjuncts, 28 conjunts are in the unsatisfiable core [2022-04-07 00:33:32,621 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-07 00:33:32,849 INFO L134 CoverageAnalysis]: Checked inductivity of 158 backedges. 14 proven. 60 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2022-04-07 00:33:32,849 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-07 00:33:33,001 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-07 00:33:33,001 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2038344627] [2022-04-07 00:33:33,001 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-07 00:33:33,002 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [972610651] [2022-04-07 00:33:33,002 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [972610651] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-07 00:33:33,002 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-07 00:33:33,002 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2022-04-07 00:33:33,002 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-07 00:33:33,002 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1901863247] [2022-04-07 00:33:33,002 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1901863247] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-07 00:33:33,002 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-07 00:33:33,002 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [11] imperfect sequences [] total 11 [2022-04-07 00:33:33,002 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1696365495] [2022-04-07 00:33:33,002 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-07 00:33:33,003 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2022-04-07 00:33:33,003 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-07 00:33:33,003 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2022-04-07 00:33:33,003 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=36, Invalid=146, Unknown=0, NotChecked=0, Total=182 [2022-04-07 00:33:33,003 INFO L87 Difference]: Start difference. First operand 68 states and 70 transitions. Second operand has 11 states, 10 states have (on average 3.1) internal successors, (31), 10 states have internal predecessors, (31), 8 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 8 states have call predecessors, (9), 8 states have call successors, (9) [2022-04-07 00:33:33,137 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 00:33:33,137 INFO L93 Difference]: Finished difference Result 76 states and 80 transitions. [2022-04-07 00:33:33,138 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-04-07 00:33:33,138 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 3.1) internal successors, (31), 10 states have internal predecessors, (31), 8 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 8 states have call predecessors, (9), 8 states have call successors, (9) Word has length 69 [2022-04-07 00:33:33,138 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-07 00:33:33,138 INFO L225 Difference]: With dead ends: 76 [2022-04-07 00:33:33,139 INFO L226 Difference]: Without dead ends: 70 [2022-04-07 00:33:33,139 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 89 GetRequests, 74 SyntacticMatches, 1 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=46, Invalid=194, Unknown=0, NotChecked=0, Total=240 [2022-04-07 00:33:33,139 INFO L913 BasicCegarLoop]: 47 mSDtfsCounter, 2 mSDsluCounter, 270 mSDsCounter, 0 mSdLazyCounter, 205 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 317 SdHoareTripleChecker+Invalid, 206 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 205 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-07 00:33:33,139 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 317 Invalid, 206 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 205 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-07 00:33:33,140 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 70 states. [2022-04-07 00:33:33,146 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 70 to 70. [2022-04-07 00:33:33,146 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 70 states, 49 states have (on average 1.0408163265306123) internal successors, (51), 49 states have internal predecessors, (51), 12 states have call successors, (12), 10 states have call predecessors, (12), 8 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-07 00:33:33,147 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 70 states to 70 states and 73 transitions. [2022-04-07 00:33:33,147 INFO L78 Accepts]: Start accepts. Automaton has 70 states and 73 transitions. Word has length 69 [2022-04-07 00:33:33,147 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-07 00:33:33,147 INFO L478 AbstractCegarLoop]: Abstraction has 70 states and 73 transitions. [2022-04-07 00:33:33,147 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 3.1) internal successors, (31), 10 states have internal predecessors, (31), 8 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 8 states have call predecessors, (9), 8 states have call successors, (9) [2022-04-07 00:33:33,147 INFO L276 IsEmpty]: Start isEmpty. Operand 70 states and 73 transitions. [2022-04-07 00:33:33,148 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 72 [2022-04-07 00:33:33,148 INFO L491 BasicCegarLoop]: Found error trace [2022-04-07 00:33:33,148 INFO L499 BasicCegarLoop]: trace histogram [8, 7, 7, 7, 6, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-07 00:33:33,167 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2022-04-07 00:33:33,365 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2022-04-07 00:33:33,365 INFO L403 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-07 00:33:33,366 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-07 00:33:33,366 INFO L85 PathProgramCache]: Analyzing trace with hash -802694170, now seen corresponding path program 9 times [2022-04-07 00:33:33,366 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-07 00:33:33,366 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [847516989] [2022-04-07 00:33:33,370 INFO L97 AcceleratorQvasr]: Qvasr could not accelerate loop because java.lang.UnsupportedOperationException: Cannot deal with arrays. [2022-04-07 00:33:33,370 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-07 00:33:33,370 INFO L85 PathProgramCache]: Analyzing trace with hash -802694170, now seen corresponding path program 10 times [2022-04-07 00:33:33,370 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-07 00:33:33,370 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2145341332] [2022-04-07 00:33:33,370 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-07 00:33:33,370 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-07 00:33:33,376 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-07 00:33:33,377 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1444999882] [2022-04-07 00:33:33,377 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-04-07 00:33:33,377 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-07 00:33:33,377 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-07 00:33:33,387 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-07 00:33:33,392 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2022-04-07 00:33:33,440 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-04-07 00:33:33,440 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-07 00:33:33,441 INFO L263 TraceCheckSpWp]: Trace formula consists of 215 conjuncts, 17 conjunts are in the unsatisfiable core [2022-04-07 00:33:33,442 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-07 00:33:33,568 INFO L134 CoverageAnalysis]: Checked inductivity of 170 backedges. 36 proven. 132 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2022-04-07 00:33:33,569 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-07 00:33:33,730 INFO L134 CoverageAnalysis]: Checked inductivity of 170 backedges. 14 proven. 72 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2022-04-07 00:33:33,730 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-07 00:33:33,730 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2145341332] [2022-04-07 00:33:33,730 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-07 00:33:33,730 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1444999882] [2022-04-07 00:33:33,730 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1444999882] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-07 00:33:33,730 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-07 00:33:33,730 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 14 [2022-04-07 00:33:33,731 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-07 00:33:33,731 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [847516989] [2022-04-07 00:33:33,731 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [847516989] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-07 00:33:33,731 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-07 00:33:33,731 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [] total 10 [2022-04-07 00:33:33,731 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1314538005] [2022-04-07 00:33:33,731 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-07 00:33:33,731 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-04-07 00:33:33,731 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-07 00:33:33,732 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-04-07 00:33:33,732 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=111, Unknown=0, NotChecked=0, Total=182 [2022-04-07 00:33:33,732 INFO L87 Difference]: Start difference. First operand 70 states and 73 transitions. Second operand has 10 states, 10 states have (on average 5.0) internal successors, (50), 9 states have internal predecessors, (50), 9 states have call successors, (11), 9 states have call predecessors, (11), 8 states have return successors, (9), 8 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-07 00:33:33,806 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 00:33:33,806 INFO L93 Difference]: Finished difference Result 86 states and 88 transitions. [2022-04-07 00:33:33,807 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2022-04-07 00:33:33,807 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 5.0) internal successors, (50), 9 states have internal predecessors, (50), 9 states have call successors, (11), 9 states have call predecessors, (11), 8 states have return successors, (9), 8 states have call predecessors, (9), 9 states have call successors, (9) Word has length 71 [2022-04-07 00:33:33,807 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-07 00:33:33,808 INFO L225 Difference]: With dead ends: 86 [2022-04-07 00:33:33,808 INFO L226 Difference]: Without dead ends: 76 [2022-04-07 00:33:33,808 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 147 GetRequests, 128 SyntacticMatches, 1 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 33 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=149, Invalid=231, Unknown=0, NotChecked=0, Total=380 [2022-04-07 00:33:33,809 INFO L913 BasicCegarLoop]: 31 mSDtfsCounter, 6 mSDsluCounter, 104 mSDsCounter, 0 mSdLazyCounter, 44 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 135 SdHoareTripleChecker+Invalid, 49 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 44 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-07 00:33:33,809 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 135 Invalid, 49 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 44 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-07 00:33:33,809 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 76 states. [2022-04-07 00:33:33,815 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 76 to 76. [2022-04-07 00:33:33,815 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 76 states, 54 states have (on average 1.037037037037037) internal successors, (56), 54 states have internal predecessors, (56), 12 states have call successors, (12), 11 states have call predecessors, (12), 9 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-07 00:33:33,816 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 76 states to 76 states and 78 transitions. [2022-04-07 00:33:33,816 INFO L78 Accepts]: Start accepts. Automaton has 76 states and 78 transitions. Word has length 71 [2022-04-07 00:33:33,816 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-07 00:33:33,816 INFO L478 AbstractCegarLoop]: Abstraction has 76 states and 78 transitions. [2022-04-07 00:33:33,816 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 5.0) internal successors, (50), 9 states have internal predecessors, (50), 9 states have call successors, (11), 9 states have call predecessors, (11), 8 states have return successors, (9), 8 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-07 00:33:33,816 INFO L276 IsEmpty]: Start isEmpty. Operand 76 states and 78 transitions. [2022-04-07 00:33:33,817 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 78 [2022-04-07 00:33:33,817 INFO L491 BasicCegarLoop]: Found error trace [2022-04-07 00:33:33,817 INFO L499 BasicCegarLoop]: trace histogram [9, 8, 8, 7, 7, 7, 7, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-07 00:33:33,836 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2022-04-07 00:33:34,033 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable14,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-07 00:33:34,034 INFO L403 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-07 00:33:34,034 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-07 00:33:34,034 INFO L85 PathProgramCache]: Analyzing trace with hash 540885452, now seen corresponding path program 11 times [2022-04-07 00:33:34,034 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-07 00:33:34,034 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [721491315] [2022-04-07 00:33:34,039 INFO L97 AcceleratorQvasr]: Qvasr could not accelerate loop because java.lang.UnsupportedOperationException: Cannot deal with arrays. [2022-04-07 00:33:34,039 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-07 00:33:34,039 INFO L85 PathProgramCache]: Analyzing trace with hash 540885452, now seen corresponding path program 12 times [2022-04-07 00:33:34,039 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-07 00:33:34,039 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1943846753] [2022-04-07 00:33:34,039 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-07 00:33:34,039 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-07 00:33:34,045 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-07 00:33:34,045 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [34712162] [2022-04-07 00:33:34,045 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-04-07 00:33:34,045 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-07 00:33:34,045 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-07 00:33:34,049 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-07 00:33:34,058 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2022-04-07 00:33:39,389 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2022-04-07 00:33:39,389 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-07 00:33:39,405 INFO L263 TraceCheckSpWp]: Trace formula consists of 225 conjuncts, 33 conjunts are in the unsatisfiable core [2022-04-07 00:33:39,406 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-07 00:33:39,701 INFO L134 CoverageAnalysis]: Checked inductivity of 212 backedges. 16 proven. 84 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2022-04-07 00:33:39,701 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-07 00:33:40,228 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-07 00:33:40,228 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1943846753] [2022-04-07 00:33:40,228 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-07 00:33:40,229 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [34712162] [2022-04-07 00:33:40,229 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [34712162] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-07 00:33:40,229 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-07 00:33:40,229 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2022-04-07 00:33:40,229 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-07 00:33:40,229 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [721491315] [2022-04-07 00:33:40,229 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [721491315] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-07 00:33:40,229 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-07 00:33:40,229 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [12] imperfect sequences [] total 12 [2022-04-07 00:33:40,229 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [830177979] [2022-04-07 00:33:40,229 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-07 00:33:40,231 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-04-07 00:33:40,231 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-07 00:33:40,231 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-04-07 00:33:40,231 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=72, Invalid=270, Unknown=0, NotChecked=0, Total=342 [2022-04-07 00:33:40,231 INFO L87 Difference]: Start difference. First operand 76 states and 78 transitions. Second operand has 12 states, 11 states have (on average 3.090909090909091) internal successors, (34), 11 states have internal predecessors, (34), 9 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (10), 9 states have call predecessors, (10), 9 states have call successors, (10) [2022-04-07 00:33:40,400 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 00:33:40,400 INFO L93 Difference]: Finished difference Result 84 states and 88 transitions. [2022-04-07 00:33:40,413 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-04-07 00:33:40,414 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 3.090909090909091) internal successors, (34), 11 states have internal predecessors, (34), 9 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (10), 9 states have call predecessors, (10), 9 states have call successors, (10) Word has length 77 [2022-04-07 00:33:40,414 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-07 00:33:40,414 INFO L225 Difference]: With dead ends: 84 [2022-04-07 00:33:40,414 INFO L226 Difference]: Without dead ends: 78 [2022-04-07 00:33:40,415 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 129 GetRequests, 109 SyntacticMatches, 1 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=82, Invalid=338, Unknown=0, NotChecked=0, Total=420 [2022-04-07 00:33:40,416 INFO L913 BasicCegarLoop]: 51 mSDtfsCounter, 2 mSDsluCounter, 316 mSDsCounter, 0 mSdLazyCounter, 261 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 367 SdHoareTripleChecker+Invalid, 262 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 261 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-07 00:33:40,416 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 367 Invalid, 262 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 261 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-07 00:33:40,417 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 78 states. [2022-04-07 00:33:40,427 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 78 to 78. [2022-04-07 00:33:40,428 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 78 states, 55 states have (on average 1.0363636363636364) internal successors, (57), 55 states have internal predecessors, (57), 13 states have call successors, (13), 11 states have call predecessors, (13), 9 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-07 00:33:40,428 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 78 states to 78 states and 81 transitions. [2022-04-07 00:33:40,429 INFO L78 Accepts]: Start accepts. Automaton has 78 states and 81 transitions. Word has length 77 [2022-04-07 00:33:40,429 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-07 00:33:40,429 INFO L478 AbstractCegarLoop]: Abstraction has 78 states and 81 transitions. [2022-04-07 00:33:40,429 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 3.090909090909091) internal successors, (34), 11 states have internal predecessors, (34), 9 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (10), 9 states have call predecessors, (10), 9 states have call successors, (10) [2022-04-07 00:33:40,429 INFO L276 IsEmpty]: Start isEmpty. Operand 78 states and 81 transitions. [2022-04-07 00:33:40,429 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 80 [2022-04-07 00:33:40,430 INFO L491 BasicCegarLoop]: Found error trace [2022-04-07 00:33:40,430 INFO L499 BasicCegarLoop]: trace histogram [9, 8, 8, 8, 7, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-07 00:33:40,440 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Ended with exit code 0 [2022-04-07 00:33:40,635 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2022-04-07 00:33:40,637 INFO L403 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-07 00:33:40,637 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-07 00:33:40,637 INFO L85 PathProgramCache]: Analyzing trace with hash -1454305145, now seen corresponding path program 11 times [2022-04-07 00:33:40,637 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-07 00:33:40,637 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [199377848] [2022-04-07 00:33:40,639 INFO L97 AcceleratorQvasr]: Qvasr could not accelerate loop because java.lang.UnsupportedOperationException: Cannot deal with arrays. [2022-04-07 00:33:40,639 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-07 00:33:40,639 INFO L85 PathProgramCache]: Analyzing trace with hash -1454305145, now seen corresponding path program 12 times [2022-04-07 00:33:40,639 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-07 00:33:40,639 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1373451516] [2022-04-07 00:33:40,639 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-07 00:33:40,640 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-07 00:33:40,645 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-07 00:33:40,645 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [909527388] [2022-04-07 00:33:40,645 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-04-07 00:33:40,645 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-07 00:33:40,645 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-07 00:33:40,646 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-07 00:33:40,647 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2022-04-07 00:33:40,804 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 8 check-sat command(s) [2022-04-07 00:33:40,805 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-07 00:33:40,806 INFO L263 TraceCheckSpWp]: Trace formula consists of 236 conjuncts, 19 conjunts are in the unsatisfiable core [2022-04-07 00:33:40,807 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-07 00:33:40,955 INFO L134 CoverageAnalysis]: Checked inductivity of 226 backedges. 42 proven. 182 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2022-04-07 00:33:40,956 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-07 00:33:41,088 INFO L134 CoverageAnalysis]: Checked inductivity of 226 backedges. 16 proven. 98 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2022-04-07 00:33:41,088 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-07 00:33:41,088 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1373451516] [2022-04-07 00:33:41,088 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-07 00:33:41,088 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [909527388] [2022-04-07 00:33:41,088 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [909527388] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-07 00:33:41,088 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-07 00:33:41,088 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 14 [2022-04-07 00:33:41,089 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-07 00:33:41,090 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [199377848] [2022-04-07 00:33:41,090 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [199377848] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-07 00:33:41,090 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-07 00:33:41,090 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [11] imperfect sequences [] total 11 [2022-04-07 00:33:41,090 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [99507968] [2022-04-07 00:33:41,090 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-07 00:33:41,090 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2022-04-07 00:33:41,090 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-07 00:33:41,090 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2022-04-07 00:33:41,091 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=111, Unknown=0, NotChecked=0, Total=182 [2022-04-07 00:33:41,091 INFO L87 Difference]: Start difference. First operand 78 states and 81 transitions. Second operand has 11 states, 11 states have (on average 5.090909090909091) internal successors, (56), 10 states have internal predecessors, (56), 10 states have call successors, (12), 10 states have call predecessors, (12), 9 states have return successors, (10), 9 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-07 00:33:41,215 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 00:33:41,216 INFO L93 Difference]: Finished difference Result 94 states and 96 transitions. [2022-04-07 00:33:41,216 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2022-04-07 00:33:41,216 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 5.090909090909091) internal successors, (56), 10 states have internal predecessors, (56), 10 states have call successors, (12), 10 states have call predecessors, (12), 9 states have return successors, (10), 9 states have call predecessors, (10), 10 states have call successors, (10) Word has length 79 [2022-04-07 00:33:41,216 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-07 00:33:41,216 INFO L225 Difference]: With dead ends: 94 [2022-04-07 00:33:41,216 INFO L226 Difference]: Without dead ends: 84 [2022-04-07 00:33:41,217 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 164 GetRequests, 144 SyntacticMatches, 1 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 39 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=162, Invalid=258, Unknown=0, NotChecked=0, Total=420 [2022-04-07 00:33:41,217 INFO L913 BasicCegarLoop]: 32 mSDtfsCounter, 24 mSDsluCounter, 73 mSDsCounter, 0 mSdLazyCounter, 39 mSolverCounterSat, 20 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 105 SdHoareTripleChecker+Invalid, 59 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 20 IncrementalHoareTripleChecker+Valid, 39 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-07 00:33:41,217 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [24 Valid, 105 Invalid, 59 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [20 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-07 00:33:41,218 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 84 states. [2022-04-07 00:33:41,240 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 84 to 84. [2022-04-07 00:33:41,240 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 84 states, 60 states have (on average 1.0333333333333334) internal successors, (62), 60 states have internal predecessors, (62), 13 states have call successors, (13), 12 states have call predecessors, (13), 10 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-07 00:33:41,240 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 84 states to 84 states and 86 transitions. [2022-04-07 00:33:41,240 INFO L78 Accepts]: Start accepts. Automaton has 84 states and 86 transitions. Word has length 79 [2022-04-07 00:33:41,242 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-07 00:33:41,242 INFO L478 AbstractCegarLoop]: Abstraction has 84 states and 86 transitions. [2022-04-07 00:33:41,242 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 5.090909090909091) internal successors, (56), 10 states have internal predecessors, (56), 10 states have call successors, (12), 10 states have call predecessors, (12), 9 states have return successors, (10), 9 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-07 00:33:41,243 INFO L276 IsEmpty]: Start isEmpty. Operand 84 states and 86 transitions. [2022-04-07 00:33:41,244 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 86 [2022-04-07 00:33:41,244 INFO L491 BasicCegarLoop]: Found error trace [2022-04-07 00:33:41,244 INFO L499 BasicCegarLoop]: trace histogram [10, 9, 9, 8, 8, 8, 8, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-07 00:33:41,261 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2022-04-07 00:33:41,449 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2022-04-07 00:33:41,449 INFO L403 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-07 00:33:41,450 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-07 00:33:41,450 INFO L85 PathProgramCache]: Analyzing trace with hash -1082476115, now seen corresponding path program 13 times [2022-04-07 00:33:41,450 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-07 00:33:41,450 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1955229684] [2022-04-07 00:33:41,453 INFO L97 AcceleratorQvasr]: Qvasr could not accelerate loop because java.lang.UnsupportedOperationException: Cannot deal with arrays. [2022-04-07 00:33:41,453 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-07 00:33:41,453 INFO L85 PathProgramCache]: Analyzing trace with hash -1082476115, now seen corresponding path program 14 times [2022-04-07 00:33:41,453 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-07 00:33:41,453 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1466709436] [2022-04-07 00:33:41,453 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-07 00:33:41,453 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-07 00:33:41,470 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-07 00:33:41,470 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2032706046] [2022-04-07 00:33:41,470 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-07 00:33:41,470 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-07 00:33:41,470 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-07 00:33:41,471 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-07 00:33:41,472 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2022-04-07 00:33:42,586 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-07 00:33:42,587 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-07 00:33:42,589 INFO L263 TraceCheckSpWp]: Trace formula consists of 246 conjuncts, 36 conjunts are in the unsatisfiable core [2022-04-07 00:33:42,590 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-07 00:33:42,844 INFO L134 CoverageAnalysis]: Checked inductivity of 274 backedges. 18 proven. 112 refuted. 0 times theorem prover too weak. 144 trivial. 0 not checked. [2022-04-07 00:33:42,844 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-07 00:33:42,949 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-07 00:33:42,949 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1466709436] [2022-04-07 00:33:42,949 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-07 00:33:42,949 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2032706046] [2022-04-07 00:33:42,949 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2032706046] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-07 00:33:42,949 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-07 00:33:42,949 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2022-04-07 00:33:42,949 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-07 00:33:42,950 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1955229684] [2022-04-07 00:33:42,950 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1955229684] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-07 00:33:42,950 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-07 00:33:42,950 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [13] imperfect sequences [] total 13 [2022-04-07 00:33:42,950 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [120092048] [2022-04-07 00:33:42,950 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-07 00:33:42,950 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2022-04-07 00:33:42,950 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-07 00:33:42,950 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2022-04-07 00:33:42,950 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=42, Invalid=198, Unknown=0, NotChecked=0, Total=240 [2022-04-07 00:33:42,951 INFO L87 Difference]: Start difference. First operand 84 states and 86 transitions. Second operand has 13 states, 12 states have (on average 3.0833333333333335) internal successors, (37), 12 states have internal predecessors, (37), 10 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (11), 10 states have call predecessors, (11), 10 states have call successors, (11) [2022-04-07 00:33:43,135 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 00:33:43,135 INFO L93 Difference]: Finished difference Result 92 states and 96 transitions. [2022-04-07 00:33:43,135 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-04-07 00:33:43,135 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 12 states have (on average 3.0833333333333335) internal successors, (37), 12 states have internal predecessors, (37), 10 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (11), 10 states have call predecessors, (11), 10 states have call successors, (11) Word has length 85 [2022-04-07 00:33:43,136 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-07 00:33:43,136 INFO L225 Difference]: With dead ends: 92 [2022-04-07 00:33:43,136 INFO L226 Difference]: Without dead ends: 86 [2022-04-07 00:33:43,136 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 105 GetRequests, 88 SyntacticMatches, 1 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=52, Invalid=254, Unknown=0, NotChecked=0, Total=306 [2022-04-07 00:33:43,137 INFO L913 BasicCegarLoop]: 56 mSDtfsCounter, 2 mSDsluCounter, 375 mSDsCounter, 0 mSdLazyCounter, 324 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 431 SdHoareTripleChecker+Invalid, 325 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 324 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-04-07 00:33:43,137 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 431 Invalid, 325 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 324 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-04-07 00:33:43,137 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 86 states. [2022-04-07 00:33:43,143 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 86 to 86. [2022-04-07 00:33:43,144 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 86 states, 61 states have (on average 1.0327868852459017) internal successors, (63), 61 states have internal predecessors, (63), 14 states have call successors, (14), 12 states have call predecessors, (14), 10 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-07 00:33:43,144 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 86 states to 86 states and 89 transitions. [2022-04-07 00:33:43,144 INFO L78 Accepts]: Start accepts. Automaton has 86 states and 89 transitions. Word has length 85 [2022-04-07 00:33:43,144 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-07 00:33:43,145 INFO L478 AbstractCegarLoop]: Abstraction has 86 states and 89 transitions. [2022-04-07 00:33:43,145 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 12 states have (on average 3.0833333333333335) internal successors, (37), 12 states have internal predecessors, (37), 10 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (11), 10 states have call predecessors, (11), 10 states have call successors, (11) [2022-04-07 00:33:43,145 INFO L276 IsEmpty]: Start isEmpty. Operand 86 states and 89 transitions. [2022-04-07 00:33:43,145 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2022-04-07 00:33:43,145 INFO L491 BasicCegarLoop]: Found error trace [2022-04-07 00:33:43,145 INFO L499 BasicCegarLoop]: trace histogram [10, 9, 9, 9, 8, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-07 00:33:43,152 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Forceful destruction successful, exit code 0 [2022-04-07 00:33:43,346 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2022-04-07 00:33:43,346 INFO L403 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-07 00:33:43,346 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-07 00:33:43,347 INFO L85 PathProgramCache]: Analyzing trace with hash 1863324712, now seen corresponding path program 13 times [2022-04-07 00:33:43,347 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-07 00:33:43,347 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1873362998] [2022-04-07 00:33:43,349 INFO L97 AcceleratorQvasr]: Qvasr could not accelerate loop because java.lang.UnsupportedOperationException: Cannot deal with arrays. [2022-04-07 00:33:43,349 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-07 00:33:43,349 INFO L85 PathProgramCache]: Analyzing trace with hash 1863324712, now seen corresponding path program 14 times [2022-04-07 00:33:43,349 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-07 00:33:43,349 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [544099214] [2022-04-07 00:33:43,349 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-07 00:33:43,349 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-07 00:33:43,354 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-07 00:33:43,354 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1254800172] [2022-04-07 00:33:43,354 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-07 00:33:43,354 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-07 00:33:43,355 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-07 00:33:43,367 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-07 00:33:43,400 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2022-04-07 00:33:43,445 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-07 00:33:43,446 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-07 00:33:43,448 INFO L263 TraceCheckSpWp]: Trace formula consists of 257 conjuncts, 21 conjunts are in the unsatisfiable core [2022-04-07 00:33:43,449 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-07 00:33:43,621 INFO L134 CoverageAnalysis]: Checked inductivity of 290 backedges. 48 proven. 240 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2022-04-07 00:33:43,622 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-07 00:33:43,766 INFO L134 CoverageAnalysis]: Checked inductivity of 290 backedges. 18 proven. 128 refuted. 0 times theorem prover too weak. 144 trivial. 0 not checked. [2022-04-07 00:33:43,766 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-07 00:33:43,766 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [544099214] [2022-04-07 00:33:43,766 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-07 00:33:43,766 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1254800172] [2022-04-07 00:33:43,766 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1254800172] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-07 00:33:43,766 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-07 00:33:43,767 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 14 [2022-04-07 00:33:43,767 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-07 00:33:43,767 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1873362998] [2022-04-07 00:33:43,767 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1873362998] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-07 00:33:43,767 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-07 00:33:43,767 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [12] imperfect sequences [] total 12 [2022-04-07 00:33:43,767 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [663361455] [2022-04-07 00:33:43,767 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-07 00:33:43,767 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-04-07 00:33:43,767 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-07 00:33:43,768 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-04-07 00:33:43,768 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=111, Unknown=0, NotChecked=0, Total=182 [2022-04-07 00:33:43,768 INFO L87 Difference]: Start difference. First operand 86 states and 89 transitions. Second operand has 12 states, 12 states have (on average 5.166666666666667) internal successors, (62), 11 states have internal predecessors, (62), 11 states have call successors, (13), 11 states have call predecessors, (13), 10 states have return successors, (11), 10 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-07 00:33:43,870 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 00:33:43,870 INFO L93 Difference]: Finished difference Result 102 states and 104 transitions. [2022-04-07 00:33:43,870 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2022-04-07 00:33:43,870 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 5.166666666666667) internal successors, (62), 11 states have internal predecessors, (62), 11 states have call successors, (13), 11 states have call predecessors, (13), 10 states have return successors, (11), 10 states have call predecessors, (11), 11 states have call successors, (11) Word has length 87 [2022-04-07 00:33:43,871 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-07 00:33:43,871 INFO L225 Difference]: With dead ends: 102 [2022-04-07 00:33:43,871 INFO L226 Difference]: Without dead ends: 92 [2022-04-07 00:33:43,871 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 181 GetRequests, 160 SyntacticMatches, 1 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 46 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=175, Invalid=287, Unknown=0, NotChecked=0, Total=462 [2022-04-07 00:33:43,872 INFO L913 BasicCegarLoop]: 33 mSDtfsCounter, 6 mSDsluCounter, 105 mSDsCounter, 0 mSdLazyCounter, 50 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 138 SdHoareTripleChecker+Invalid, 55 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 50 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-07 00:33:43,872 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 138 Invalid, 55 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 50 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-07 00:33:43,872 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 92 states. [2022-04-07 00:33:43,886 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 92 to 92. [2022-04-07 00:33:43,886 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 92 states, 66 states have (on average 1.0303030303030303) internal successors, (68), 66 states have internal predecessors, (68), 14 states have call successors, (14), 13 states have call predecessors, (14), 11 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-07 00:33:43,886 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 92 states to 92 states and 94 transitions. [2022-04-07 00:33:43,887 INFO L78 Accepts]: Start accepts. Automaton has 92 states and 94 transitions. Word has length 87 [2022-04-07 00:33:43,887 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-07 00:33:43,887 INFO L478 AbstractCegarLoop]: Abstraction has 92 states and 94 transitions. [2022-04-07 00:33:43,887 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 5.166666666666667) internal successors, (62), 11 states have internal predecessors, (62), 11 states have call successors, (13), 11 states have call predecessors, (13), 10 states have return successors, (11), 10 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-07 00:33:43,887 INFO L276 IsEmpty]: Start isEmpty. Operand 92 states and 94 transitions. [2022-04-07 00:33:43,887 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 94 [2022-04-07 00:33:43,887 INFO L491 BasicCegarLoop]: Found error trace [2022-04-07 00:33:43,888 INFO L499 BasicCegarLoop]: trace histogram [11, 10, 10, 9, 9, 9, 9, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-07 00:33:43,905 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Forceful destruction successful, exit code 0 [2022-04-07 00:33:44,103 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,19 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-07 00:33:44,103 INFO L403 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-07 00:33:44,104 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-07 00:33:44,104 INFO L85 PathProgramCache]: Analyzing trace with hash -243875698, now seen corresponding path program 15 times [2022-04-07 00:33:44,104 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-07 00:33:44,104 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [372512680] [2022-04-07 00:33:44,107 INFO L97 AcceleratorQvasr]: Qvasr could not accelerate loop because java.lang.UnsupportedOperationException: Cannot deal with arrays. [2022-04-07 00:33:44,107 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-07 00:33:44,107 INFO L85 PathProgramCache]: Analyzing trace with hash -243875698, now seen corresponding path program 16 times [2022-04-07 00:33:44,107 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-07 00:33:44,108 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [82066743] [2022-04-07 00:33:44,108 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-07 00:33:44,108 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-07 00:33:44,114 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-07 00:33:44,114 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1246103836] [2022-04-07 00:33:44,114 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-04-07 00:33:44,114 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-07 00:33:44,115 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-07 00:33:44,115 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-07 00:33:44,117 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Waiting until timeout for monitored process [2022-04-07 00:33:44,165 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-04-07 00:33:44,165 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-07 00:33:44,167 INFO L263 TraceCheckSpWp]: Trace formula consists of 194 conjuncts, 40 conjunts are in the unsatisfiable core [2022-04-07 00:33:44,168 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-07 00:33:44,439 INFO L134 CoverageAnalysis]: Checked inductivity of 344 backedges. 20 proven. 144 refuted. 0 times theorem prover too weak. 180 trivial. 0 not checked. [2022-04-07 00:33:44,439 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-07 00:33:44,554 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-07 00:33:44,554 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [82066743] [2022-04-07 00:33:44,554 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-07 00:33:44,554 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1246103836] [2022-04-07 00:33:44,554 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1246103836] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-07 00:33:44,554 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-07 00:33:44,554 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14] total 14 [2022-04-07 00:33:44,555 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-07 00:33:44,555 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [372512680] [2022-04-07 00:33:44,555 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [372512680] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-07 00:33:44,555 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-07 00:33:44,555 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [14] imperfect sequences [] total 14 [2022-04-07 00:33:44,555 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1383541107] [2022-04-07 00:33:44,555 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-07 00:33:44,555 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2022-04-07 00:33:44,555 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-07 00:33:44,556 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-04-07 00:33:44,556 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=45, Invalid=227, Unknown=0, NotChecked=0, Total=272 [2022-04-07 00:33:44,556 INFO L87 Difference]: Start difference. First operand 92 states and 94 transitions. Second operand has 14 states, 13 states have (on average 3.076923076923077) internal successors, (40), 13 states have internal predecessors, (40), 11 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (12), 11 states have call predecessors, (12), 11 states have call successors, (12) [2022-04-07 00:33:44,780 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 00:33:44,780 INFO L93 Difference]: Finished difference Result 100 states and 104 transitions. [2022-04-07 00:33:44,780 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2022-04-07 00:33:44,780 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 13 states have (on average 3.076923076923077) internal successors, (40), 13 states have internal predecessors, (40), 11 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (12), 11 states have call predecessors, (12), 11 states have call successors, (12) Word has length 93 [2022-04-07 00:33:44,780 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-07 00:33:44,781 INFO L225 Difference]: With dead ends: 100 [2022-04-07 00:33:44,781 INFO L226 Difference]: Without dead ends: 94 [2022-04-07 00:33:44,781 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 113 GetRequests, 95 SyntacticMatches, 1 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=55, Invalid=287, Unknown=0, NotChecked=0, Total=342 [2022-04-07 00:33:44,782 INFO L913 BasicCegarLoop]: 60 mSDtfsCounter, 2 mSDsluCounter, 433 mSDsCounter, 0 mSdLazyCounter, 389 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 493 SdHoareTripleChecker+Invalid, 390 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 389 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-04-07 00:33:44,782 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 493 Invalid, 390 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 389 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-04-07 00:33:44,782 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 94 states. [2022-04-07 00:33:44,802 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 94 to 94. [2022-04-07 00:33:44,802 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 94 states, 67 states have (on average 1.0298507462686568) internal successors, (69), 67 states have internal predecessors, (69), 15 states have call successors, (15), 13 states have call predecessors, (15), 11 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-07 00:33:44,803 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 94 states to 94 states and 97 transitions. [2022-04-07 00:33:44,803 INFO L78 Accepts]: Start accepts. Automaton has 94 states and 97 transitions. Word has length 93 [2022-04-07 00:33:44,803 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-07 00:33:44,803 INFO L478 AbstractCegarLoop]: Abstraction has 94 states and 97 transitions. [2022-04-07 00:33:44,803 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 13 states have (on average 3.076923076923077) internal successors, (40), 13 states have internal predecessors, (40), 11 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (12), 11 states have call predecessors, (12), 11 states have call successors, (12) [2022-04-07 00:33:44,803 INFO L276 IsEmpty]: Start isEmpty. Operand 94 states and 97 transitions. [2022-04-07 00:33:44,815 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 96 [2022-04-07 00:33:44,815 INFO L491 BasicCegarLoop]: Found error trace [2022-04-07 00:33:44,815 INFO L499 BasicCegarLoop]: trace histogram [11, 10, 10, 10, 9, 9, 9, 9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-07 00:33:44,849 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Forceful destruction successful, exit code 0 [2022-04-07 00:33:45,033 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,20 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-07 00:33:45,033 INFO L403 AbstractCegarLoop]: === Iteration 21 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-07 00:33:45,033 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-07 00:33:45,033 INFO L85 PathProgramCache]: Analyzing trace with hash 304473801, now seen corresponding path program 15 times [2022-04-07 00:33:45,034 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-07 00:33:45,034 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [830042310] [2022-04-07 00:33:45,037 INFO L97 AcceleratorQvasr]: Qvasr could not accelerate loop because java.lang.UnsupportedOperationException: Cannot deal with arrays. [2022-04-07 00:33:45,038 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-07 00:33:45,038 INFO L85 PathProgramCache]: Analyzing trace with hash 304473801, now seen corresponding path program 16 times [2022-04-07 00:33:45,038 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-07 00:33:45,038 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [510960380] [2022-04-07 00:33:45,038 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-07 00:33:45,038 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-07 00:33:45,057 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-07 00:33:45,057 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1316722180] [2022-04-07 00:33:45,057 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-04-07 00:33:45,057 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-07 00:33:45,057 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-07 00:33:45,058 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-07 00:33:45,060 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Waiting until timeout for monitored process [2022-04-07 00:33:45,111 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-04-07 00:33:45,111 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-07 00:33:45,112 INFO L263 TraceCheckSpWp]: Trace formula consists of 278 conjuncts, 23 conjunts are in the unsatisfiable core [2022-04-07 00:33:45,114 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-07 00:33:45,306 INFO L134 CoverageAnalysis]: Checked inductivity of 362 backedges. 54 proven. 306 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2022-04-07 00:33:45,306 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-07 00:33:45,457 INFO L134 CoverageAnalysis]: Checked inductivity of 362 backedges. 20 proven. 162 refuted. 0 times theorem prover too weak. 180 trivial. 0 not checked. [2022-04-07 00:33:45,457 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-07 00:33:45,457 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [510960380] [2022-04-07 00:33:45,457 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-07 00:33:45,457 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1316722180] [2022-04-07 00:33:45,457 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1316722180] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-07 00:33:45,457 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-07 00:33:45,457 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 13 [2022-04-07 00:33:45,458 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-07 00:33:45,458 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [830042310] [2022-04-07 00:33:45,458 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [830042310] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-07 00:33:45,458 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-07 00:33:45,458 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [13] imperfect sequences [] total 13 [2022-04-07 00:33:45,459 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1403398982] [2022-04-07 00:33:45,459 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-07 00:33:45,459 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2022-04-07 00:33:45,459 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-07 00:33:45,459 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2022-04-07 00:33:45,459 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=68, Invalid=88, Unknown=0, NotChecked=0, Total=156 [2022-04-07 00:33:45,460 INFO L87 Difference]: Start difference. First operand 94 states and 97 transitions. Second operand has 13 states, 13 states have (on average 5.230769230769231) internal successors, (68), 12 states have internal predecessors, (68), 12 states have call successors, (14), 12 states have call predecessors, (14), 11 states have return successors, (12), 11 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-07 00:33:45,564 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 00:33:45,564 INFO L93 Difference]: Finished difference Result 110 states and 112 transitions. [2022-04-07 00:33:45,565 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2022-04-07 00:33:45,565 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 5.230769230769231) internal successors, (68), 12 states have internal predecessors, (68), 12 states have call successors, (14), 12 states have call predecessors, (14), 11 states have return successors, (12), 11 states have call predecessors, (12), 12 states have call successors, (12) Word has length 95 [2022-04-07 00:33:45,565 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-07 00:33:45,565 INFO L225 Difference]: With dead ends: 110 [2022-04-07 00:33:45,565 INFO L226 Difference]: Without dead ends: 100 [2022-04-07 00:33:45,566 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 198 GetRequests, 177 SyntacticMatches, 1 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 54 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=176, Invalid=286, Unknown=0, NotChecked=0, Total=462 [2022-04-07 00:33:45,566 INFO L913 BasicCegarLoop]: 34 mSDtfsCounter, 12 mSDsluCounter, 101 mSDsCounter, 0 mSdLazyCounter, 53 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 135 SdHoareTripleChecker+Invalid, 63 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 53 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-07 00:33:45,566 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [12 Valid, 135 Invalid, 63 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 53 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-07 00:33:45,567 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 100 states. [2022-04-07 00:33:45,574 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 100 to 100. [2022-04-07 00:33:45,574 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 100 states, 72 states have (on average 1.0277777777777777) internal successors, (74), 72 states have internal predecessors, (74), 15 states have call successors, (15), 14 states have call predecessors, (15), 12 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-07 00:33:45,574 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 100 states to 100 states and 102 transitions. [2022-04-07 00:33:45,575 INFO L78 Accepts]: Start accepts. Automaton has 100 states and 102 transitions. Word has length 95 [2022-04-07 00:33:45,575 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-07 00:33:45,575 INFO L478 AbstractCegarLoop]: Abstraction has 100 states and 102 transitions. [2022-04-07 00:33:45,575 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 5.230769230769231) internal successors, (68), 12 states have internal predecessors, (68), 12 states have call successors, (14), 12 states have call predecessors, (14), 11 states have return successors, (12), 11 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-07 00:33:45,575 INFO L276 IsEmpty]: Start isEmpty. Operand 100 states and 102 transitions. [2022-04-07 00:33:45,575 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 102 [2022-04-07 00:33:45,575 INFO L491 BasicCegarLoop]: Found error trace [2022-04-07 00:33:45,576 INFO L499 BasicCegarLoop]: trace histogram [12, 11, 11, 10, 10, 10, 10, 9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-07 00:33:45,593 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Forceful destruction successful, exit code 0 [2022-04-07 00:33:45,789 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 21 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable20 [2022-04-07 00:33:45,789 INFO L403 AbstractCegarLoop]: === Iteration 22 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-07 00:33:45,790 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-07 00:33:45,790 INFO L85 PathProgramCache]: Analyzing trace with hash 1379030639, now seen corresponding path program 17 times [2022-04-07 00:33:45,790 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-07 00:33:45,790 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [415462546] [2022-04-07 00:33:45,792 INFO L97 AcceleratorQvasr]: Qvasr could not accelerate loop because java.lang.UnsupportedOperationException: Cannot deal with arrays. [2022-04-07 00:33:45,792 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-07 00:33:45,792 INFO L85 PathProgramCache]: Analyzing trace with hash 1379030639, now seen corresponding path program 18 times [2022-04-07 00:33:45,792 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-07 00:33:45,792 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1240791882] [2022-04-07 00:33:45,792 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-07 00:33:45,793 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-07 00:33:45,798 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-07 00:33:45,798 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [765500541] [2022-04-07 00:33:45,798 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-04-07 00:33:45,798 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-07 00:33:45,798 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-07 00:33:45,799 INFO L229 MonitoredProcess]: Starting monitored process 22 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-07 00:33:45,800 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Waiting until timeout for monitored process [2022-04-07 00:35:28,179 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 10 check-sat command(s) [2022-04-07 00:35:28,180 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-07 00:35:28,248 INFO L263 TraceCheckSpWp]: Trace formula consists of 288 conjuncts, 45 conjunts are in the unsatisfiable core [2022-04-07 00:35:28,250 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-07 00:35:28,655 INFO L134 CoverageAnalysis]: Checked inductivity of 422 backedges. 22 proven. 180 refuted. 0 times theorem prover too weak. 220 trivial. 0 not checked. [2022-04-07 00:35:28,655 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-07 00:35:29,216 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-07 00:35:29,216 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1240791882] [2022-04-07 00:35:29,216 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-07 00:35:29,216 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [765500541] [2022-04-07 00:35:29,217 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [765500541] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-07 00:35:29,217 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-07 00:35:29,217 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2022-04-07 00:35:29,217 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-07 00:35:29,217 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [415462546] [2022-04-07 00:35:29,217 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [415462546] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-07 00:35:29,217 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-07 00:35:29,217 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [15] imperfect sequences [] total 15 [2022-04-07 00:35:29,217 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [947023457] [2022-04-07 00:35:29,217 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-07 00:35:29,217 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2022-04-07 00:35:29,218 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-07 00:35:29,218 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2022-04-07 00:35:29,218 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=126, Invalid=474, Unknown=0, NotChecked=0, Total=600 [2022-04-07 00:35:29,218 INFO L87 Difference]: Start difference. First operand 100 states and 102 transitions. Second operand has 15 states, 14 states have (on average 3.0714285714285716) internal successors, (43), 14 states have internal predecessors, (43), 12 states have call successors, (15), 2 states have call predecessors, (15), 1 states have return successors, (13), 12 states have call predecessors, (13), 12 states have call successors, (13) [2022-04-07 00:35:29,486 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 00:35:29,486 INFO L93 Difference]: Finished difference Result 108 states and 112 transitions. [2022-04-07 00:35:29,487 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2022-04-07 00:35:29,487 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 14 states have (on average 3.0714285714285716) internal successors, (43), 14 states have internal predecessors, (43), 12 states have call successors, (15), 2 states have call predecessors, (15), 1 states have return successors, (13), 12 states have call predecessors, (13), 12 states have call successors, (13) Word has length 101 [2022-04-07 00:35:29,487 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-07 00:35:29,488 INFO L225 Difference]: With dead ends: 108 [2022-04-07 00:35:29,488 INFO L226 Difference]: Without dead ends: 102 [2022-04-07 00:35:29,488 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 177 GetRequests, 151 SyntacticMatches, 1 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=136, Invalid=566, Unknown=0, NotChecked=0, Total=702 [2022-04-07 00:35:29,489 INFO L913 BasicCegarLoop]: 64 mSDtfsCounter, 2 mSDsluCounter, 488 mSDsCounter, 0 mSdLazyCounter, 467 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 552 SdHoareTripleChecker+Invalid, 468 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 467 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-04-07 00:35:29,489 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 552 Invalid, 468 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 467 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-04-07 00:35:29,489 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 102 states. [2022-04-07 00:35:29,497 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 102 to 102. [2022-04-07 00:35:29,497 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 102 states, 73 states have (on average 1.0273972602739727) internal successors, (75), 73 states have internal predecessors, (75), 16 states have call successors, (16), 14 states have call predecessors, (16), 12 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) [2022-04-07 00:35:29,498 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 102 states to 102 states and 105 transitions. [2022-04-07 00:35:29,498 INFO L78 Accepts]: Start accepts. Automaton has 102 states and 105 transitions. Word has length 101 [2022-04-07 00:35:29,498 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-07 00:35:29,498 INFO L478 AbstractCegarLoop]: Abstraction has 102 states and 105 transitions. [2022-04-07 00:35:29,498 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 14 states have (on average 3.0714285714285716) internal successors, (43), 14 states have internal predecessors, (43), 12 states have call successors, (15), 2 states have call predecessors, (15), 1 states have return successors, (13), 12 states have call predecessors, (13), 12 states have call successors, (13) [2022-04-07 00:35:29,498 INFO L276 IsEmpty]: Start isEmpty. Operand 102 states and 105 transitions. [2022-04-07 00:35:29,499 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 104 [2022-04-07 00:35:29,499 INFO L491 BasicCegarLoop]: Found error trace [2022-04-07 00:35:29,499 INFO L499 BasicCegarLoop]: trace histogram [12, 11, 11, 11, 10, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-07 00:35:29,536 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Ended with exit code 0 [2022-04-07 00:35:29,705 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 22 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable21 [2022-04-07 00:35:29,706 INFO L403 AbstractCegarLoop]: === Iteration 23 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-07 00:35:29,706 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-07 00:35:29,706 INFO L85 PathProgramCache]: Analyzing trace with hash 844335210, now seen corresponding path program 17 times [2022-04-07 00:35:29,706 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-07 00:35:29,706 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1770113143] [2022-04-07 00:35:29,709 INFO L97 AcceleratorQvasr]: Qvasr could not accelerate loop because java.lang.UnsupportedOperationException: Cannot deal with arrays. [2022-04-07 00:35:29,709 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-07 00:35:29,709 INFO L85 PathProgramCache]: Analyzing trace with hash 844335210, now seen corresponding path program 18 times [2022-04-07 00:35:29,709 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-07 00:35:29,709 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2041504423] [2022-04-07 00:35:29,709 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-07 00:35:29,709 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-07 00:35:29,715 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-07 00:35:29,715 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [935636081] [2022-04-07 00:35:29,715 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-04-07 00:35:29,715 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-07 00:35:29,715 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-07 00:35:29,716 INFO L229 MonitoredProcess]: Starting monitored process 23 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-07 00:35:29,717 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (23)] Waiting until timeout for monitored process [2022-04-07 00:35:30,387 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 11 check-sat command(s) [2022-04-07 00:35:30,387 INFO L229 tOrderPrioritization]: Conjunction of SSA is sat [2022-04-07 00:35:30,387 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders.