/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/acceleratedInterpolationJordan_32.epf -i ../../../trunk/examples/svcomp/nla-digbench-scaling/ps4-ll_unwindbound100.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-34549b5 [2022-04-06 18:18:37,148 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-06 18:18:37,153 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-06 18:18:37,186 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-06 18:18:37,186 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-06 18:18:37,188 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-06 18:18:37,190 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-06 18:18:37,192 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-06 18:18:37,193 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-06 18:18:37,196 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-06 18:18:37,196 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-06 18:18:37,197 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-06 18:18:37,198 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-06 18:18:37,199 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-06 18:18:37,200 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-06 18:18:37,202 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-06 18:18:37,202 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-06 18:18:37,203 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-06 18:18:37,204 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-06 18:18:37,208 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-06 18:18:37,209 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-06 18:18:37,210 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-06 18:18:37,211 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-06 18:18:37,211 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-06 18:18:37,212 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-06 18:18:37,216 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-06 18:18:37,217 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-06 18:18:37,217 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-06 18:18:37,217 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-06 18:18:37,217 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-06 18:18:37,218 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-06 18:18:37,219 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-06 18:18:37,220 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-06 18:18:37,220 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-06 18:18:37,220 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-06 18:18:37,221 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-06 18:18:37,221 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-06 18:18:37,221 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-06 18:18:37,222 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-06 18:18:37,222 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-06 18:18:37,222 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-06 18:18:37,224 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-06 18:18:37,224 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationJordan_32.epf [2022-04-06 18:18:37,231 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-06 18:18:37,232 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-06 18:18:37,233 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-06 18:18:37,233 INFO L138 SettingsManager]: * sizeof long=4 [2022-04-06 18:18:37,233 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-06 18:18:37,233 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-04-06 18:18:37,233 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-06 18:18:37,233 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-06 18:18:37,233 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-06 18:18:37,234 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-06 18:18:37,234 INFO L138 SettingsManager]: * sizeof long double=12 [2022-04-06 18:18:37,234 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-06 18:18:37,234 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-06 18:18:37,234 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-06 18:18:37,234 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-06 18:18:37,234 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-06 18:18:37,234 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-04-06 18:18:37,235 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-06 18:18:37,235 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-06 18:18:37,235 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-06 18:18:37,235 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_NestedInterpolation [2022-04-06 18:18:37,235 INFO L138 SettingsManager]: * Trace refinement strategy=ACCELERATED_INTERPOLATION [2022-04-06 18:18:37,235 INFO L138 SettingsManager]: * Trace refinement strategy used in Accelerated Interpolation=CAMEL [2022-04-06 18:18:37,235 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-04-06 18:18:37,235 INFO L138 SettingsManager]: * Loop acceleration method that is used by accelerated interpolation=JORDAN [2022-04-06 18:18:37,235 INFO L138 SettingsManager]: * Use separate solver for trace checks=false WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.core: Log level for class -> de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN; [2022-04-06 18:18:37,436 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-06 18:18:37,455 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-06 18:18:37,457 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-06 18:18:37,458 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-06 18:18:37,458 INFO L275 PluginConnector]: CDTParser initialized [2022-04-06 18:18:37,459 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/ps4-ll_unwindbound100.c [2022-04-06 18:18:37,510 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/e5fe83720/1169dbd247a5444b8844a05812f008fd/FLAGe10f00712 [2022-04-06 18:18:37,895 INFO L306 CDTParser]: Found 1 translation units. [2022-04-06 18:18:37,896 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/ps4-ll_unwindbound100.c [2022-04-06 18:18:37,902 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/e5fe83720/1169dbd247a5444b8844a05812f008fd/FLAGe10f00712 [2022-04-06 18:18:37,916 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/e5fe83720/1169dbd247a5444b8844a05812f008fd [2022-04-06 18:18:37,917 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-06 18:18:37,918 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-04-06 18:18:37,920 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-06 18:18:37,921 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-06 18:18:37,923 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-06 18:18:37,924 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.04 06:18:37" (1/1) ... [2022-04-06 18:18:37,925 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@1acbda8c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 06:18:37, skipping insertion in model container [2022-04-06 18:18:37,925 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.04 06:18:37" (1/1) ... [2022-04-06 18:18:37,941 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-06 18:18:37,951 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-06 18:18:38,104 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/ps4-ll_unwindbound100.c[458,471] [2022-04-06 18:18:38,125 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-06 18:18:38,131 INFO L203 MainTranslator]: Completed pre-run [2022-04-06 18:18:38,140 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/ps4-ll_unwindbound100.c[458,471] [2022-04-06 18:18:38,153 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-06 18:18:38,162 INFO L208 MainTranslator]: Completed translation [2022-04-06 18:18:38,163 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 06:18:38 WrapperNode [2022-04-06 18:18:38,163 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-06 18:18:38,164 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-06 18:18:38,164 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-06 18:18:38,164 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-06 18:18:38,172 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 06:18:38" (1/1) ... [2022-04-06 18:18:38,172 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 06:18:38" (1/1) ... [2022-04-06 18:18:38,177 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 06:18:38" (1/1) ... [2022-04-06 18:18:38,177 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 06:18:38" (1/1) ... [2022-04-06 18:18:38,186 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 06:18:38" (1/1) ... [2022-04-06 18:18:38,189 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 06:18:38" (1/1) ... [2022-04-06 18:18:38,190 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 06:18:38" (1/1) ... [2022-04-06 18:18:38,193 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-06 18:18:38,194 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-06 18:18:38,194 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-06 18:18:38,194 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-06 18:18:38,195 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 06:18:38" (1/1) ... [2022-04-06 18:18:38,200 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-06 18:18:38,210 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:18:38,219 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2022-04-06 18:18:38,226 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2022-04-06 18:18:38,266 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-06 18:18:38,267 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-06 18:18:38,267 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-06 18:18:38,267 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-06 18:18:38,267 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-06 18:18:38,267 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-06 18:18:38,267 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-06 18:18:38,267 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-06 18:18:38,268 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-06 18:18:38,268 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-06 18:18:38,268 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_short [2022-04-06 18:18:38,269 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-06 18:18:38,269 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-06 18:18:38,269 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-06 18:18:38,269 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-06 18:18:38,269 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-06 18:18:38,269 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-06 18:18:38,269 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-06 18:18:38,269 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-06 18:18:38,269 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-06 18:18:38,310 INFO L234 CfgBuilder]: Building ICFG [2022-04-06 18:18:38,311 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-06 18:18:38,438 INFO L275 CfgBuilder]: Performing block encoding [2022-04-06 18:18:38,442 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-06 18:18:38,442 INFO L299 CfgBuilder]: Removed 1 assume(true) statements. [2022-04-06 18:18:38,443 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.04 06:18:38 BoogieIcfgContainer [2022-04-06 18:18:38,443 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-06 18:18:38,444 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-06 18:18:38,445 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-06 18:18:38,450 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-06 18:18:38,450 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 06.04 06:18:37" (1/3) ... [2022-04-06 18:18:38,451 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2e6cd61e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.04 06:18:38, skipping insertion in model container [2022-04-06 18:18:38,451 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 06:18:38" (2/3) ... [2022-04-06 18:18:38,451 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2e6cd61e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.04 06:18:38, skipping insertion in model container [2022-04-06 18:18:38,451 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.04 06:18:38" (3/3) ... [2022-04-06 18:18:38,452 INFO L111 eAbstractionObserver]: Analyzing ICFG ps4-ll_unwindbound100.c [2022-04-06 18:18:38,457 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:Craig_NestedInterpolation Determinization: PREDICATE_ABSTRACTION [2022-04-06 18:18:38,457 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-06 18:18:38,491 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-06 18:18:38,498 INFO L340 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=Craig_NestedInterpolation, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=All, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP [2022-04-06 18:18:38,498 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-06 18:18:38,510 INFO L276 IsEmpty]: Start isEmpty. Operand has 23 states, 13 states have (on average 1.3846153846153846) internal successors, (18), 14 states have internal predecessors, (18), 5 states have call successors, (5), 3 states have call predecessors, (5), 3 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-06 18:18:38,515 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2022-04-06 18:18:38,515 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:18:38,515 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:18:38,516 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:18:38,520 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:18:38,520 INFO L85 PathProgramCache]: Analyzing trace with hash -2133548928, now seen corresponding path program 1 times [2022-04-06 18:18:38,526 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:38,526 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1473638468] [2022-04-06 18:18:38,534 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 18:18:38,534 INFO L85 PathProgramCache]: Analyzing trace with hash -2133548928, now seen corresponding path program 2 times [2022-04-06 18:18:38,536 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:18:38,537 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1673400868] [2022-04-06 18:18:38,537 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:18:38,538 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:18:38,611 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 18:18:38,675 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-06 18:18:38,677 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 18:18:38,683 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-06 18:18:38,683 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:18:38,684 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1673400868] [2022-04-06 18:18:38,684 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1673400868] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:18:38,684 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:18:38,684 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-06 18:18:38,686 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:18:38,686 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1473638468] [2022-04-06 18:18:38,686 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1473638468] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:18:38,687 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:18:38,687 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-06 18:18:38,687 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [631215312] [2022-04-06 18:18:38,687 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:18:38,690 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-06 18:18:38,690 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:38,722 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-06 18:18:38,723 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-06 18:18:38,724 INFO L87 Difference]: Start difference. First operand has 23 states, 13 states have (on average 1.3846153846153846) internal successors, (18), 14 states have internal predecessors, (18), 5 states have call successors, (5), 3 states have call predecessors, (5), 3 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) Second operand has 3 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 2 states have internal predecessors, (7), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-06 18:18:38,789 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:18:38,789 INFO L93 Difference]: Finished difference Result 41 states and 55 transitions. [2022-04-06 18:18:38,793 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-06 18:18:38,794 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 2 states have internal predecessors, (7), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 11 [2022-04-06 18:18:38,795 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:18:38,799 INFO L225 Difference]: With dead ends: 41 [2022-04-06 18:18:38,799 INFO L226 Difference]: Without dead ends: 19 [2022-04-06 18:18:38,801 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-06 18:18:38,805 INFO L913 BasicCegarLoop]: 25 mSDtfsCounter, 6 mSDsluCounter, 4 mSDsCounter, 0 mSdLazyCounter, 12 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 29 SdHoareTripleChecker+Invalid, 16 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 12 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 18:18:38,807 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 29 Invalid, 16 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 12 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 18:18:38,817 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 19 states. [2022-04-06 18:18:38,829 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 19 to 18. [2022-04-06 18:18:38,829 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 18 states, 10 states have (on average 1.3) internal successors, (13), 11 states have internal predecessors, (13), 5 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-04-06 18:18:38,830 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 18 states to 18 states and 21 transitions. [2022-04-06 18:18:38,831 INFO L78 Accepts]: Start accepts. Automaton has 18 states and 21 transitions. Word has length 11 [2022-04-06 18:18:38,831 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:18:38,831 INFO L478 AbstractCegarLoop]: Abstraction has 18 states and 21 transitions. [2022-04-06 18:18:38,831 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 2 states have internal predecessors, (7), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-06 18:18:38,832 INFO L276 IsEmpty]: Start isEmpty. Operand 18 states and 21 transitions. [2022-04-06 18:18:38,832 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2022-04-06 18:18:38,832 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:18:38,832 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:18:38,832 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-06 18:18:38,833 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:18:38,833 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:18:38,833 INFO L85 PathProgramCache]: Analyzing trace with hash -2118701623, now seen corresponding path program 1 times [2022-04-06 18:18:38,834 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:38,834 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [108089843] [2022-04-06 18:18:38,835 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 18:18:38,835 INFO L85 PathProgramCache]: Analyzing trace with hash -2118701623, now seen corresponding path program 2 times [2022-04-06 18:18:38,835 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:18:38,836 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [444468920] [2022-04-06 18:18:38,836 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:18:38,836 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:18:38,854 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:18:38,859 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [805470843] [2022-04-06 18:18:38,859 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 18:18:38,859 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:38,859 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:18:38,862 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 18:18:38,863 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2022-04-06 18:18:38,896 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2022-04-06 18:18:38,897 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:18:38,904 INFO L263 TraceCheckSpWp]: Trace formula consists of 71 conjuncts, 5 conjunts are in the unsatisfiable core [2022-04-06 18:18:38,907 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:18:38,970 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-06 18:18:38,973 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-06 18:18:38,973 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:18:38,973 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [444468920] [2022-04-06 18:18:38,973 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:18:38,974 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [805470843] [2022-04-06 18:18:38,975 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [805470843] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:18:38,975 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:18:38,975 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-04-06 18:18:38,976 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:18:38,976 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [108089843] [2022-04-06 18:18:38,976 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [108089843] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:18:38,976 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:18:38,976 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-04-06 18:18:38,977 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2023885325] [2022-04-06 18:18:38,977 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:18:38,980 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2022-04-06 18:18:38,980 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:38,980 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2022-04-06 18:18:38,981 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-04-06 18:18:38,981 INFO L87 Difference]: Start difference. First operand 18 states and 21 transitions. Second operand has 4 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-06 18:18:38,994 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:18:38,994 INFO L93 Difference]: Finished difference Result 28 states and 32 transitions. [2022-04-06 18:18:38,995 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2022-04-06 18:18:38,995 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2022-04-06 18:18:38,995 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:18:38,996 INFO L225 Difference]: With dead ends: 28 [2022-04-06 18:18:38,996 INFO L226 Difference]: Without dead ends: 20 [2022-04-06 18:18:38,996 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 9 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-06 18:18:38,997 INFO L913 BasicCegarLoop]: 19 mSDtfsCounter, 0 mSDsluCounter, 32 mSDsCounter, 0 mSdLazyCounter, 7 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 51 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-06 18:18:38,997 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 51 Invalid, 7 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 7 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 18:18:38,998 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 20 states. [2022-04-06 18:18:39,005 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 20 to 20. [2022-04-06 18:18:39,005 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 20 states, 12 states have (on average 1.25) internal successors, (15), 13 states have internal predecessors, (15), 5 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-04-06 18:18:39,006 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 23 transitions. [2022-04-06 18:18:39,006 INFO L78 Accepts]: Start accepts. Automaton has 20 states and 23 transitions. Word has length 12 [2022-04-06 18:18:39,006 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:18:39,006 INFO L478 AbstractCegarLoop]: Abstraction has 20 states and 23 transitions. [2022-04-06 18:18:39,006 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-06 18:18:39,006 INFO L276 IsEmpty]: Start isEmpty. Operand 20 states and 23 transitions. [2022-04-06 18:18:39,006 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2022-04-06 18:18:39,006 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:18:39,007 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:18:39,023 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-06 18:18:39,211 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-06 18:18:39,212 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:18:39,212 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:18:39,212 INFO L85 PathProgramCache]: Analyzing trace with hash -2116914163, now seen corresponding path program 1 times [2022-04-06 18:18:39,212 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:39,212 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [963432210] [2022-04-06 18:18:39,214 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 18:18:39,214 INFO L85 PathProgramCache]: Analyzing trace with hash -2116914163, now seen corresponding path program 2 times [2022-04-06 18:18:39,214 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:18:39,214 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2033701321] [2022-04-06 18:18:39,214 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:18:39,214 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:18:39,225 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:18:39,225 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [453075390] [2022-04-06 18:18:39,225 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 18:18:39,225 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:39,225 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:18:39,229 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 18:18:39,239 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2022-04-06 18:18:39,261 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2022-04-06 18:18:39,261 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:18:39,262 INFO L263 TraceCheckSpWp]: Trace formula consists of 71 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-06 18:18:39,263 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:18:39,330 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-06 18:18:39,330 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-06 18:18:39,330 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:18:39,330 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2033701321] [2022-04-06 18:18:39,330 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:18:39,331 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [453075390] [2022-04-06 18:18:39,331 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [453075390] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:18:39,331 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:18:39,331 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 18:18:39,331 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:18:39,331 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [963432210] [2022-04-06 18:18:39,331 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [963432210] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:18:39,331 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:18:39,331 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 18:18:39,332 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [814410595] [2022-04-06 18:18:39,332 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:18:39,332 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 18:18:39,332 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:39,332 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 18:18:39,332 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-06 18:18:39,333 INFO L87 Difference]: Start difference. First operand 20 states and 23 transitions. Second operand has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-06 18:18:39,364 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:18:39,364 INFO L93 Difference]: Finished difference Result 30 states and 35 transitions. [2022-04-06 18:18:39,364 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-06 18:18:39,364 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2022-04-06 18:18:39,365 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:18:39,365 INFO L225 Difference]: With dead ends: 30 [2022-04-06 18:18:39,365 INFO L226 Difference]: Without dead ends: 26 [2022-04-06 18:18:39,365 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-04-06 18:18:39,366 INFO L913 BasicCegarLoop]: 19 mSDtfsCounter, 6 mSDsluCounter, 45 mSDsCounter, 0 mSdLazyCounter, 28 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 64 SdHoareTripleChecker+Invalid, 30 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 28 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 18:18:39,367 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [8 Valid, 64 Invalid, 30 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 28 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 18:18:39,367 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26 states. [2022-04-06 18:18:39,372 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26 to 26. [2022-04-06 18:18:39,372 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-06 18:18:39,372 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 29 transitions. [2022-04-06 18:18:39,373 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 29 transitions. Word has length 12 [2022-04-06 18:18:39,373 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:18:39,373 INFO L478 AbstractCegarLoop]: Abstraction has 26 states and 29 transitions. [2022-04-06 18:18:39,373 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-06 18:18:39,373 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 29 transitions. [2022-04-06 18:18:39,373 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2022-04-06 18:18:39,374 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:18:39,374 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:18:39,406 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-06 18:18:39,590 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-06 18:18:39,591 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:18:39,591 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:18:39,591 INFO L85 PathProgramCache]: Analyzing trace with hash -263585780, now seen corresponding path program 1 times [2022-04-06 18:18:39,592 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:39,592 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [484081616] [2022-04-06 18:18:39,605 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-04-06 18:18:39,606 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-04-06 18:18:39,606 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-06 18:18:39,606 INFO L85 PathProgramCache]: Analyzing trace with hash -263585780, now seen corresponding path program 2 times [2022-04-06 18:18:39,606 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:18:39,606 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1717221105] [2022-04-06 18:18:39,606 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:18:39,606 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:18:39,614 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:18:39,614 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [30349121] [2022-04-06 18:18:39,614 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 18:18:39,614 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:39,615 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:18:39,616 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 18:18:39,618 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2022-04-06 18:18:39,655 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 18:18:39,655 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:18:39,656 INFO L263 TraceCheckSpWp]: Trace formula consists of 92 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-06 18:18:39,657 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:18:39,705 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-06 18:18:39,705 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 18:18:39,766 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-06 18:18:39,766 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:18:39,767 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1717221105] [2022-04-06 18:18:39,767 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:18:39,767 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [30349121] [2022-04-06 18:18:39,767 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [30349121] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 18:18:39,767 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 18:18:39,767 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2022-04-06 18:18:39,768 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:18:39,768 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [484081616] [2022-04-06 18:18:39,768 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [484081616] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:18:39,768 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:18:39,768 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 18:18:39,768 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [640154569] [2022-04-06 18:18:39,768 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:18:39,769 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 18:18:39,769 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:39,769 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 18:18:39,769 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2022-04-06 18:18:39,769 INFO L87 Difference]: Start difference. First operand 26 states and 29 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 4 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-06 18:18:39,789 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:18:39,790 INFO L93 Difference]: Finished difference Result 36 states and 40 transitions. [2022-04-06 18:18:39,790 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-04-06 18:18:39,790 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 4 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 20 [2022-04-06 18:18:39,790 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:18:39,791 INFO L225 Difference]: With dead ends: 36 [2022-04-06 18:18:39,791 INFO L226 Difference]: Without dead ends: 28 [2022-04-06 18:18:39,791 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 40 GetRequests, 33 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=27, Invalid=45, Unknown=0, NotChecked=0, Total=72 [2022-04-06 18:18:39,792 INFO L913 BasicCegarLoop]: 20 mSDtfsCounter, 2 mSDsluCounter, 46 mSDsCounter, 0 mSdLazyCounter, 11 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 66 SdHoareTripleChecker+Invalid, 14 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 11 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 18:18:39,792 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 66 Invalid, 14 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 11 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 18:18:39,793 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 28 states. [2022-04-06 18:18:39,797 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 28 to 28. [2022-04-06 18:18:39,797 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 28 states, 18 states have (on average 1.1666666666666667) internal successors, (21), 19 states have internal predecessors, (21), 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-06 18:18:39,797 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28 states to 28 states and 31 transitions. [2022-04-06 18:18:39,798 INFO L78 Accepts]: Start accepts. Automaton has 28 states and 31 transitions. Word has length 20 [2022-04-06 18:18:39,798 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:18:39,798 INFO L478 AbstractCegarLoop]: Abstraction has 28 states and 31 transitions. [2022-04-06 18:18:39,798 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 4 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-06 18:18:39,798 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 31 transitions. [2022-04-06 18:18:39,798 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2022-04-06 18:18:39,799 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:18:39,799 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:18:39,818 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-06 18:18:40,015 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-06 18:18:40,016 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:18:40,017 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:18:40,017 INFO L85 PathProgramCache]: Analyzing trace with hash -261798320, now seen corresponding path program 1 times [2022-04-06 18:18:40,017 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:40,017 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1222656720] [2022-04-06 18:18:40,020 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-04-06 18:18:40,021 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-04-06 18:18:40,021 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-06 18:18:40,021 INFO L85 PathProgramCache]: Analyzing trace with hash -261798320, now seen corresponding path program 2 times [2022-04-06 18:18:40,021 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:18:40,021 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1499840873] [2022-04-06 18:18:40,021 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:18:40,021 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:18:40,027 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:18:40,028 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1472466616] [2022-04-06 18:18:40,028 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 18:18:40,028 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:40,028 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:18:40,032 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 18:18:40,034 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2022-04-06 18:18:40,066 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 18:18:40,066 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:18:40,067 INFO L263 TraceCheckSpWp]: Trace formula consists of 92 conjuncts, 11 conjunts are in the unsatisfiable core [2022-04-06 18:18:40,068 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:18:40,182 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-06 18:18:40,182 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 18:18:40,499 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-06 18:18:40,500 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:18:40,502 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1499840873] [2022-04-06 18:18:40,502 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:18:40,503 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1472466616] [2022-04-06 18:18:40,503 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1472466616] provided 1 perfect and 1 imperfect interpolant sequences [2022-04-06 18:18:40,503 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-04-06 18:18:40,503 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2022-04-06 18:18:40,503 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:18:40,503 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1222656720] [2022-04-06 18:18:40,504 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1222656720] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:18:40,504 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:18:40,504 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 18:18:40,504 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2061529785] [2022-04-06 18:18:40,504 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:18:40,504 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 18:18:40,504 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:40,505 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 18:18:40,506 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2022-04-06 18:18:40,506 INFO L87 Difference]: Start difference. First operand 28 states and 31 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), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-06 18:18:40,546 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:18:40,546 INFO L93 Difference]: Finished difference Result 34 states and 36 transitions. [2022-04-06 18:18:40,546 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-06 18:18:40,547 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), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 20 [2022-04-06 18:18:40,547 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:18:40,550 INFO L225 Difference]: With dead ends: 34 [2022-04-06 18:18:40,550 INFO L226 Difference]: Without dead ends: 29 [2022-04-06 18:18:40,551 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 40 GetRequests, 32 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2022-04-06 18:18:40,555 INFO L913 BasicCegarLoop]: 17 mSDtfsCounter, 7 mSDsluCounter, 36 mSDsCounter, 0 mSdLazyCounter, 21 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 53 SdHoareTripleChecker+Invalid, 22 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 21 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 18:18:40,555 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [8 Valid, 53 Invalid, 22 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 21 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 18:18:40,558 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 29 states. [2022-04-06 18:18:40,561 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 29 to 29. [2022-04-06 18:18:40,562 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 29 states, 20 states have (on average 1.1) internal successors, (22), 20 states have internal predecessors, (22), 5 states have call successors, (5), 5 states have call predecessors, (5), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-04-06 18:18:40,562 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 30 transitions. [2022-04-06 18:18:40,562 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 30 transitions. Word has length 20 [2022-04-06 18:18:40,562 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:18:40,563 INFO L478 AbstractCegarLoop]: Abstraction has 29 states and 30 transitions. [2022-04-06 18:18:40,563 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), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-06 18:18:40,563 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 30 transitions. [2022-04-06 18:18:40,563 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2022-04-06 18:18:40,563 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:18:40,563 INFO L499 BasicCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:18:40,582 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2022-04-06 18:18:40,764 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-06 18:18:40,764 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:18:40,764 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:18:40,764 INFO L85 PathProgramCache]: Analyzing trace with hash 891414954, now seen corresponding path program 1 times [2022-04-06 18:18:40,765 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:40,765 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1712914389] [2022-04-06 18:18:40,768 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-04-06 18:18:40,768 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-04-06 18:18:40,768 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-06 18:18:40,768 INFO L85 PathProgramCache]: Analyzing trace with hash 891414954, now seen corresponding path program 2 times [2022-04-06 18:18:40,769 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:18:40,769 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1427103169] [2022-04-06 18:18:40,769 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:18:40,769 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:18:40,794 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:18:40,795 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1991221184] [2022-04-06 18:18:40,795 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 18:18:40,795 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:40,795 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:18:40,812 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 18:18:40,813 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2022-04-06 18:18:40,847 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 18:18:40,847 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:18:40,848 INFO L263 TraceCheckSpWp]: Trace formula consists of 102 conjuncts, 12 conjunts are in the unsatisfiable core [2022-04-06 18:18:40,849 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:18:40,996 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 4 proven. 4 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-06 18:18:40,996 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 18:18:41,113 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:18:41,113 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1427103169] [2022-04-06 18:18:41,113 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:18:41,113 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1991221184] [2022-04-06 18:18:41,113 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1991221184] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-06 18:18:41,113 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-06 18:18:41,114 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2022-04-06 18:18:41,114 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:18:41,114 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1712914389] [2022-04-06 18:18:41,114 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1712914389] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:18:41,114 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:18:41,114 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2022-04-06 18:18:41,114 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1499084380] [2022-04-06 18:18:41,114 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:18:41,114 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-04-06 18:18:41,114 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:41,115 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-04-06 18:18:41,115 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=66, Unknown=0, NotChecked=0, Total=90 [2022-04-06 18:18:41,115 INFO L87 Difference]: Start difference. First operand 29 states and 30 transitions. Second operand has 7 states, 6 states have (on average 2.5) internal successors, (15), 6 states have internal predecessors, (15), 4 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-04-06 18:18:41,179 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:18:41,179 INFO L93 Difference]: Finished difference Result 36 states and 38 transitions. [2022-04-06 18:18:41,180 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-04-06 18:18:41,180 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 2.5) internal successors, (15), 6 states have internal predecessors, (15), 4 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Word has length 26 [2022-04-06 18:18:41,180 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:18:41,181 INFO L225 Difference]: With dead ends: 36 [2022-04-06 18:18:41,181 INFO L226 Difference]: Without dead ends: 31 [2022-04-06 18:18:41,181 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 41 GetRequests, 30 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-06 18:18:41,181 INFO L913 BasicCegarLoop]: 22 mSDtfsCounter, 2 mSDsluCounter, 78 mSDsCounter, 0 mSdLazyCounter, 46 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 100 SdHoareTripleChecker+Invalid, 46 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 46 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 18:18:41,182 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 100 Invalid, 46 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 46 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 18:18:41,182 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2022-04-06 18:18:41,186 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 31. [2022-04-06 18:18:41,186 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 31 states, 21 states have (on average 1.0952380952380953) internal successors, (23), 21 states have internal predecessors, (23), 6 states have call successors, (6), 5 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-06 18:18:41,187 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 33 transitions. [2022-04-06 18:18:41,187 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 33 transitions. Word has length 26 [2022-04-06 18:18:41,187 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:18:41,187 INFO L478 AbstractCegarLoop]: Abstraction has 31 states and 33 transitions. [2022-04-06 18:18:41,187 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 2.5) internal successors, (15), 6 states have internal predecessors, (15), 4 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-04-06 18:18:41,187 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 33 transitions. [2022-04-06 18:18:41,188 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2022-04-06 18:18:41,188 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:18:41,188 INFO L499 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:18:41,207 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2022-04-06 18:18:41,403 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-06 18:18:41,403 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:18:41,404 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:18:41,404 INFO L85 PathProgramCache]: Analyzing trace with hash -1647059121, now seen corresponding path program 3 times [2022-04-06 18:18:41,404 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:41,404 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [689365979] [2022-04-06 18:18:41,406 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-04-06 18:18:41,407 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-04-06 18:18:41,407 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-06 18:18:41,407 INFO L85 PathProgramCache]: Analyzing trace with hash -1647059121, now seen corresponding path program 4 times [2022-04-06 18:18:41,407 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:18:41,407 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1681760057] [2022-04-06 18:18:41,407 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:18:41,407 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:18:41,412 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:18:41,412 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [57356708] [2022-04-06 18:18:41,412 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-04-06 18:18:41,413 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:41,413 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:18:41,413 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 18:18:41,414 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2022-04-06 18:18:41,442 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-04-06 18:18:41,442 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:18:41,442 INFO L263 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 9 conjunts are in the unsatisfiable core [2022-04-06 18:18:41,444 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:18:41,503 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 4 proven. 12 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-06 18:18:41,503 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 18:18:41,566 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 4 proven. 8 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-06 18:18:41,566 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:18:41,567 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1681760057] [2022-04-06 18:18:41,567 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:18:41,567 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [57356708] [2022-04-06 18:18:41,567 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [57356708] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 18:18:41,567 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 18:18:41,567 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 10 [2022-04-06 18:18:41,567 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:18:41,567 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [689365979] [2022-04-06 18:18:41,567 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [689365979] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:18:41,567 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:18:41,567 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-06 18:18:41,568 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [161049502] [2022-04-06 18:18:41,568 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:18:41,568 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-06 18:18:41,568 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:41,568 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-06 18:18:41,568 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2022-04-06 18:18:41,568 INFO L87 Difference]: Start difference. First operand 31 states and 33 transitions. Second operand has 6 states, 6 states have (on average 3.3333333333333335) internal successors, (20), 5 states have internal predecessors, (20), 5 states have call successors, (5), 5 states have call predecessors, (5), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-04-06 18:18:41,597 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:18:41,597 INFO L93 Difference]: Finished difference Result 42 states and 43 transitions. [2022-04-06 18:18:41,598 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-04-06 18:18:41,598 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 3.3333333333333335) internal successors, (20), 5 states have internal predecessors, (20), 5 states have call successors, (5), 5 states have call predecessors, (5), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Word has length 28 [2022-04-06 18:18:41,598 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:18:41,598 INFO L225 Difference]: With dead ends: 42 [2022-04-06 18:18:41,598 INFO L226 Difference]: Without dead ends: 37 [2022-04-06 18:18:41,599 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 57 GetRequests, 47 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-06 18:18:41,599 INFO L913 BasicCegarLoop]: 19 mSDtfsCounter, 4 mSDsluCounter, 45 mSDsCounter, 0 mSdLazyCounter, 16 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 64 SdHoareTripleChecker+Invalid, 22 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 16 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 18:18:41,599 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [4 Valid, 64 Invalid, 22 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 16 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 18:18:41,600 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2022-04-06 18:18:41,604 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 37. [2022-04-06 18:18:41,604 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 26 states have (on average 1.0769230769230769) internal successors, (28), 26 states have internal predecessors, (28), 6 states have call successors, (6), 6 states have call predecessors, (6), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2022-04-06 18:18:41,604 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 38 transitions. [2022-04-06 18:18:41,605 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 38 transitions. Word has length 28 [2022-04-06 18:18:41,605 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:18:41,605 INFO L478 AbstractCegarLoop]: Abstraction has 37 states and 38 transitions. [2022-04-06 18:18:41,605 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 3.3333333333333335) internal successors, (20), 5 states have internal predecessors, (20), 5 states have call successors, (5), 5 states have call predecessors, (5), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-04-06 18:18:41,605 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 38 transitions. [2022-04-06 18:18:41,605 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2022-04-06 18:18:41,605 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:18:41,605 INFO L499 BasicCegarLoop]: trace histogram [4, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:18:41,624 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2022-04-06 18:18:41,815 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-06 18:18:41,815 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:18:41,816 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:18:41,816 INFO L85 PathProgramCache]: Analyzing trace with hash 1036651181, now seen corresponding path program 3 times [2022-04-06 18:18:41,816 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:41,816 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [658708546] [2022-04-06 18:18:41,818 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-04-06 18:18:41,818 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-04-06 18:18:41,819 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-06 18:18:41,819 INFO L85 PathProgramCache]: Analyzing trace with hash 1036651181, now seen corresponding path program 4 times [2022-04-06 18:18:41,819 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:18:41,819 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [403131166] [2022-04-06 18:18:41,819 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:18:41,819 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:18:41,824 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:18:41,824 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [290231355] [2022-04-06 18:18:41,824 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-04-06 18:18:41,824 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:41,824 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:18:41,826 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 18:18:41,827 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2022-04-06 18:18:41,873 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-04-06 18:18:41,873 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:18:41,874 INFO L263 TraceCheckSpWp]: Trace formula consists of 123 conjuncts, 17 conjunts are in the unsatisfiable core [2022-04-06 18:18:41,875 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:18:42,019 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 6 proven. 12 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-06 18:18:42,019 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 18:18:42,194 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:18:42,194 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [403131166] [2022-04-06 18:18:42,194 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:18:42,194 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [290231355] [2022-04-06 18:18:42,194 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [290231355] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-06 18:18:42,194 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-06 18:18:42,194 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8] total 8 [2022-04-06 18:18:42,194 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:18:42,194 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [658708546] [2022-04-06 18:18:42,194 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [658708546] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:18:42,195 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:18:42,195 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2022-04-06 18:18:42,195 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1482053944] [2022-04-06 18:18:42,195 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:18:42,195 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-04-06 18:18:42,195 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:42,195 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-04-06 18:18:42,195 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=32, Invalid=100, Unknown=0, NotChecked=0, Total=132 [2022-04-06 18:18:42,196 INFO L87 Difference]: Start difference. First operand 37 states and 38 transitions. Second operand has 8 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 7 states have internal predecessors, (18), 5 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2022-04-06 18:18:42,258 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:18:42,258 INFO L93 Difference]: Finished difference Result 44 states and 46 transitions. [2022-04-06 18:18:42,258 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-04-06 18:18:42,258 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 7 states have internal predecessors, (18), 5 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Word has length 34 [2022-04-06 18:18:42,258 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:18:42,259 INFO L225 Difference]: With dead ends: 44 [2022-04-06 18:18:42,259 INFO L226 Difference]: Without dead ends: 39 [2022-04-06 18:18:42,259 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 57 GetRequests, 44 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=42, Invalid=140, Unknown=0, NotChecked=0, Total=182 [2022-04-06 18:18:42,260 INFO L913 BasicCegarLoop]: 26 mSDtfsCounter, 2 mSDsluCounter, 106 mSDsCounter, 0 mSdLazyCounter, 71 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 132 SdHoareTripleChecker+Invalid, 71 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 71 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 18:18:42,260 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 132 Invalid, 71 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 71 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 18:18:42,260 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2022-04-06 18:18:42,264 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 39. [2022-04-06 18:18:42,265 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 39 states, 27 states have (on average 1.0740740740740742) internal successors, (29), 27 states have internal predecessors, (29), 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-06 18:18:42,265 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 41 transitions. [2022-04-06 18:18:42,265 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 41 transitions. Word has length 34 [2022-04-06 18:18:42,265 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:18:42,265 INFO L478 AbstractCegarLoop]: Abstraction has 39 states and 41 transitions. [2022-04-06 18:18:42,266 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 7 states have internal predecessors, (18), 5 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2022-04-06 18:18:42,266 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 41 transitions. [2022-04-06 18:18:42,266 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2022-04-06 18:18:42,266 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:18:42,266 INFO L499 BasicCegarLoop]: trace histogram [4, 4, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:18:42,277 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2022-04-06 18:18:42,477 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-06 18:18:42,477 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:18:42,478 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:18:42,478 INFO L85 PathProgramCache]: Analyzing trace with hash 486001554, now seen corresponding path program 5 times [2022-04-06 18:18:42,478 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:42,478 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [947182044] [2022-04-06 18:18:42,480 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-04-06 18:18:42,481 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-04-06 18:18:42,481 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-06 18:18:42,481 INFO L85 PathProgramCache]: Analyzing trace with hash 486001554, now seen corresponding path program 6 times [2022-04-06 18:18:42,481 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:18:42,481 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [242002423] [2022-04-06 18:18:42,481 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:18:42,481 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:18:42,487 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:18:42,488 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1863033599] [2022-04-06 18:18:42,488 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-04-06 18:18:42,488 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:42,488 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:18:42,499 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 18:18:42,500 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2022-04-06 18:18:42,544 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2022-04-06 18:18:42,545 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:18:42,545 INFO L263 TraceCheckSpWp]: Trace formula consists of 134 conjuncts, 11 conjunts are in the unsatisfiable core [2022-04-06 18:18:42,547 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:18:42,621 INFO L134 CoverageAnalysis]: Checked inductivity of 36 backedges. 6 proven. 30 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-06 18:18:42,621 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 18:18:42,704 INFO L134 CoverageAnalysis]: Checked inductivity of 36 backedges. 6 proven. 18 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-06 18:18:42,704 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:18:42,704 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [242002423] [2022-04-06 18:18:42,704 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:18:42,704 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1863033599] [2022-04-06 18:18:42,704 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1863033599] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 18:18:42,704 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 18:18:42,704 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 12 [2022-04-06 18:18:42,706 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:18:42,706 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [947182044] [2022-04-06 18:18:42,706 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [947182044] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:18:42,707 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:18:42,707 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2022-04-06 18:18:42,707 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [86436114] [2022-04-06 18:18:42,707 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:18:42,707 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-04-06 18:18:42,707 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:42,707 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-04-06 18:18:42,707 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=50, Invalid=82, Unknown=0, NotChecked=0, Total=132 [2022-04-06 18:18:42,708 INFO L87 Difference]: Start difference. First operand 39 states and 41 transitions. Second operand has 7 states, 7 states have (on average 3.7142857142857144) internal successors, (26), 6 states have internal predecessors, (26), 6 states have call successors, (6), 6 states have call predecessors, (6), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2022-04-06 18:18:42,742 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:18:42,743 INFO L93 Difference]: Finished difference Result 50 states and 51 transitions. [2022-04-06 18:18:42,743 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-04-06 18:18:42,743 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 3.7142857142857144) internal successors, (26), 6 states have internal predecessors, (26), 6 states have call successors, (6), 6 states have call predecessors, (6), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Word has length 36 [2022-04-06 18:18:42,743 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:18:42,744 INFO L225 Difference]: With dead ends: 50 [2022-04-06 18:18:42,744 INFO L226 Difference]: Without dead ends: 45 [2022-04-06 18:18:42,745 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 74 GetRequests, 61 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-06 18:18:42,746 INFO L913 BasicCegarLoop]: 20 mSDtfsCounter, 4 mSDsluCounter, 50 mSDsCounter, 0 mSdLazyCounter, 19 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 70 SdHoareTripleChecker+Invalid, 25 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 19 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 18:18:42,746 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [4 Valid, 70 Invalid, 25 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 19 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 18:18:42,747 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2022-04-06 18:18:42,763 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 45. [2022-04-06 18:18:42,763 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 32 states have (on average 1.0625) internal successors, (34), 32 states have internal predecessors, (34), 7 states have call successors, (7), 7 states have call predecessors, (7), 5 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-06 18:18:42,764 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 46 transitions. [2022-04-06 18:18:42,764 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 46 transitions. Word has length 36 [2022-04-06 18:18:42,764 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:18:42,764 INFO L478 AbstractCegarLoop]: Abstraction has 45 states and 46 transitions. [2022-04-06 18:18:42,764 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 3.7142857142857144) internal successors, (26), 6 states have internal predecessors, (26), 6 states have call successors, (6), 6 states have call predecessors, (6), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2022-04-06 18:18:42,764 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 46 transitions. [2022-04-06 18:18:42,765 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2022-04-06 18:18:42,765 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:18:42,765 INFO L499 BasicCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:18:42,787 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2022-04-06 18:18:42,965 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-06 18:18:42,966 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:18:42,966 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:18:42,966 INFO L85 PathProgramCache]: Analyzing trace with hash -1383171920, now seen corresponding path program 5 times [2022-04-06 18:18:42,966 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:42,966 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [459701232] [2022-04-06 18:18:42,969 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-04-06 18:18:42,969 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-04-06 18:18:42,969 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-06 18:18:42,969 INFO L85 PathProgramCache]: Analyzing trace with hash -1383171920, now seen corresponding path program 6 times [2022-04-06 18:18:42,969 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:18:42,969 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1273304220] [2022-04-06 18:18:42,969 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:18:42,969 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:18:42,974 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:18:42,974 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1254278772] [2022-04-06 18:18:42,974 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-04-06 18:18:42,974 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:42,974 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:18:42,975 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 18:18:42,976 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2022-04-06 18:18:43,058 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2022-04-06 18:18:43,059 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:18:43,060 INFO L263 TraceCheckSpWp]: Trace formula consists of 144 conjuncts, 20 conjunts are in the unsatisfiable core [2022-04-06 18:18:43,061 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:18:43,201 INFO L134 CoverageAnalysis]: Checked inductivity of 56 backedges. 8 proven. 24 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-04-06 18:18:43,201 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 18:18:43,302 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:18:43,303 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1273304220] [2022-04-06 18:18:43,303 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:18:43,303 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1254278772] [2022-04-06 18:18:43,303 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1254278772] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-06 18:18:43,303 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-06 18:18:43,303 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2022-04-06 18:18:43,303 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:18:43,303 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [459701232] [2022-04-06 18:18:43,303 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [459701232] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:18:43,303 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:18:43,304 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2022-04-06 18:18:43,304 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [311984728] [2022-04-06 18:18:43,304 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:18:43,304 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-04-06 18:18:43,304 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:43,304 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-04-06 18:18:43,304 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2022-04-06 18:18:43,304 INFO L87 Difference]: Start difference. First operand 45 states and 46 transitions. Second operand has 9 states, 8 states have (on average 2.625) internal successors, (21), 8 states have internal predecessors, (21), 6 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-06 18:18:43,386 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:18:43,386 INFO L93 Difference]: Finished difference Result 52 states and 54 transitions. [2022-04-06 18:18:43,387 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-04-06 18:18:43,387 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 2.625) internal successors, (21), 8 states have internal predecessors, (21), 6 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) Word has length 42 [2022-04-06 18:18:43,387 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:18:43,387 INFO L225 Difference]: With dead ends: 52 [2022-04-06 18:18:43,387 INFO L226 Difference]: Without dead ends: 47 [2022-04-06 18:18:43,388 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 57 GetRequests, 44 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-06 18:18:43,388 INFO L913 BasicCegarLoop]: 30 mSDtfsCounter, 2 mSDsluCounter, 138 mSDsCounter, 0 mSdLazyCounter, 102 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 168 SdHoareTripleChecker+Invalid, 102 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 102 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 18:18:43,388 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 168 Invalid, 102 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 102 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 18:18:43,388 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2022-04-06 18:18:43,392 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 47. [2022-04-06 18:18:43,392 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 47 states, 33 states have (on average 1.0606060606060606) internal successors, (35), 33 states have internal predecessors, (35), 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-06 18:18:43,393 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 49 transitions. [2022-04-06 18:18:43,393 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 49 transitions. Word has length 42 [2022-04-06 18:18:43,393 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:18:43,393 INFO L478 AbstractCegarLoop]: Abstraction has 47 states and 49 transitions. [2022-04-06 18:18:43,393 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 2.625) internal successors, (21), 8 states have internal predecessors, (21), 6 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-06 18:18:43,393 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 49 transitions. [2022-04-06 18:18:43,394 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2022-04-06 18:18:43,394 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:18:43,394 INFO L499 BasicCegarLoop]: trace histogram [5, 5, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:18:43,411 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2022-04-06 18:18:43,606 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-06 18:18:43,606 INFO L403 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:18:43,607 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:18:43,607 INFO L85 PathProgramCache]: Analyzing trace with hash -1386691371, now seen corresponding path program 7 times [2022-04-06 18:18:43,607 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:43,607 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [4836245] [2022-04-06 18:18:43,609 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-04-06 18:18:43,609 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-04-06 18:18:43,609 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-06 18:18:43,609 INFO L85 PathProgramCache]: Analyzing trace with hash -1386691371, now seen corresponding path program 8 times [2022-04-06 18:18:43,609 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:18:43,609 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1175009011] [2022-04-06 18:18:43,609 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:18:43,609 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:18:43,614 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:18:43,614 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1479251450] [2022-04-06 18:18:43,614 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 18:18:43,614 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:43,614 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:18:43,615 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 18:18:43,644 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2022-04-06 18:18:43,652 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 18:18:43,652 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:18:43,653 INFO L263 TraceCheckSpWp]: Trace formula consists of 155 conjuncts, 13 conjunts are in the unsatisfiable core [2022-04-06 18:18:43,654 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:18:43,761 INFO L134 CoverageAnalysis]: Checked inductivity of 64 backedges. 8 proven. 56 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-06 18:18:43,761 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 18:18:43,866 INFO L134 CoverageAnalysis]: Checked inductivity of 64 backedges. 8 proven. 32 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-04-06 18:18:43,866 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:18:43,866 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1175009011] [2022-04-06 18:18:43,866 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:18:43,866 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1479251450] [2022-04-06 18:18:43,866 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1479251450] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 18:18:43,866 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 18:18:43,866 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 14 [2022-04-06 18:18:43,866 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:18:43,867 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [4836245] [2022-04-06 18:18:43,867 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [4836245] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:18:43,867 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:18:43,867 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2022-04-06 18:18:43,867 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1071112711] [2022-04-06 18:18:43,867 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:18:43,867 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-04-06 18:18:43,867 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:43,867 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-04-06 18:18:43,868 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=111, Unknown=0, NotChecked=0, Total=182 [2022-04-06 18:18:43,868 INFO L87 Difference]: Start difference. First operand 47 states and 49 transitions. Second operand has 8 states, 8 states have (on average 4.0) internal successors, (32), 7 states have internal predecessors, (32), 7 states have call successors, (7), 7 states have call predecessors, (7), 5 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-06 18:18:43,937 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:18:43,937 INFO L93 Difference]: Finished difference Result 58 states and 59 transitions. [2022-04-06 18:18:43,938 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-04-06 18:18:43,938 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 4.0) internal successors, (32), 7 states have internal predecessors, (32), 7 states have call successors, (7), 7 states have call predecessors, (7), 5 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) Word has length 44 [2022-04-06 18:18:43,938 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:18:43,938 INFO L225 Difference]: With dead ends: 58 [2022-04-06 18:18:43,939 INFO L226 Difference]: Without dead ends: 53 [2022-04-06 18:18:43,939 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 91 GetRequests, 75 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-06 18:18:43,939 INFO L913 BasicCegarLoop]: 21 mSDtfsCounter, 8 mSDsluCounter, 48 mSDsCounter, 0 mSdLazyCounter, 24 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 69 SdHoareTripleChecker+Invalid, 36 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 24 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 18:18:43,939 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [8 Valid, 69 Invalid, 36 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 24 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 18:18:43,940 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 53 states. [2022-04-06 18:18:43,944 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 53 to 53. [2022-04-06 18:18:43,944 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 53 states, 38 states have (on average 1.0526315789473684) internal successors, (40), 38 states have internal predecessors, (40), 8 states have call successors, (8), 8 states have call predecessors, (8), 6 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-06 18:18:43,944 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 54 transitions. [2022-04-06 18:18:43,944 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 54 transitions. Word has length 44 [2022-04-06 18:18:43,945 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:18:43,945 INFO L478 AbstractCegarLoop]: Abstraction has 53 states and 54 transitions. [2022-04-06 18:18:43,945 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 4.0) internal successors, (32), 7 states have internal predecessors, (32), 7 states have call successors, (7), 7 states have call predecessors, (7), 5 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-06 18:18:43,945 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 54 transitions. [2022-04-06 18:18:43,945 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2022-04-06 18:18:43,945 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:18:43,945 INFO L499 BasicCegarLoop]: trace histogram [6, 5, 5, 5, 5, 5, 5, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:18:43,964 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-06 18:18:44,157 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-06 18:18:44,157 INFO L403 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:18:44,157 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:18:44,158 INFO L85 PathProgramCache]: Analyzing trace with hash 1037185971, now seen corresponding path program 7 times [2022-04-06 18:18:44,158 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:44,158 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [670839280] [2022-04-06 18:18:44,160 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-04-06 18:18:44,160 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-04-06 18:18:44,160 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-06 18:18:44,160 INFO L85 PathProgramCache]: Analyzing trace with hash 1037185971, now seen corresponding path program 8 times [2022-04-06 18:18:44,160 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:18:44,160 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1803795129] [2022-04-06 18:18:44,160 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:18:44,160 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:18:44,165 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:18:44,165 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1540748460] [2022-04-06 18:18:44,165 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 18:18:44,165 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:44,166 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:18:44,166 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-06 18:18:44,167 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-06 18:18:44,262 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 18:18:44,262 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:18:44,263 INFO L263 TraceCheckSpWp]: Trace formula consists of 165 conjuncts, 24 conjunts are in the unsatisfiable core [2022-04-06 18:18:44,264 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:18:44,440 INFO L134 CoverageAnalysis]: Checked inductivity of 90 backedges. 10 proven. 40 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2022-04-06 18:18:44,440 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 18:18:44,581 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:18:44,581 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1803795129] [2022-04-06 18:18:44,581 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:18:44,581 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1540748460] [2022-04-06 18:18:44,581 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1540748460] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-06 18:18:44,581 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-06 18:18:44,581 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2022-04-06 18:18:44,582 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:18:44,582 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [670839280] [2022-04-06 18:18:44,582 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [670839280] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:18:44,582 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:18:44,582 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [] total 10 [2022-04-06 18:18:44,582 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1614120687] [2022-04-06 18:18:44,582 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:18:44,582 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-04-06 18:18:44,582 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:44,582 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-04-06 18:18:44,583 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=123, Unknown=0, NotChecked=0, Total=156 [2022-04-06 18:18:44,583 INFO L87 Difference]: Start difference. First operand 53 states and 54 transitions. Second operand has 10 states, 9 states have (on average 2.6666666666666665) internal successors, (24), 9 states have internal predecessors, (24), 7 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-06 18:18:44,687 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:18:44,687 INFO L93 Difference]: Finished difference Result 60 states and 62 transitions. [2022-04-06 18:18:44,687 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-04-06 18:18:44,687 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 2.6666666666666665) internal successors, (24), 9 states have internal predecessors, (24), 7 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Word has length 50 [2022-04-06 18:18:44,688 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:18:44,688 INFO L225 Difference]: With dead ends: 60 [2022-04-06 18:18:44,688 INFO L226 Difference]: Without dead ends: 55 [2022-04-06 18:18:44,688 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 65 GetRequests, 51 SyntacticMatches, 1 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=43, Invalid=167, Unknown=0, NotChecked=0, Total=210 [2022-04-06 18:18:44,689 INFO L913 BasicCegarLoop]: 34 mSDtfsCounter, 2 mSDsluCounter, 174 mSDsCounter, 0 mSdLazyCounter, 139 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 208 SdHoareTripleChecker+Invalid, 139 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 139 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 18:18:44,689 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 208 Invalid, 139 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 139 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 18:18:44,689 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2022-04-06 18:18:44,693 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 55. [2022-04-06 18:18:44,693 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 55 states, 39 states have (on average 1.0512820512820513) internal successors, (41), 39 states have internal predecessors, (41), 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-06 18:18:44,694 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 57 transitions. [2022-04-06 18:18:44,694 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 57 transitions. Word has length 50 [2022-04-06 18:18:44,694 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:18:44,694 INFO L478 AbstractCegarLoop]: Abstraction has 55 states and 57 transitions. [2022-04-06 18:18:44,694 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 2.6666666666666665) internal successors, (24), 9 states have internal predecessors, (24), 7 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-06 18:18:44,695 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 57 transitions. [2022-04-06 18:18:44,695 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 53 [2022-04-06 18:18:44,695 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:18:44,695 INFO L499 BasicCegarLoop]: trace histogram [6, 6, 5, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:18:44,700 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-06 18:18:44,900 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-06 18:18:44,900 INFO L403 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:18:44,900 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:18:44,900 INFO L85 PathProgramCache]: Analyzing trace with hash 999934744, now seen corresponding path program 9 times [2022-04-06 18:18:44,901 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:44,901 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [530513170] [2022-04-06 18:18:44,902 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-04-06 18:18:44,903 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-04-06 18:18:44,903 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-06 18:18:44,903 INFO L85 PathProgramCache]: Analyzing trace with hash 999934744, now seen corresponding path program 10 times [2022-04-06 18:18:44,903 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:18:44,903 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [639328596] [2022-04-06 18:18:44,903 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:18:44,903 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:18:44,908 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:18:44,908 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [680040015] [2022-04-06 18:18:44,908 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-04-06 18:18:44,908 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:44,908 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:18:44,909 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-06 18:18:44,910 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-06 18:18:45,031 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-04-06 18:18:45,031 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:18:45,032 INFO L263 TraceCheckSpWp]: Trace formula consists of 176 conjuncts, 15 conjunts are in the unsatisfiable core [2022-04-06 18:18:45,033 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:18:45,124 INFO L134 CoverageAnalysis]: Checked inductivity of 100 backedges. 10 proven. 90 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-06 18:18:45,124 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 18:18:45,250 INFO L134 CoverageAnalysis]: Checked inductivity of 100 backedges. 10 proven. 50 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2022-04-06 18:18:45,250 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:18:45,250 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [639328596] [2022-04-06 18:18:45,250 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:18:45,251 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [680040015] [2022-04-06 18:18:45,251 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [680040015] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 18:18:45,251 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 18:18:45,251 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 16 [2022-04-06 18:18:45,251 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:18:45,251 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [530513170] [2022-04-06 18:18:45,251 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [530513170] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:18:45,251 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:18:45,251 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2022-04-06 18:18:45,251 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [666868537] [2022-04-06 18:18:45,251 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:18:45,251 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-04-06 18:18:45,252 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:45,252 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-04-06 18:18:45,252 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=96, Invalid=144, Unknown=0, NotChecked=0, Total=240 [2022-04-06 18:18:45,252 INFO L87 Difference]: Start difference. First operand 55 states and 57 transitions. Second operand has 9 states, 9 states have (on average 4.222222222222222) internal successors, (38), 8 states have internal predecessors, (38), 8 states have call successors, (8), 8 states have call predecessors, (8), 6 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-06 18:18:45,309 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:18:45,309 INFO L93 Difference]: Finished difference Result 66 states and 67 transitions. [2022-04-06 18:18:45,309 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2022-04-06 18:18:45,309 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 4.222222222222222) internal successors, (38), 8 states have internal predecessors, (38), 8 states have call successors, (8), 8 states have call predecessors, (8), 6 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Word has length 52 [2022-04-06 18:18:45,310 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:18:45,310 INFO L225 Difference]: With dead ends: 66 [2022-04-06 18:18:45,310 INFO L226 Difference]: Without dead ends: 61 [2022-04-06 18:18:45,310 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 108 GetRequests, 89 SyntacticMatches, 0 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 26 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=171, Invalid=249, Unknown=0, NotChecked=0, Total=420 [2022-04-06 18:18:45,311 INFO L913 BasicCegarLoop]: 22 mSDtfsCounter, 2 mSDsluCounter, 67 mSDsCounter, 0 mSdLazyCounter, 30 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 89 SdHoareTripleChecker+Invalid, 33 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 30 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 18:18:45,311 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 89 Invalid, 33 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 30 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 18:18:45,311 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 61 states. [2022-04-06 18:18:45,315 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 61 to 61. [2022-04-06 18:18:45,316 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 61 states, 44 states have (on average 1.0454545454545454) internal successors, (46), 44 states have internal predecessors, (46), 9 states have call successors, (9), 9 states have call predecessors, (9), 7 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-06 18:18:45,316 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 61 states to 61 states and 62 transitions. [2022-04-06 18:18:45,316 INFO L78 Accepts]: Start accepts. Automaton has 61 states and 62 transitions. Word has length 52 [2022-04-06 18:18:45,316 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:18:45,316 INFO L478 AbstractCegarLoop]: Abstraction has 61 states and 62 transitions. [2022-04-06 18:18:45,316 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 4.222222222222222) internal successors, (38), 8 states have internal predecessors, (38), 8 states have call successors, (8), 8 states have call predecessors, (8), 6 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-06 18:18:45,316 INFO L276 IsEmpty]: Start isEmpty. Operand 61 states and 62 transitions. [2022-04-06 18:18:45,317 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2022-04-06 18:18:45,317 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:18:45,317 INFO L499 BasicCegarLoop]: trace histogram [7, 6, 6, 6, 6, 6, 6, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:18:45,335 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-06 18:18:45,535 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-06 18:18:45,536 INFO L403 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:18:45,536 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:18:45,536 INFO L85 PathProgramCache]: Analyzing trace with hash -1795671114, now seen corresponding path program 9 times [2022-04-06 18:18:45,536 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:45,536 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [672453765] [2022-04-06 18:18:45,538 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-04-06 18:18:45,538 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-04-06 18:18:45,538 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-06 18:18:45,538 INFO L85 PathProgramCache]: Analyzing trace with hash -1795671114, now seen corresponding path program 10 times [2022-04-06 18:18:45,538 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:18:45,538 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2008606998] [2022-04-06 18:18:45,538 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:18:45,538 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:18:45,543 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:18:45,544 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [159471612] [2022-04-06 18:18:45,544 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-04-06 18:18:45,544 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:45,544 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:18:45,545 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-06 18:18:45,546 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-06 18:18:45,809 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-04-06 18:18:45,809 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:18:45,810 INFO L263 TraceCheckSpWp]: Trace formula consists of 186 conjuncts, 28 conjunts are in the unsatisfiable core [2022-04-06 18:18:45,811 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:18:46,063 INFO L134 CoverageAnalysis]: Checked inductivity of 132 backedges. 12 proven. 60 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2022-04-06 18:18:46,063 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 18:18:46,163 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:18:46,163 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2008606998] [2022-04-06 18:18:46,163 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:18:46,163 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [159471612] [2022-04-06 18:18:46,163 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [159471612] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-06 18:18:46,163 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-06 18:18:46,163 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2022-04-06 18:18:46,163 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:18:46,164 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [672453765] [2022-04-06 18:18:46,164 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [672453765] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:18:46,164 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:18:46,164 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [11] imperfect sequences [] total 11 [2022-04-06 18:18:46,164 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [281175257] [2022-04-06 18:18:46,164 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:18:46,164 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2022-04-06 18:18:46,164 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:46,164 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2022-04-06 18:18:46,165 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=36, Invalid=146, Unknown=0, NotChecked=0, Total=182 [2022-04-06 18:18:46,165 INFO L87 Difference]: Start difference. First operand 61 states and 62 transitions. Second operand has 11 states, 10 states have (on average 2.7) internal successors, (27), 10 states have internal predecessors, (27), 8 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-06 18:18:46,287 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:18:46,288 INFO L93 Difference]: Finished difference Result 68 states and 70 transitions. [2022-04-06 18:18:46,288 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-04-06 18:18:46,288 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 2.7) internal successors, (27), 10 states have internal predecessors, (27), 8 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Word has length 58 [2022-04-06 18:18:46,288 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:18:46,289 INFO L225 Difference]: With dead ends: 68 [2022-04-06 18:18:46,289 INFO L226 Difference]: Without dead ends: 63 [2022-04-06 18:18:46,289 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 73 GetRequests, 58 SyntacticMatches, 1 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=46, Invalid=194, Unknown=0, NotChecked=0, Total=240 [2022-04-06 18:18:46,289 INFO L913 BasicCegarLoop]: 38 mSDtfsCounter, 2 mSDsluCounter, 214 mSDsCounter, 0 mSdLazyCounter, 182 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 252 SdHoareTripleChecker+Invalid, 182 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 182 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 18:18:46,290 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 252 Invalid, 182 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 182 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 18:18:46,290 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2022-04-06 18:18:46,295 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 63. [2022-04-06 18:18:46,296 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 63 states, 45 states have (on average 1.0444444444444445) internal successors, (47), 45 states have internal predecessors, (47), 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-06 18:18:46,296 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 65 transitions. [2022-04-06 18:18:46,296 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 65 transitions. Word has length 58 [2022-04-06 18:18:46,296 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:18:46,296 INFO L478 AbstractCegarLoop]: Abstraction has 63 states and 65 transitions. [2022-04-06 18:18:46,296 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 2.7) internal successors, (27), 10 states have internal predecessors, (27), 8 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-06 18:18:46,297 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 65 transitions. [2022-04-06 18:18:46,297 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2022-04-06 18:18:46,297 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:18:46,297 INFO L499 BasicCegarLoop]: trace histogram [7, 7, 6, 6, 6, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:18:46,306 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-06 18:18:46,505 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-06 18:18:46,506 INFO L403 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:18:46,506 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:18:46,506 INFO L85 PathProgramCache]: Analyzing trace with hash 1633541723, now seen corresponding path program 11 times [2022-04-06 18:18:46,506 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:46,506 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1855029631] [2022-04-06 18:18:46,509 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-04-06 18:18:46,509 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-04-06 18:18:46,509 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-06 18:18:46,509 INFO L85 PathProgramCache]: Analyzing trace with hash 1633541723, now seen corresponding path program 12 times [2022-04-06 18:18:46,509 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:18:46,509 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1730423256] [2022-04-06 18:18:46,509 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:18:46,509 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:18:46,515 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:18:46,515 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [439181398] [2022-04-06 18:18:46,515 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-04-06 18:18:46,516 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:46,516 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:18:46,517 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-06 18:18:46,518 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-06 18:18:46,605 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2022-04-06 18:18:46,606 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:18:46,607 INFO L263 TraceCheckSpWp]: Trace formula consists of 197 conjuncts, 17 conjunts are in the unsatisfiable core [2022-04-06 18:18:46,608 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:18:46,743 INFO L134 CoverageAnalysis]: Checked inductivity of 144 backedges. 12 proven. 132 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-06 18:18:46,743 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 18:18:46,888 INFO L134 CoverageAnalysis]: Checked inductivity of 144 backedges. 12 proven. 72 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2022-04-06 18:18:46,888 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:18:46,888 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1730423256] [2022-04-06 18:18:46,888 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:18:46,888 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [439181398] [2022-04-06 18:18:46,889 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [439181398] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 18:18:46,889 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 18:18:46,889 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 18 [2022-04-06 18:18:46,889 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:18:46,889 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1855029631] [2022-04-06 18:18:46,889 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1855029631] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:18:46,889 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:18:46,889 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [] total 10 [2022-04-06 18:18:46,889 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [21674744] [2022-04-06 18:18:46,889 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:18:46,889 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-04-06 18:18:46,889 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:46,890 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-04-06 18:18:46,890 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=125, Invalid=181, Unknown=0, NotChecked=0, Total=306 [2022-04-06 18:18:46,890 INFO L87 Difference]: Start difference. First operand 63 states and 65 transitions. Second operand has 10 states, 10 states have (on average 4.4) internal successors, (44), 9 states have internal predecessors, (44), 9 states have call successors, (9), 9 states have call predecessors, (9), 7 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-06 18:18:46,960 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:18:46,960 INFO L93 Difference]: Finished difference Result 74 states and 75 transitions. [2022-04-06 18:18:46,961 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2022-04-06 18:18:46,961 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 4.4) internal successors, (44), 9 states have internal predecessors, (44), 9 states have call successors, (9), 9 states have call predecessors, (9), 7 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Word has length 60 [2022-04-06 18:18:46,961 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:18:46,961 INFO L225 Difference]: With dead ends: 74 [2022-04-06 18:18:46,961 INFO L226 Difference]: Without dead ends: 69 [2022-04-06 18:18:46,962 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 125 GetRequests, 103 SyntacticMatches, 0 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 34 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=227, Invalid=325, Unknown=0, NotChecked=0, Total=552 [2022-04-06 18:18:46,962 INFO L913 BasicCegarLoop]: 23 mSDtfsCounter, 10 mSDsluCounter, 58 mSDsCounter, 0 mSdLazyCounter, 34 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 81 SdHoareTripleChecker+Invalid, 49 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 34 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 18:18:46,962 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [10 Valid, 81 Invalid, 49 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 34 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 18:18:46,963 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 69 states. [2022-04-06 18:18:46,967 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 69 to 69. [2022-04-06 18:18:46,967 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 69 states, 50 states have (on average 1.04) internal successors, (52), 50 states have internal predecessors, (52), 10 states have call successors, (10), 10 states have call predecessors, (10), 8 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-06 18:18:46,967 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 69 states to 69 states and 70 transitions. [2022-04-06 18:18:46,967 INFO L78 Accepts]: Start accepts. Automaton has 69 states and 70 transitions. Word has length 60 [2022-04-06 18:18:46,968 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:18:46,968 INFO L478 AbstractCegarLoop]: Abstraction has 69 states and 70 transitions. [2022-04-06 18:18:46,968 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 4.4) internal successors, (44), 9 states have internal predecessors, (44), 9 states have call successors, (9), 9 states have call predecessors, (9), 7 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-06 18:18:46,968 INFO L276 IsEmpty]: Start isEmpty. Operand 69 states and 70 transitions. [2022-04-06 18:18:46,968 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 67 [2022-04-06 18:18:46,968 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:18:46,968 INFO L499 BasicCegarLoop]: trace histogram [8, 7, 7, 7, 7, 7, 7, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:18:46,980 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-06 18:18:47,180 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-06 18:18:47,181 INFO L403 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:18:47,181 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:18:47,181 INFO L85 PathProgramCache]: Analyzing trace with hash 1180930233, now seen corresponding path program 11 times [2022-04-06 18:18:47,181 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:47,181 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1990715066] [2022-04-06 18:18:47,183 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-04-06 18:18:47,183 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-04-06 18:18:47,183 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-06 18:18:47,183 INFO L85 PathProgramCache]: Analyzing trace with hash 1180930233, now seen corresponding path program 12 times [2022-04-06 18:18:47,183 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:18:47,183 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [280987012] [2022-04-06 18:18:47,183 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:18:47,183 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:18:47,188 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:18:47,188 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2086228336] [2022-04-06 18:18:47,188 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-04-06 18:18:47,188 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:47,188 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:18:47,189 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-06 18:18:47,190 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-06 18:18:47,511 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2022-04-06 18:18:47,511 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:18:47,513 INFO L263 TraceCheckSpWp]: Trace formula consists of 207 conjuncts, 32 conjunts are in the unsatisfiable core [2022-04-06 18:18:47,514 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:18:47,726 INFO L134 CoverageAnalysis]: Checked inductivity of 182 backedges. 14 proven. 84 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2022-04-06 18:18:47,726 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 18:18:47,880 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:18:47,880 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [280987012] [2022-04-06 18:18:47,880 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:18:47,880 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2086228336] [2022-04-06 18:18:47,880 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2086228336] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-06 18:18:47,880 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-06 18:18:47,880 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2022-04-06 18:18:47,881 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:18:47,881 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1990715066] [2022-04-06 18:18:47,881 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1990715066] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:18:47,881 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:18:47,881 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [12] imperfect sequences [] total 12 [2022-04-06 18:18:47,881 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1729155518] [2022-04-06 18:18:47,881 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:18:47,881 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-04-06 18:18:47,881 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:47,881 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-04-06 18:18:47,882 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=39, Invalid=171, Unknown=0, NotChecked=0, Total=210 [2022-04-06 18:18:47,882 INFO L87 Difference]: Start difference. First operand 69 states and 70 transitions. Second operand has 12 states, 11 states have (on average 2.727272727272727) internal successors, (30), 11 states have internal predecessors, (30), 9 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-06 18:18:48,024 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:18:48,024 INFO L93 Difference]: Finished difference Result 76 states and 78 transitions. [2022-04-06 18:18:48,024 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-04-06 18:18:48,024 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 2.727272727272727) internal successors, (30), 11 states have internal predecessors, (30), 9 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) Word has length 66 [2022-04-06 18:18:48,025 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:18:48,025 INFO L225 Difference]: With dead ends: 76 [2022-04-06 18:18:48,025 INFO L226 Difference]: Without dead ends: 71 [2022-04-06 18:18:48,025 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 81 GetRequests, 65 SyntacticMatches, 1 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=49, Invalid=223, Unknown=0, NotChecked=0, Total=272 [2022-04-06 18:18:48,026 INFO L913 BasicCegarLoop]: 42 mSDtfsCounter, 2 mSDsluCounter, 258 mSDsCounter, 0 mSdLazyCounter, 231 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 300 SdHoareTripleChecker+Invalid, 231 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 231 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 18:18:48,026 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 300 Invalid, 231 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 231 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 18:18:48,026 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 71 states. [2022-04-06 18:18:48,031 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 71 to 71. [2022-04-06 18:18:48,031 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 51 states have (on average 1.0392156862745099) internal successors, (53), 51 states have internal predecessors, (53), 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-06 18:18:48,031 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 73 transitions. [2022-04-06 18:18:48,031 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 73 transitions. Word has length 66 [2022-04-06 18:18:48,032 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:18:48,032 INFO L478 AbstractCegarLoop]: Abstraction has 71 states and 73 transitions. [2022-04-06 18:18:48,032 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 2.727272727272727) internal successors, (30), 11 states have internal predecessors, (30), 9 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-06 18:18:48,032 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 73 transitions. [2022-04-06 18:18:48,032 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 69 [2022-04-06 18:18:48,032 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:18:48,032 INFO L499 BasicCegarLoop]: trace histogram [8, 8, 7, 7, 7, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:18:48,039 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2022-04-06 18:18:48,237 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-06 18:18:48,238 INFO L403 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:18:48,238 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:18:48,238 INFO L85 PathProgramCache]: Analyzing trace with hash 1699217054, now seen corresponding path program 13 times [2022-04-06 18:18:48,238 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:48,238 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1775351321] [2022-04-06 18:18:48,240 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-04-06 18:18:48,240 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-04-06 18:18:48,240 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-06 18:18:48,240 INFO L85 PathProgramCache]: Analyzing trace with hash 1699217054, now seen corresponding path program 14 times [2022-04-06 18:18:48,240 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:18:48,240 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1131118633] [2022-04-06 18:18:48,241 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:18:48,241 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:18:48,256 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:18:48,257 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [593075778] [2022-04-06 18:18:48,257 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 18:18:48,258 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:48,258 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:18:48,258 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-06 18:18:48,259 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-06 18:18:48,307 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 18:18:48,307 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:18:48,308 INFO L263 TraceCheckSpWp]: Trace formula consists of 218 conjuncts, 19 conjunts are in the unsatisfiable core [2022-04-06 18:18:48,310 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:18:48,448 INFO L134 CoverageAnalysis]: Checked inductivity of 196 backedges. 14 proven. 182 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-06 18:18:48,449 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 18:18:48,619 INFO L134 CoverageAnalysis]: Checked inductivity of 196 backedges. 14 proven. 98 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2022-04-06 18:18:48,619 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:18:48,620 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1131118633] [2022-04-06 18:18:48,620 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:18:48,620 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [593075778] [2022-04-06 18:18:48,620 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [593075778] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 18:18:48,620 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 18:18:48,620 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 20 [2022-04-06 18:18:48,620 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:18:48,620 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1775351321] [2022-04-06 18:18:48,620 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1775351321] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:18:48,620 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:18:48,620 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [11] imperfect sequences [] total 11 [2022-04-06 18:18:48,620 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1132017730] [2022-04-06 18:18:48,620 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:18:48,621 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2022-04-06 18:18:48,621 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:48,621 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2022-04-06 18:18:48,621 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=158, Invalid=222, Unknown=0, NotChecked=0, Total=380 [2022-04-06 18:18:48,621 INFO L87 Difference]: Start difference. First operand 71 states and 73 transitions. Second operand has 11 states, 11 states have (on average 4.545454545454546) internal successors, (50), 10 states have internal predecessors, (50), 10 states have call successors, (10), 10 states have call predecessors, (10), 8 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-06 18:18:48,714 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:18:48,714 INFO L93 Difference]: Finished difference Result 82 states and 83 transitions. [2022-04-06 18:18:48,714 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2022-04-06 18:18:48,715 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 4.545454545454546) internal successors, (50), 10 states have internal predecessors, (50), 10 states have call successors, (10), 10 states have call predecessors, (10), 8 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) Word has length 68 [2022-04-06 18:18:48,715 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:18:48,715 INFO L225 Difference]: With dead ends: 82 [2022-04-06 18:18:48,715 INFO L226 Difference]: Without dead ends: 77 [2022-04-06 18:18:48,716 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 142 GetRequests, 117 SyntacticMatches, 0 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 43 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=291, Invalid=411, Unknown=0, NotChecked=0, Total=702 [2022-04-06 18:18:48,716 INFO L913 BasicCegarLoop]: 24 mSDtfsCounter, 4 mSDsluCounter, 84 mSDsCounter, 0 mSdLazyCounter, 42 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 108 SdHoareTripleChecker+Invalid, 48 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 42 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 18:18:48,716 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [4 Valid, 108 Invalid, 48 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 42 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 18:18:48,717 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 77 states. [2022-04-06 18:18:48,721 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 77 to 77. [2022-04-06 18:18:48,721 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 77 states, 56 states have (on average 1.0357142857142858) internal successors, (58), 56 states have internal predecessors, (58), 11 states have call successors, (11), 11 states have call predecessors, (11), 9 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-06 18:18:48,722 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 77 states to 77 states and 78 transitions. [2022-04-06 18:18:48,722 INFO L78 Accepts]: Start accepts. Automaton has 77 states and 78 transitions. Word has length 68 [2022-04-06 18:18:48,722 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:18:48,722 INFO L478 AbstractCegarLoop]: Abstraction has 77 states and 78 transitions. [2022-04-06 18:18:48,722 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 4.545454545454546) internal successors, (50), 10 states have internal predecessors, (50), 10 states have call successors, (10), 10 states have call predecessors, (10), 8 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-06 18:18:48,722 INFO L276 IsEmpty]: Start isEmpty. Operand 77 states and 78 transitions. [2022-04-06 18:18:48,723 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2022-04-06 18:18:48,723 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:18:48,723 INFO L499 BasicCegarLoop]: trace histogram [9, 8, 8, 8, 8, 8, 8, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:18:48,741 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-06 18:18:48,942 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-06 18:18:48,942 INFO L403 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:18:48,942 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:18:48,942 INFO L85 PathProgramCache]: Analyzing trace with hash -763940164, now seen corresponding path program 13 times [2022-04-06 18:18:48,942 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:48,943 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1991471927] [2022-04-06 18:18:48,944 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-04-06 18:18:48,944 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-04-06 18:18:48,944 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-06 18:18:48,944 INFO L85 PathProgramCache]: Analyzing trace with hash -763940164, now seen corresponding path program 14 times [2022-04-06 18:18:48,944 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:18:48,945 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1770535745] [2022-04-06 18:18:48,945 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:18:48,945 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:18:48,950 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:18:48,950 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [66218914] [2022-04-06 18:18:48,950 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 18:18:48,950 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:48,951 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:18:48,951 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-06 18:18:48,952 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-06 18:18:49,363 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 18:18:49,363 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:18:49,365 INFO L263 TraceCheckSpWp]: Trace formula consists of 228 conjuncts, 36 conjunts are in the unsatisfiable core [2022-04-06 18:18:49,366 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:18:49,625 INFO L134 CoverageAnalysis]: Checked inductivity of 240 backedges. 16 proven. 112 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2022-04-06 18:18:49,626 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 18:18:49,745 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:18:49,746 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1770535745] [2022-04-06 18:18:49,746 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:18:49,746 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [66218914] [2022-04-06 18:18:49,746 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [66218914] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-06 18:18:49,746 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-06 18:18:49,746 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2022-04-06 18:18:49,746 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:18:49,746 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1991471927] [2022-04-06 18:18:49,746 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1991471927] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:18:49,746 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:18:49,746 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [13] imperfect sequences [] total 13 [2022-04-06 18:18:49,747 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [598976879] [2022-04-06 18:18:49,747 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:18:49,747 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2022-04-06 18:18:49,747 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:49,747 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2022-04-06 18:18:49,747 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=42, Invalid=198, Unknown=0, NotChecked=0, Total=240 [2022-04-06 18:18:49,748 INFO L87 Difference]: Start difference. First operand 77 states and 78 transitions. Second operand has 13 states, 12 states have (on average 2.75) internal successors, (33), 12 states have internal predecessors, (33), 10 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-06 18:18:49,941 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:18:49,941 INFO L93 Difference]: Finished difference Result 84 states and 86 transitions. [2022-04-06 18:18:49,942 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-04-06 18:18:49,942 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 12 states have (on average 2.75) internal successors, (33), 12 states have internal predecessors, (33), 10 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Word has length 74 [2022-04-06 18:18:49,942 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:18:49,943 INFO L225 Difference]: With dead ends: 84 [2022-04-06 18:18:49,943 INFO L226 Difference]: Without dead ends: 79 [2022-04-06 18:18:49,943 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 89 GetRequests, 72 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-06 18:18:49,944 INFO L913 BasicCegarLoop]: 46 mSDtfsCounter, 2 mSDsluCounter, 306 mSDsCounter, 0 mSdLazyCounter, 286 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 352 SdHoareTripleChecker+Invalid, 286 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 286 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-04-06 18:18:49,944 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 352 Invalid, 286 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 286 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-04-06 18:18:49,944 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 79 states. [2022-04-06 18:18:49,951 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 79 to 79. [2022-04-06 18:18:49,951 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 79 states, 57 states have (on average 1.0350877192982457) internal successors, (59), 57 states have internal predecessors, (59), 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-06 18:18:49,951 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 79 states to 79 states and 81 transitions. [2022-04-06 18:18:49,952 INFO L78 Accepts]: Start accepts. Automaton has 79 states and 81 transitions. Word has length 74 [2022-04-06 18:18:49,952 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:18:49,952 INFO L478 AbstractCegarLoop]: Abstraction has 79 states and 81 transitions. [2022-04-06 18:18:49,952 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 12 states have (on average 2.75) internal successors, (33), 12 states have internal predecessors, (33), 10 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-06 18:18:49,952 INFO L276 IsEmpty]: Start isEmpty. Operand 79 states and 81 transitions. [2022-04-06 18:18:49,953 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 77 [2022-04-06 18:18:49,953 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:18:49,953 INFO L499 BasicCegarLoop]: trace histogram [9, 9, 8, 8, 8, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:18:49,959 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-06 18:18:50,155 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-06 18:18:50,156 INFO L403 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:18:50,156 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:18:50,156 INFO L85 PathProgramCache]: Analyzing trace with hash 989539297, now seen corresponding path program 15 times [2022-04-06 18:18:50,156 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:50,156 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [195853666] [2022-04-06 18:18:50,160 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-04-06 18:18:50,160 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-04-06 18:18:50,160 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-06 18:18:50,160 INFO L85 PathProgramCache]: Analyzing trace with hash 989539297, now seen corresponding path program 16 times [2022-04-06 18:18:50,160 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:18:50,160 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1905794701] [2022-04-06 18:18:50,160 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:18:50,160 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:18:50,165 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:18:50,165 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [551477598] [2022-04-06 18:18:50,165 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-04-06 18:18:50,165 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:50,165 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:18:50,169 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-06 18:18:50,169 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-06 18:18:50,711 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-04-06 18:18:50,711 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:18:50,713 INFO L263 TraceCheckSpWp]: Trace formula consists of 239 conjuncts, 21 conjunts are in the unsatisfiable core [2022-04-06 18:18:50,714 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:18:50,864 INFO L134 CoverageAnalysis]: Checked inductivity of 256 backedges. 16 proven. 240 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-06 18:18:50,864 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 18:18:51,067 INFO L134 CoverageAnalysis]: Checked inductivity of 256 backedges. 16 proven. 128 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2022-04-06 18:18:51,068 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:18:51,068 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1905794701] [2022-04-06 18:18:51,068 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:18:51,068 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [551477598] [2022-04-06 18:18:51,068 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [551477598] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 18:18:51,068 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 18:18:51,068 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 22 [2022-04-06 18:18:51,068 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:18:51,068 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [195853666] [2022-04-06 18:18:51,069 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [195853666] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:18:51,069 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:18:51,069 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [12] imperfect sequences [] total 12 [2022-04-06 18:18:51,069 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [639524483] [2022-04-06 18:18:51,069 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:18:51,069 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-04-06 18:18:51,069 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:51,069 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-04-06 18:18:51,070 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=195, Invalid=267, Unknown=0, NotChecked=0, Total=462 [2022-04-06 18:18:51,070 INFO L87 Difference]: Start difference. First operand 79 states and 81 transitions. Second operand has 12 states, 12 states have (on average 4.666666666666667) internal successors, (56), 11 states have internal predecessors, (56), 11 states have call successors, (11), 11 states have call predecessors, (11), 9 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-06 18:18:51,183 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:18:51,184 INFO L93 Difference]: Finished difference Result 90 states and 91 transitions. [2022-04-06 18:18:51,184 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2022-04-06 18:18:51,184 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 4.666666666666667) internal successors, (56), 11 states have internal predecessors, (56), 11 states have call successors, (11), 11 states have call predecessors, (11), 9 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Word has length 76 [2022-04-06 18:18:51,184 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:18:51,185 INFO L225 Difference]: With dead ends: 90 [2022-04-06 18:18:51,185 INFO L226 Difference]: Without dead ends: 85 [2022-04-06 18:18:51,186 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 159 GetRequests, 131 SyntacticMatches, 0 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 53 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=363, Invalid=507, Unknown=0, NotChecked=0, Total=870 [2022-04-06 18:18:51,186 INFO L913 BasicCegarLoop]: 25 mSDtfsCounter, 6 mSDsluCounter, 75 mSDsCounter, 0 mSdLazyCounter, 51 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 100 SdHoareTripleChecker+Invalid, 60 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 51 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 18:18:51,186 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 100 Invalid, 60 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 51 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 18:18:51,186 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 85 states. [2022-04-06 18:18:51,194 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 85 to 85. [2022-04-06 18:18:51,194 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 85 states, 62 states have (on average 1.032258064516129) internal successors, (64), 62 states have internal predecessors, (64), 12 states have call successors, (12), 12 states have call predecessors, (12), 10 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-06 18:18:51,194 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 85 states to 85 states and 86 transitions. [2022-04-06 18:18:51,194 INFO L78 Accepts]: Start accepts. Automaton has 85 states and 86 transitions. Word has length 76 [2022-04-06 18:18:51,195 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:18:51,195 INFO L478 AbstractCegarLoop]: Abstraction has 85 states and 86 transitions. [2022-04-06 18:18:51,195 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 4.666666666666667) internal successors, (56), 11 states have internal predecessors, (56), 11 states have call successors, (11), 11 states have call predecessors, (11), 9 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-06 18:18:51,195 INFO L276 IsEmpty]: Start isEmpty. Operand 85 states and 86 transitions. [2022-04-06 18:18:51,195 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 83 [2022-04-06 18:18:51,195 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:18:51,195 INFO L499 BasicCegarLoop]: trace histogram [10, 9, 9, 9, 9, 9, 9, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:18:51,203 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-06 18:18:51,401 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-06 18:18:51,401 INFO L403 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:18:51,401 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:18:51,401 INFO L85 PathProgramCache]: Analyzing trace with hash -1500110401, now seen corresponding path program 15 times [2022-04-06 18:18:51,402 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:51,402 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1628809318] [2022-04-06 18:18:51,403 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-04-06 18:18:51,403 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-04-06 18:18:51,403 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-06 18:18:51,403 INFO L85 PathProgramCache]: Analyzing trace with hash -1500110401, now seen corresponding path program 16 times [2022-04-06 18:18:51,404 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:18:51,404 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1752298108] [2022-04-06 18:18:51,404 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:18:51,404 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:18:51,408 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:18:51,409 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1882088578] [2022-04-06 18:18:51,409 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-04-06 18:18:51,409 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:51,409 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:18:51,410 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-06 18:18:51,412 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-06 18:18:52,029 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-04-06 18:18:52,030 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:18:52,031 INFO L263 TraceCheckSpWp]: Trace formula consists of 249 conjuncts, 40 conjunts are in the unsatisfiable core [2022-04-06 18:18:52,033 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:18:52,291 INFO L134 CoverageAnalysis]: Checked inductivity of 306 backedges. 18 proven. 144 refuted. 0 times theorem prover too weak. 144 trivial. 0 not checked. [2022-04-06 18:18:52,292 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 18:18:52,452 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:18:52,452 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1752298108] [2022-04-06 18:18:52,452 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:18:52,452 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1882088578] [2022-04-06 18:18:52,453 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1882088578] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-06 18:18:52,453 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-06 18:18:52,453 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14] total 14 [2022-04-06 18:18:52,453 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:18:52,453 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1628809318] [2022-04-06 18:18:52,453 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1628809318] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:18:52,453 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:18:52,453 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [14] imperfect sequences [] total 14 [2022-04-06 18:18:52,453 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1507865708] [2022-04-06 18:18:52,453 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:18:52,453 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2022-04-06 18:18:52,454 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:52,454 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-04-06 18:18:52,454 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=45, Invalid=227, Unknown=0, NotChecked=0, Total=272 [2022-04-06 18:18:52,454 INFO L87 Difference]: Start difference. First operand 85 states and 86 transitions. Second operand has 14 states, 13 states have (on average 2.769230769230769) internal successors, (36), 13 states have internal predecessors, (36), 11 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-06 18:18:52,670 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:18:52,670 INFO L93 Difference]: Finished difference Result 92 states and 94 transitions. [2022-04-06 18:18:52,670 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2022-04-06 18:18:52,670 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 13 states have (on average 2.769230769230769) internal successors, (36), 13 states have internal predecessors, (36), 11 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Word has length 82 [2022-04-06 18:18:52,671 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:18:52,671 INFO L225 Difference]: With dead ends: 92 [2022-04-06 18:18:52,671 INFO L226 Difference]: Without dead ends: 87 [2022-04-06 18:18:52,671 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 97 GetRequests, 79 SyntacticMatches, 1 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=55, Invalid=287, Unknown=0, NotChecked=0, Total=342 [2022-04-06 18:18:52,672 INFO L913 BasicCegarLoop]: 50 mSDtfsCounter, 2 mSDsluCounter, 358 mSDsCounter, 0 mSdLazyCounter, 347 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 408 SdHoareTripleChecker+Invalid, 347 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 347 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-04-06 18:18:52,672 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 408 Invalid, 347 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 347 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-04-06 18:18:52,672 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 87 states. [2022-04-06 18:18:52,677 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 87 to 87. [2022-04-06 18:18:52,678 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 87 states, 63 states have (on average 1.0317460317460319) internal successors, (65), 63 states have internal predecessors, (65), 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-06 18:18:52,678 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 87 states to 87 states and 89 transitions. [2022-04-06 18:18:52,678 INFO L78 Accepts]: Start accepts. Automaton has 87 states and 89 transitions. Word has length 82 [2022-04-06 18:18:52,678 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:18:52,678 INFO L478 AbstractCegarLoop]: Abstraction has 87 states and 89 transitions. [2022-04-06 18:18:52,678 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 13 states have (on average 2.769230769230769) internal successors, (36), 13 states have internal predecessors, (36), 11 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-06 18:18:52,679 INFO L276 IsEmpty]: Start isEmpty. Operand 87 states and 89 transitions. [2022-04-06 18:18:52,679 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 85 [2022-04-06 18:18:52,679 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:18:52,679 INFO L499 BasicCegarLoop]: trace histogram [10, 10, 9, 9, 9, 9, 9, 9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:18:52,686 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-06 18:18:52,884 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-06 18:18:52,884 INFO L403 AbstractCegarLoop]: === Iteration 21 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:18:52,884 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:18:52,885 INFO L85 PathProgramCache]: Analyzing trace with hash -2095421916, now seen corresponding path program 17 times [2022-04-06 18:18:52,885 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:18:52,885 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1119627871] [2022-04-06 18:18:52,886 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-04-06 18:18:52,886 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-04-06 18:18:52,887 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-06 18:18:52,887 INFO L85 PathProgramCache]: Analyzing trace with hash -2095421916, now seen corresponding path program 18 times [2022-04-06 18:18:52,887 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:18:52,887 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [297051064] [2022-04-06 18:18:52,887 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:18:52,887 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:18:52,892 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:18:52,892 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [416936517] [2022-04-06 18:18:52,892 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-04-06 18:18:52,892 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:18:52,893 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:18:52,895 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-06 18:18:52,896 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Waiting until timeout for monitored process