/usr/bin/java -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data --core.log.level.for.class de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN -tc ../../../trunk/examples/toolchains/AutomizerC.xml -s ../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationQvasr_64.epf -i ../../../trunk/examples/svcomp/nla-digbench-scaling/hard-ll_valuebound100.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-34549b5 [2022-04-06 23:00:58,074 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-06 23:00:58,076 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-06 23:00:58,099 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-06 23:00:58,099 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-06 23:00:58,100 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-06 23:00:58,100 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-06 23:00:58,102 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-06 23:00:58,103 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-06 23:00:58,104 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-06 23:00:58,104 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-06 23:00:58,105 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-06 23:00:58,105 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-06 23:00:58,106 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-06 23:00:58,107 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-06 23:00:58,112 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-06 23:00:58,112 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-06 23:00:58,117 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-06 23:00:58,122 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-06 23:00:58,123 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-06 23:00:58,124 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-06 23:00:58,127 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-06 23:00:58,127 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-06 23:00:58,129 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-06 23:00:58,129 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-06 23:00:58,131 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-06 23:00:58,131 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-06 23:00:58,131 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-06 23:00:58,132 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-06 23:00:58,132 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-06 23:00:58,133 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-06 23:00:58,133 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-06 23:00:58,133 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-06 23:00:58,133 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-06 23:00:58,134 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-06 23:00:58,134 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-06 23:00:58,134 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-06 23:00:58,135 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-06 23:00:58,135 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-06 23:00:58,135 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-06 23:00:58,136 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-06 23:00:58,136 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-06 23:00:58,137 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationQvasr_64.epf [2022-04-06 23:00:58,142 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-06 23:00:58,142 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-06 23:00:58,145 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-06 23:00:58,145 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-06 23:00:58,146 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-06 23:00:58,146 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-06 23:00:58,146 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-06 23:00:58,146 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-06 23:00:58,146 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-06 23:00:58,146 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-06 23:00:58,147 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-06 23:00:58,147 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-06 23:00:58,147 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-06 23:00:58,147 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-04-06 23:00:58,147 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-06 23:00:58,147 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-06 23:00:58,147 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-06 23:00:58,147 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_NestedInterpolation [2022-04-06 23:00:58,147 INFO L138 SettingsManager]: * Trace refinement strategy=ACCELERATED_INTERPOLATION [2022-04-06 23:00:58,147 INFO L138 SettingsManager]: * Trace refinement strategy used in Accelerated Interpolation=CAMEL [2022-04-06 23:00:58,148 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-04-06 23:00:58,148 INFO L138 SettingsManager]: * Loop acceleration method that is used by accelerated interpolation=QVASR [2022-04-06 23:00:58,148 INFO L138 SettingsManager]: * Use separate solver for trace checks=false WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.core: Log level for class -> de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN; [2022-04-06 23:00:58,336 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-06 23:00:58,351 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-06 23:00:58,353 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-06 23:00:58,354 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-06 23:00:58,354 INFO L275 PluginConnector]: CDTParser initialized [2022-04-06 23:00:58,355 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/hard-ll_valuebound100.c [2022-04-06 23:00:58,398 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/20213a374/fd85d5350bf44a06be5e9a2eaf2f4404/FLAG0e243e618 [2022-04-06 23:00:58,781 INFO L306 CDTParser]: Found 1 translation units. [2022-04-06 23:00:58,782 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/hard-ll_valuebound100.c [2022-04-06 23:00:58,786 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/20213a374/fd85d5350bf44a06be5e9a2eaf2f4404/FLAG0e243e618 [2022-04-06 23:00:58,798 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/20213a374/fd85d5350bf44a06be5e9a2eaf2f4404 [2022-04-06 23:00:58,800 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-06 23:00:58,801 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-04-06 23:00:58,802 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-06 23:00:58,802 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-06 23:00:58,805 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-06 23:00:58,805 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.04 11:00:58" (1/1) ... [2022-04-06 23:00:58,806 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@a95ebfb and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:00:58, skipping insertion in model container [2022-04-06 23:00:58,806 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.04 11:00:58" (1/1) ... [2022-04-06 23:00:58,811 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-06 23:00:58,821 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-06 23:00:58,956 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/hard-ll_valuebound100.c[538,551] [2022-04-06 23:00:58,975 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-06 23:00:58,982 INFO L203 MainTranslator]: Completed pre-run [2022-04-06 23:00:58,992 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/hard-ll_valuebound100.c[538,551] [2022-04-06 23:00:59,006 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-06 23:00:59,015 INFO L208 MainTranslator]: Completed translation [2022-04-06 23:00:59,015 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:00:59 WrapperNode [2022-04-06 23:00:59,016 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-06 23:00:59,017 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-06 23:00:59,017 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-06 23:00:59,018 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-06 23:00:59,025 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:00:59" (1/1) ... [2022-04-06 23:00:59,025 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:00:59" (1/1) ... [2022-04-06 23:00:59,030 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:00:59" (1/1) ... [2022-04-06 23:00:59,030 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:00:59" (1/1) ... [2022-04-06 23:00:59,038 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:00:59" (1/1) ... [2022-04-06 23:00:59,043 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:00:59" (1/1) ... [2022-04-06 23:00:59,049 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:00:59" (1/1) ... [2022-04-06 23:00:59,056 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-06 23:00:59,057 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-06 23:00:59,057 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-06 23:00:59,057 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-06 23:00:59,057 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:00:59" (1/1) ... [2022-04-06 23:00:59,062 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-06 23:00:59,069 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 23:00:59,080 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2022-04-06 23:00:59,081 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2022-04-06 23:00:59,101 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-06 23:00:59,102 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-06 23:00:59,102 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-06 23:00:59,102 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-06 23:00:59,102 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-06 23:00:59,102 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-06 23:00:59,102 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-06 23:00:59,102 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-06 23:00:59,102 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-06 23:00:59,102 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-06 23:00:59,102 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_uint [2022-04-06 23:00:59,102 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-06 23:00:59,103 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-06 23:00:59,103 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-06 23:00:59,103 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-06 23:00:59,103 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-06 23:00:59,103 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-06 23:00:59,103 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-06 23:00:59,103 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-06 23:00:59,103 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-06 23:00:59,144 INFO L234 CfgBuilder]: Building ICFG [2022-04-06 23:00:59,145 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-06 23:00:59,296 INFO L275 CfgBuilder]: Performing block encoding [2022-04-06 23:00:59,303 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-06 23:00:59,303 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-04-06 23:00:59,305 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.04 11:00:59 BoogieIcfgContainer [2022-04-06 23:00:59,305 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-06 23:00:59,306 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-06 23:00:59,306 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-06 23:00:59,321 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-06 23:00:59,321 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 06.04 11:00:58" (1/3) ... [2022-04-06 23:00:59,322 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@42d8f4fe and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.04 11:00:59, skipping insertion in model container [2022-04-06 23:00:59,322 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:00:59" (2/3) ... [2022-04-06 23:00:59,322 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@42d8f4fe and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.04 11:00:59, skipping insertion in model container [2022-04-06 23:00:59,322 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.04 11:00:59" (3/3) ... [2022-04-06 23:00:59,323 INFO L111 eAbstractionObserver]: Analyzing ICFG hard-ll_valuebound100.c [2022-04-06 23:00:59,342 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:Craig_NestedInterpolation Determinization: PREDICATE_ABSTRACTION [2022-04-06 23:00:59,342 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-06 23:00:59,376 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-06 23:00:59,385 INFO L340 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=Craig_NestedInterpolation, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=All, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP [2022-04-06 23:00:59,385 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-06 23:00:59,396 INFO L276 IsEmpty]: Start isEmpty. Operand has 38 states, 20 states have (on average 1.5) internal successors, (30), 21 states have internal predecessors, (30), 12 states have call successors, (12), 4 states have call predecessors, (12), 4 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-06 23:00:59,405 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2022-04-06 23:00:59,406 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:00:59,406 INFO L499 BasicCegarLoop]: trace histogram [3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:00:59,407 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:00:59,410 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:00:59,411 INFO L85 PathProgramCache]: Analyzing trace with hash -1784424332, now seen corresponding path program 1 times [2022-04-06 23:00:59,416 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:00:59,417 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1152628196] [2022-04-06 23:00:59,426 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 23:00:59,426 INFO L85 PathProgramCache]: Analyzing trace with hash -1784424332, now seen corresponding path program 2 times [2022-04-06 23:00:59,427 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:00:59,428 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1394125540] [2022-04-06 23:00:59,428 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:00:59,429 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:00:59,512 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 23:00:59,576 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-06 23:00:59,583 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 23:00:59,593 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-06 23:00:59,594 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 23:00:59,598 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-04-06 23:00:59,599 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 23:00:59,602 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2022-04-06 23:00:59,603 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 23:00:59,606 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-06 23:00:59,607 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 23:00:59,607 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1394125540] [2022-04-06 23:00:59,607 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1394125540] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:00:59,607 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:00:59,608 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-06 23:00:59,609 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 23:00:59,609 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1152628196] [2022-04-06 23:00:59,609 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1152628196] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:00:59,610 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:00:59,610 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-06 23:00:59,610 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [343415555] [2022-04-06 23:00:59,610 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 23:00:59,613 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-06 23:00:59,613 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 23:00:59,629 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-06 23:00:59,630 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-06 23:00:59,631 INFO L87 Difference]: Start difference. First operand has 38 states, 20 states have (on average 1.5) internal successors, (30), 21 states have internal predecessors, (30), 12 states have call successors, (12), 4 states have call predecessors, (12), 4 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) Second operand has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-06 23:00:59,711 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 23:00:59,711 INFO L93 Difference]: Finished difference Result 69 states and 110 transitions. [2022-04-06 23:00:59,716 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-06 23:00:59,717 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 28 [2022-04-06 23:00:59,717 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 23:00:59,721 INFO L225 Difference]: With dead ends: 69 [2022-04-06 23:00:59,721 INFO L226 Difference]: Without dead ends: 33 [2022-04-06 23:00:59,723 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 12 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-06 23:00:59,725 INFO L913 BasicCegarLoop]: 38 mSDtfsCounter, 21 mSDsluCounter, 3 mSDsCounter, 0 mSdLazyCounter, 12 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 31 SdHoareTripleChecker+Valid, 41 SdHoareTripleChecker+Invalid, 23 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 12 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 23:00:59,725 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [31 Valid, 41 Invalid, 23 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 12 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 23:00:59,736 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2022-04-06 23:00:59,758 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 33. [2022-04-06 23:00:59,759 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 33 states, 17 states have (on average 1.2352941176470589) internal successors, (21), 18 states have internal predecessors, (21), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-06 23:00:59,762 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 43 transitions. [2022-04-06 23:00:59,763 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 43 transitions. Word has length 28 [2022-04-06 23:00:59,763 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 23:00:59,764 INFO L478 AbstractCegarLoop]: Abstraction has 33 states and 43 transitions. [2022-04-06 23:00:59,764 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-06 23:00:59,764 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 43 transitions. [2022-04-06 23:00:59,765 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2022-04-06 23:00:59,765 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:00:59,766 INFO L499 BasicCegarLoop]: trace histogram [3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:00:59,766 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-06 23:00:59,766 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:00:59,767 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:00:59,767 INFO L85 PathProgramCache]: Analyzing trace with hash 1361835634, now seen corresponding path program 1 times [2022-04-06 23:00:59,767 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:00:59,768 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [297233972] [2022-04-06 23:00:59,769 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 23:00:59,769 INFO L85 PathProgramCache]: Analyzing trace with hash 1361835634, now seen corresponding path program 2 times [2022-04-06 23:00:59,770 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:00:59,770 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [284343307] [2022-04-06 23:00:59,771 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:00:59,771 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:00:59,792 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 23:00:59,851 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-06 23:00:59,853 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 23:00:59,860 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-06 23:00:59,864 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 23:00:59,870 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-04-06 23:00:59,871 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 23:00:59,876 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2022-04-06 23:00:59,877 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 23:00:59,880 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-06 23:00:59,880 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 23:00:59,880 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [284343307] [2022-04-06 23:00:59,881 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [284343307] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:00:59,881 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:00:59,881 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-06 23:00:59,881 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 23:00:59,881 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [297233972] [2022-04-06 23:00:59,881 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [297233972] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:00:59,882 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:00:59,882 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-06 23:00:59,882 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [812519961] [2022-04-06 23:00:59,882 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 23:00:59,882 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-06 23:00:59,883 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 23:00:59,883 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-06 23:00:59,883 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-04-06 23:00:59,883 INFO L87 Difference]: Start difference. First operand 33 states and 43 transitions. Second operand has 6 states, 6 states have (on average 2.0) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2022-04-06 23:01:00,053 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 23:01:00,053 INFO L93 Difference]: Finished difference Result 46 states and 60 transitions. [2022-04-06 23:01:00,054 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-04-06 23:01:00,054 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.0) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 28 [2022-04-06 23:01:00,054 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 23:01:00,055 INFO L225 Difference]: With dead ends: 46 [2022-04-06 23:01:00,055 INFO L226 Difference]: Without dead ends: 44 [2022-04-06 23:01:00,056 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2022-04-06 23:01:00,057 INFO L913 BasicCegarLoop]: 31 mSDtfsCounter, 38 mSDsluCounter, 17 mSDsCounter, 0 mSdLazyCounter, 126 mSolverCounterSat, 29 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 44 SdHoareTripleChecker+Valid, 48 SdHoareTripleChecker+Invalid, 155 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 29 IncrementalHoareTripleChecker+Valid, 126 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 23:01:00,058 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [44 Valid, 48 Invalid, 155 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [29 Valid, 126 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 23:01:00,060 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2022-04-06 23:01:00,070 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 37. [2022-04-06 23:01:00,070 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 20 states have (on average 1.2) internal successors, (24), 21 states have internal predecessors, (24), 12 states have call successors, (12), 5 states have call predecessors, (12), 4 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-06 23:01:00,072 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 46 transitions. [2022-04-06 23:01:00,072 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 46 transitions. Word has length 28 [2022-04-06 23:01:00,073 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 23:01:00,073 INFO L478 AbstractCegarLoop]: Abstraction has 37 states and 46 transitions. [2022-04-06 23:01:00,073 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.0) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2022-04-06 23:01:00,073 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 46 transitions. [2022-04-06 23:01:00,074 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2022-04-06 23:01:00,074 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:01:00,074 INFO L499 BasicCegarLoop]: trace histogram [3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:01:00,075 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-04-06 23:01:00,075 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:01:00,075 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:01:00,076 INFO L85 PathProgramCache]: Analyzing trace with hash 1382067636, now seen corresponding path program 1 times [2022-04-06 23:01:00,076 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:01:00,083 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1479242548] [2022-04-06 23:01:00,083 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 23:01:00,083 INFO L85 PathProgramCache]: Analyzing trace with hash 1382067636, now seen corresponding path program 2 times [2022-04-06 23:01:00,084 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:01:00,084 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1219663669] [2022-04-06 23:01:00,084 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:01:00,084 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:01:00,099 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 23:01:00,150 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-06 23:01:00,155 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 23:01:00,168 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-06 23:01:00,169 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 23:01:00,171 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-04-06 23:01:00,172 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 23:01:00,175 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2022-04-06 23:01:00,175 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 23:01:00,178 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2022-04-06 23:01:00,180 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 23:01:00,183 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-06 23:01:00,183 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 23:01:00,183 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1219663669] [2022-04-06 23:01:00,183 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1219663669] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:01:00,183 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:01:00,183 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-06 23:01:00,184 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 23:01:00,184 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1479242548] [2022-04-06 23:01:00,184 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1479242548] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:01:00,184 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:01:00,184 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-06 23:01:00,184 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1303557493] [2022-04-06 23:01:00,184 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 23:01:00,185 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-06 23:01:00,185 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 23:01:00,185 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-06 23:01:00,185 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-04-06 23:01:00,185 INFO L87 Difference]: Start difference. First operand 37 states and 46 transitions. Second operand has 6 states, 6 states have (on average 2.5) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-06 23:01:00,324 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 23:01:00,325 INFO L93 Difference]: Finished difference Result 50 states and 63 transitions. [2022-04-06 23:01:00,325 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-04-06 23:01:00,325 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.5) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 33 [2022-04-06 23:01:00,326 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 23:01:00,327 INFO L225 Difference]: With dead ends: 50 [2022-04-06 23:01:00,327 INFO L226 Difference]: Without dead ends: 48 [2022-04-06 23:01:00,328 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 19 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2022-04-06 23:01:00,330 INFO L913 BasicCegarLoop]: 31 mSDtfsCounter, 33 mSDsluCounter, 17 mSDsCounter, 0 mSdLazyCounter, 132 mSolverCounterSat, 28 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 39 SdHoareTripleChecker+Valid, 48 SdHoareTripleChecker+Invalid, 160 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 28 IncrementalHoareTripleChecker+Valid, 132 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 23:01:00,334 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [39 Valid, 48 Invalid, 160 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [28 Valid, 132 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 23:01:00,335 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2022-04-06 23:01:00,353 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 41. [2022-04-06 23:01:00,353 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 23 states have (on average 1.173913043478261) internal successors, (27), 24 states have internal predecessors, (27), 12 states have call successors, (12), 6 states have call predecessors, (12), 5 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-06 23:01:00,356 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 49 transitions. [2022-04-06 23:01:00,356 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 49 transitions. Word has length 33 [2022-04-06 23:01:00,357 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 23:01:00,357 INFO L478 AbstractCegarLoop]: Abstraction has 41 states and 49 transitions. [2022-04-06 23:01:00,357 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.5) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-06 23:01:00,357 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 49 transitions. [2022-04-06 23:01:00,358 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2022-04-06 23:01:00,358 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:01:00,358 INFO L499 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:01:00,358 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2022-04-06 23:01:00,358 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:01:00,358 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:01:00,358 INFO L85 PathProgramCache]: Analyzing trace with hash -1455208590, now seen corresponding path program 1 times [2022-04-06 23:01:00,359 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:01:00,359 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1707770999] [2022-04-06 23:01:00,359 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 23:01:00,359 INFO L85 PathProgramCache]: Analyzing trace with hash -1455208590, now seen corresponding path program 2 times [2022-04-06 23:01:00,359 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:01:00,359 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1077164158] [2022-04-06 23:01:00,359 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:01:00,360 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:01:00,371 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 23:01:00,371 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1321356381] [2022-04-06 23:01:00,371 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 23:01:00,371 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:01:00,371 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 23:01:00,373 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 23:01:00,374 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2022-04-06 23:01:00,416 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 23:01:00,417 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 23:01:00,432 INFO L263 TraceCheckSpWp]: Trace formula consists of 106 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-06 23:01:00,435 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 23:01:00,543 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2022-04-06 23:01:00,544 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-06 23:01:00,544 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 23:01:00,544 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1077164158] [2022-04-06 23:01:00,544 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 23:01:00,544 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1321356381] [2022-04-06 23:01:00,544 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1321356381] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:01:00,545 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:01:00,545 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 23:01:00,545 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 23:01:00,545 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1707770999] [2022-04-06 23:01:00,545 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1707770999] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:01:00,545 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:01:00,546 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 23:01:00,546 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [915895775] [2022-04-06 23:01:00,546 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 23:01:00,546 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 23:01:00,546 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 23:01:00,546 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 23:01:00,547 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-06 23:01:00,547 INFO L87 Difference]: Start difference. First operand 41 states and 49 transitions. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2022-04-06 23:01:00,599 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 23:01:00,599 INFO L93 Difference]: Finished difference Result 69 states and 89 transitions. [2022-04-06 23:01:00,599 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-06 23:01:00,599 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 38 [2022-04-06 23:01:00,600 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 23:01:00,600 INFO L225 Difference]: With dead ends: 69 [2022-04-06 23:01:00,600 INFO L226 Difference]: Without dead ends: 55 [2022-04-06 23:01:00,601 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 38 GetRequests, 34 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-04-06 23:01:00,601 INFO L913 BasicCegarLoop]: 45 mSDtfsCounter, 8 mSDsluCounter, 100 mSDsCounter, 0 mSdLazyCounter, 50 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 145 SdHoareTripleChecker+Invalid, 53 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 50 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 23:01:00,601 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [12 Valid, 145 Invalid, 53 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 50 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 23:01:00,602 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2022-04-06 23:01:00,608 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 55. [2022-04-06 23:01:00,608 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 55 states, 30 states have (on average 1.1666666666666667) internal successors, (35), 32 states have internal predecessors, (35), 18 states have call successors, (18), 7 states have call predecessors, (18), 6 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2022-04-06 23:01:00,609 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 68 transitions. [2022-04-06 23:01:00,609 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 68 transitions. Word has length 38 [2022-04-06 23:01:00,609 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 23:01:00,609 INFO L478 AbstractCegarLoop]: Abstraction has 55 states and 68 transitions. [2022-04-06 23:01:00,609 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2022-04-06 23:01:00,609 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 68 transitions. [2022-04-06 23:01:00,610 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2022-04-06 23:01:00,610 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:01:00,610 INFO L499 BasicCegarLoop]: trace histogram [4, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:01:00,629 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2022-04-06 23:01:00,826 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:01:00,827 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:01:00,827 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:01:00,827 INFO L85 PathProgramCache]: Analyzing trace with hash -1688067263, now seen corresponding path program 1 times [2022-04-06 23:01:00,827 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:01:00,827 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [962872107] [2022-04-06 23:01:00,828 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 23:01:00,828 INFO L85 PathProgramCache]: Analyzing trace with hash -1688067263, now seen corresponding path program 2 times [2022-04-06 23:01:00,828 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:01:00,828 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1903729378] [2022-04-06 23:01:00,828 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:01:00,828 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:01:00,836 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 23:01:00,836 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [251394804] [2022-04-06 23:01:00,837 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 23:01:00,837 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:01:00,837 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 23:01:00,838 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 23:01:00,839 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2022-04-06 23:01:00,877 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 23:01:00,877 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 23:01:00,878 INFO L263 TraceCheckSpWp]: Trace formula consists of 117 conjuncts, 14 conjunts are in the unsatisfiable core [2022-04-06 23:01:00,881 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 23:01:01,139 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 9 proven. 3 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2022-04-06 23:01:01,139 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 23:01:01,288 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-04-06 23:01:01,288 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 23:01:01,288 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1903729378] [2022-04-06 23:01:01,289 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 23:01:01,289 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [251394804] [2022-04-06 23:01:01,289 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [251394804] provided 1 perfect and 1 imperfect interpolant sequences [2022-04-06 23:01:01,289 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-04-06 23:01:01,289 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [9] total 11 [2022-04-06 23:01:01,289 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 23:01:01,289 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [962872107] [2022-04-06 23:01:01,289 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [962872107] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:01:01,289 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:01:01,290 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-06 23:01:01,290 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2067740643] [2022-04-06 23:01:01,290 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 23:01:01,290 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-06 23:01:01,290 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 23:01:01,290 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-06 23:01:01,290 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=84, Unknown=0, NotChecked=0, Total=110 [2022-04-06 23:01:01,291 INFO L87 Difference]: Start difference. First operand 55 states and 68 transitions. Second operand has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-04-06 23:01:01,345 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 23:01:01,345 INFO L93 Difference]: Finished difference Result 68 states and 85 transitions. [2022-04-06 23:01:01,345 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-06 23:01:01,345 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 45 [2022-04-06 23:01:01,346 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 23:01:01,346 INFO L225 Difference]: With dead ends: 68 [2022-04-06 23:01:01,346 INFO L226 Difference]: Without dead ends: 66 [2022-04-06 23:01:01,347 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 90 GetRequests, 79 SyntacticMatches, 1 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2022-04-06 23:01:01,347 INFO L913 BasicCegarLoop]: 42 mSDtfsCounter, 12 mSDsluCounter, 109 mSDsCounter, 0 mSdLazyCounter, 68 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 151 SdHoareTripleChecker+Invalid, 69 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 68 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 23:01:01,347 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [18 Valid, 151 Invalid, 69 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 68 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 23:01:01,348 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 66 states. [2022-04-06 23:01:01,356 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 66 to 64. [2022-04-06 23:01:01,356 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 64 states, 36 states have (on average 1.1944444444444444) internal successors, (43), 38 states have internal predecessors, (43), 20 states have call successors, (20), 8 states have call predecessors, (20), 7 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2022-04-06 23:01:01,357 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 80 transitions. [2022-04-06 23:01:01,357 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 80 transitions. Word has length 45 [2022-04-06 23:01:01,357 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 23:01:01,358 INFO L478 AbstractCegarLoop]: Abstraction has 64 states and 80 transitions. [2022-04-06 23:01:01,358 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-04-06 23:01:01,358 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 80 transitions. [2022-04-06 23:01:01,358 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2022-04-06 23:01:01,358 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:01:01,359 INFO L499 BasicCegarLoop]: trace histogram [6, 5, 5, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:01:01,381 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 23:01:01,579 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:01:01,580 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:01:01,580 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:01:01,580 INFO L85 PathProgramCache]: Analyzing trace with hash -1471734606, now seen corresponding path program 1 times [2022-04-06 23:01:01,580 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:01:01,580 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1187855036] [2022-04-06 23:01:01,580 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 23:01:01,581 INFO L85 PathProgramCache]: Analyzing trace with hash -1471734606, now seen corresponding path program 2 times [2022-04-06 23:01:01,581 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:01:01,581 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [155078387] [2022-04-06 23:01:01,581 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:01:01,581 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:01:01,589 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 23:01:01,589 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [444059478] [2022-04-06 23:01:01,589 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 23:01:01,589 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:01:01,589 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 23:01:01,590 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 23:01:01,627 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2022-04-06 23:01:01,636 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 23:01:01,636 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 23:01:01,636 INFO L263 TraceCheckSpWp]: Trace formula consists of 139 conjuncts, 18 conjunts are in the unsatisfiable core [2022-04-06 23:01:01,638 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 23:01:01,819 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 16 proven. 4 refuted. 0 times theorem prover too weak. 46 trivial. 0 not checked. [2022-04-06 23:01:01,819 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 23:01:01,959 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 56 trivial. 0 not checked. [2022-04-06 23:01:01,960 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 23:01:01,960 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [155078387] [2022-04-06 23:01:01,960 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 23:01:01,960 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [444059478] [2022-04-06 23:01:01,960 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [444059478] provided 1 perfect and 1 imperfect interpolant sequences [2022-04-06 23:01:01,960 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-04-06 23:01:01,960 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [9] total 10 [2022-04-06 23:01:01,960 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 23:01:01,960 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1187855036] [2022-04-06 23:01:01,961 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1187855036] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:01:01,961 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:01:01,961 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 23:01:01,961 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [762135511] [2022-04-06 23:01:01,961 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 23:01:01,961 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 23:01:01,961 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 23:01:01,961 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 23:01:01,961 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2022-04-06 23:01:01,962 INFO L87 Difference]: Start difference. First operand 64 states and 80 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-04-06 23:01:02,053 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 23:01:02,053 INFO L93 Difference]: Finished difference Result 76 states and 95 transitions. [2022-04-06 23:01:02,053 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-06 23:01:02,053 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 55 [2022-04-06 23:01:02,054 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 23:01:02,054 INFO L225 Difference]: With dead ends: 76 [2022-04-06 23:01:02,054 INFO L226 Difference]: Without dead ends: 74 [2022-04-06 23:01:02,055 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 110 GetRequests, 99 SyntacticMatches, 2 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2022-04-06 23:01:02,055 INFO L913 BasicCegarLoop]: 41 mSDtfsCounter, 8 mSDsluCounter, 88 mSDsCounter, 0 mSdLazyCounter, 50 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 129 SdHoareTripleChecker+Invalid, 51 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 50 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 23:01:02,055 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 129 Invalid, 51 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 50 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 23:01:02,056 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 74 states. [2022-04-06 23:01:02,064 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 74 to 71. [2022-04-06 23:01:02,064 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 40 states have (on average 1.175) internal successors, (47), 43 states have internal predecessors, (47), 22 states have call successors, (22), 9 states have call predecessors, (22), 8 states have return successors, (19), 18 states have call predecessors, (19), 19 states have call successors, (19) [2022-04-06 23:01:02,065 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 88 transitions. [2022-04-06 23:01:02,065 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 88 transitions. Word has length 55 [2022-04-06 23:01:02,065 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 23:01:02,065 INFO L478 AbstractCegarLoop]: Abstraction has 71 states and 88 transitions. [2022-04-06 23:01:02,065 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-04-06 23:01:02,065 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 88 transitions. [2022-04-06 23:01:02,066 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2022-04-06 23:01:02,066 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:01:02,066 INFO L499 BasicCegarLoop]: trace histogram [6, 5, 5, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:01:02,085 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 23:01:02,282 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:01:02,283 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:01:02,283 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:01:02,283 INFO L85 PathProgramCache]: Analyzing trace with hash -682689219, now seen corresponding path program 1 times [2022-04-06 23:01:02,284 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:01:02,284 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [143829588] [2022-04-06 23:01:02,284 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 23:01:02,284 INFO L85 PathProgramCache]: Analyzing trace with hash -682689219, now seen corresponding path program 2 times [2022-04-06 23:01:02,284 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:01:02,284 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [674177619] [2022-04-06 23:01:02,284 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:01:02,284 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:01:02,291 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 23:01:02,291 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [281803527] [2022-04-06 23:01:02,291 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 23:01:02,292 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:01:02,292 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 23:01:02,292 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 23:01:02,295 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2022-04-06 23:01:02,352 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 23:01:02,352 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 23:01:02,353 INFO L263 TraceCheckSpWp]: Trace formula consists of 137 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-06 23:01:02,354 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 23:01:02,450 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2022-04-06 23:01:02,451 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-06 23:01:02,451 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 23:01:02,451 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [674177619] [2022-04-06 23:01:02,451 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 23:01:02,451 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [281803527] [2022-04-06 23:01:02,451 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [281803527] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:01:02,451 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:01:02,451 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 23:01:02,452 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 23:01:02,452 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [143829588] [2022-04-06 23:01:02,452 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [143829588] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:01:02,452 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:01:02,452 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 23:01:02,452 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1746410517] [2022-04-06 23:01:02,452 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 23:01:02,453 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 23:01:02,453 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 23:01:02,453 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 23:01:02,453 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-06 23:01:02,453 INFO L87 Difference]: Start difference. First operand 71 states and 88 transitions. Second operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2022-04-06 23:01:02,494 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 23:01:02,494 INFO L93 Difference]: Finished difference Result 79 states and 96 transitions. [2022-04-06 23:01:02,494 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-06 23:01:02,494 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) Word has length 56 [2022-04-06 23:01:02,496 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 23:01:02,498 INFO L225 Difference]: With dead ends: 79 [2022-04-06 23:01:02,498 INFO L226 Difference]: Without dead ends: 72 [2022-04-06 23:01:02,498 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 56 GetRequests, 52 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-04-06 23:01:02,498 INFO L913 BasicCegarLoop]: 36 mSDtfsCounter, 8 mSDsluCounter, 87 mSDsCounter, 0 mSdLazyCounter, 49 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 123 SdHoareTripleChecker+Invalid, 52 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 49 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 23:01:02,499 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [9 Valid, 123 Invalid, 52 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 49 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 23:01:02,499 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 72 states. [2022-04-06 23:01:02,506 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 72 to 71. [2022-04-06 23:01:02,506 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 41 states have (on average 1.146341463414634) internal successors, (47), 44 states have internal predecessors, (47), 20 states have call successors, (20), 10 states have call predecessors, (20), 9 states have return successors, (18), 16 states have call predecessors, (18), 18 states have call successors, (18) [2022-04-06 23:01:02,507 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 85 transitions. [2022-04-06 23:01:02,507 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 85 transitions. Word has length 56 [2022-04-06 23:01:02,507 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 23:01:02,507 INFO L478 AbstractCegarLoop]: Abstraction has 71 states and 85 transitions. [2022-04-06 23:01:02,507 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2022-04-06 23:01:02,507 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 85 transitions. [2022-04-06 23:01:02,508 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2022-04-06 23:01:02,508 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:01:02,508 INFO L499 BasicCegarLoop]: trace histogram [9, 8, 8, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:01:02,524 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2022-04-06 23:01:02,724 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:01:02,724 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:01:02,725 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:01:02,725 INFO L85 PathProgramCache]: Analyzing trace with hash 680531353, now seen corresponding path program 1 times [2022-04-06 23:01:02,725 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:01:02,725 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [242595169] [2022-04-06 23:01:02,725 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 23:01:02,725 INFO L85 PathProgramCache]: Analyzing trace with hash 680531353, now seen corresponding path program 2 times [2022-04-06 23:01:02,726 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:01:02,726 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1256170918] [2022-04-06 23:01:02,726 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:01:02,726 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:01:02,733 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 23:01:02,733 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1773390758] [2022-04-06 23:01:02,733 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 23:01:02,733 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:01:02,733 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 23:01:02,734 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 23:01:02,735 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2022-04-06 23:01:02,793 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 23:01:02,793 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 23:01:02,794 INFO L263 TraceCheckSpWp]: Trace formula consists of 179 conjuncts, 25 conjunts are in the unsatisfiable core [2022-04-06 23:01:02,796 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 23:01:03,277 INFO L134 CoverageAnalysis]: Checked inductivity of 147 backedges. 16 proven. 7 refuted. 0 times theorem prover too weak. 124 trivial. 0 not checked. [2022-04-06 23:01:03,278 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 23:01:04,267 INFO L134 CoverageAnalysis]: Checked inductivity of 147 backedges. 16 proven. 7 refuted. 0 times theorem prover too weak. 124 trivial. 0 not checked. [2022-04-06 23:01:04,268 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 23:01:04,268 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1256170918] [2022-04-06 23:01:04,271 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 23:01:04,271 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1773390758] [2022-04-06 23:01:04,271 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1773390758] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 23:01:04,271 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 23:01:04,271 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 14 [2022-04-06 23:01:04,272 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 23:01:04,272 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [242595169] [2022-04-06 23:01:04,272 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [242595169] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:01:04,272 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:01:04,272 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2022-04-06 23:01:04,272 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1034373462] [2022-04-06 23:01:04,272 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 23:01:04,272 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-04-06 23:01:04,272 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 23:01:04,273 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-04-06 23:01:04,273 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=47, Invalid=135, Unknown=0, NotChecked=0, Total=182 [2022-04-06 23:01:04,273 INFO L87 Difference]: Start difference. First operand 71 states and 85 transitions. Second operand has 9 states, 9 states have (on average 2.4444444444444446) internal successors, (22), 8 states have internal predecessors, (22), 5 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2022-04-06 23:01:04,484 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 23:01:04,484 INFO L93 Difference]: Finished difference Result 135 states and 165 transitions. [2022-04-06 23:01:04,484 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-04-06 23:01:04,484 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.4444444444444446) internal successors, (22), 8 states have internal predecessors, (22), 5 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) Word has length 75 [2022-04-06 23:01:04,485 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 23:01:04,486 INFO L225 Difference]: With dead ends: 135 [2022-04-06 23:01:04,486 INFO L226 Difference]: Without dead ends: 108 [2022-04-06 23:01:04,486 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 150 GetRequests, 136 SyntacticMatches, 1 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 36 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=51, Invalid=159, Unknown=0, NotChecked=0, Total=210 [2022-04-06 23:01:04,487 INFO L913 BasicCegarLoop]: 47 mSDtfsCounter, 10 mSDsluCounter, 187 mSDsCounter, 0 mSdLazyCounter, 260 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 234 SdHoareTripleChecker+Invalid, 273 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 260 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-04-06 23:01:04,487 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [13 Valid, 234 Invalid, 273 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 260 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-04-06 23:01:04,487 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 108 states. [2022-04-06 23:01:04,500 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 108 to 106. [2022-04-06 23:01:04,501 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 106 states, 64 states have (on average 1.140625) internal successors, (73), 67 states have internal predecessors, (73), 27 states have call successors, (27), 15 states have call predecessors, (27), 14 states have return successors, (25), 23 states have call predecessors, (25), 25 states have call successors, (25) [2022-04-06 23:01:04,501 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 125 transitions. [2022-04-06 23:01:04,501 INFO L78 Accepts]: Start accepts. Automaton has 106 states and 125 transitions. Word has length 75 [2022-04-06 23:01:04,502 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 23:01:04,502 INFO L478 AbstractCegarLoop]: Abstraction has 106 states and 125 transitions. [2022-04-06 23:01:04,502 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.4444444444444446) internal successors, (22), 8 states have internal predecessors, (22), 5 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2022-04-06 23:01:04,502 INFO L276 IsEmpty]: Start isEmpty. Operand 106 states and 125 transitions. [2022-04-06 23:01:04,502 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 81 [2022-04-06 23:01:04,503 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:01:04,503 INFO L499 BasicCegarLoop]: trace histogram [10, 9, 9, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:01:04,523 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2022-04-06 23:01:04,720 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:01:04,721 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:01:04,721 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:01:04,721 INFO L85 PathProgramCache]: Analyzing trace with hash -1566820819, now seen corresponding path program 3 times [2022-04-06 23:01:04,721 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:01:04,721 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1072174887] [2022-04-06 23:01:04,722 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 23:01:04,722 INFO L85 PathProgramCache]: Analyzing trace with hash -1566820819, now seen corresponding path program 4 times [2022-04-06 23:01:04,722 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:01:04,722 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2037531255] [2022-04-06 23:01:04,722 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:01:04,722 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:01:04,735 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 23:01:04,735 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1510941543] [2022-04-06 23:01:04,735 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-04-06 23:01:04,736 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:01:04,736 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 23:01:04,736 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 23:01:04,738 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2022-04-06 23:01:04,776 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-04-06 23:01:04,776 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 23:01:04,777 INFO L263 TraceCheckSpWp]: Trace formula consists of 188 conjuncts, 17 conjunts are in the unsatisfiable core [2022-04-06 23:01:04,779 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 23:01:04,989 INFO L134 CoverageAnalysis]: Checked inductivity of 182 backedges. 18 proven. 8 refuted. 0 times theorem prover too weak. 156 trivial. 0 not checked. [2022-04-06 23:01:04,989 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 23:01:06,593 INFO L134 CoverageAnalysis]: Checked inductivity of 182 backedges. 18 proven. 8 refuted. 0 times theorem prover too weak. 156 trivial. 0 not checked. [2022-04-06 23:01:06,594 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 23:01:06,594 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2037531255] [2022-04-06 23:01:06,594 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 23:01:06,594 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1510941543] [2022-04-06 23:01:06,594 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1510941543] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 23:01:06,594 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 23:01:06,594 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 12 [2022-04-06 23:01:06,595 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 23:01:06,595 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1072174887] [2022-04-06 23:01:06,595 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1072174887] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:01:06,595 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:01:06,595 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2022-04-06 23:01:06,595 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [557494415] [2022-04-06 23:01:06,595 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 23:01:06,595 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-04-06 23:01:06,595 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 23:01:06,596 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-04-06 23:01:06,596 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=36, Invalid=96, Unknown=0, NotChecked=0, Total=132 [2022-04-06 23:01:06,596 INFO L87 Difference]: Start difference. First operand 106 states and 125 transitions. Second operand has 8 states, 8 states have (on average 2.75) internal successors, (22), 7 states have internal predecessors, (22), 5 states have call successors, (15), 2 states have call predecessors, (15), 1 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) [2022-04-06 23:01:06,734 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 23:01:06,734 INFO L93 Difference]: Finished difference Result 133 states and 159 transitions. [2022-04-06 23:01:06,735 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-04-06 23:01:06,735 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 2.75) internal successors, (22), 7 states have internal predecessors, (22), 5 states have call successors, (15), 2 states have call predecessors, (15), 1 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) Word has length 80 [2022-04-06 23:01:06,735 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 23:01:06,736 INFO L225 Difference]: With dead ends: 133 [2022-04-06 23:01:06,736 INFO L226 Difference]: Without dead ends: 110 [2022-04-06 23:01:06,737 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 161 GetRequests, 148 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=48, Invalid=134, Unknown=0, NotChecked=0, Total=182 [2022-04-06 23:01:06,737 INFO L913 BasicCegarLoop]: 53 mSDtfsCounter, 11 mSDsluCounter, 169 mSDsCounter, 0 mSdLazyCounter, 147 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 222 SdHoareTripleChecker+Invalid, 158 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 147 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 23:01:06,737 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [13 Valid, 222 Invalid, 158 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 147 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 23:01:06,738 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 110 states. [2022-04-06 23:01:06,750 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 110 to 110. [2022-04-06 23:01:06,751 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 110 states, 66 states have (on average 1.106060606060606) internal successors, (73), 70 states have internal predecessors, (73), 28 states have call successors, (28), 16 states have call predecessors, (28), 15 states have return successors, (25), 23 states have call predecessors, (25), 25 states have call successors, (25) [2022-04-06 23:01:06,751 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 110 states to 110 states and 126 transitions. [2022-04-06 23:01:06,752 INFO L78 Accepts]: Start accepts. Automaton has 110 states and 126 transitions. Word has length 80 [2022-04-06 23:01:06,752 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 23:01:06,752 INFO L478 AbstractCegarLoop]: Abstraction has 110 states and 126 transitions. [2022-04-06 23:01:06,752 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 2.75) internal successors, (22), 7 states have internal predecessors, (22), 5 states have call successors, (15), 2 states have call predecessors, (15), 1 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) [2022-04-06 23:01:06,752 INFO L276 IsEmpty]: Start isEmpty. Operand 110 states and 126 transitions. [2022-04-06 23:01:06,753 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 87 [2022-04-06 23:01:06,753 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:01:06,753 INFO L499 BasicCegarLoop]: trace histogram [11, 10, 10, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:01:06,778 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2022-04-06 23:01:06,970 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:01:06,970 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:01:06,971 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:01:06,971 INFO L85 PathProgramCache]: Analyzing trace with hash -815356955, now seen corresponding path program 1 times [2022-04-06 23:01:06,971 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:01:06,971 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [53447566] [2022-04-06 23:01:06,971 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 23:01:06,971 INFO L85 PathProgramCache]: Analyzing trace with hash -815356955, now seen corresponding path program 2 times [2022-04-06 23:01:06,971 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:01:06,972 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [798178666] [2022-04-06 23:01:06,972 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:01:06,972 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:01:06,978 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 23:01:06,978 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [392195373] [2022-04-06 23:01:06,978 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 23:01:06,978 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:01:06,979 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 23:01:06,979 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 23:01:06,980 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2022-04-06 23:01:07,020 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 23:01:07,020 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 23:01:07,021 INFO L263 TraceCheckSpWp]: Trace formula consists of 199 conjuncts, 31 conjunts are in the unsatisfiable core [2022-04-06 23:01:07,023 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 23:01:07,874 INFO L134 CoverageAnalysis]: Checked inductivity of 221 backedges. 45 proven. 32 refuted. 0 times theorem prover too weak. 144 trivial. 0 not checked. [2022-04-06 23:01:07,874 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 23:01:22,955 INFO L134 CoverageAnalysis]: Checked inductivity of 221 backedges. 45 proven. 32 refuted. 0 times theorem prover too weak. 144 trivial. 0 not checked. [2022-04-06 23:01:22,955 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 23:01:22,955 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [798178666] [2022-04-06 23:01:22,955 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 23:01:22,955 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [392195373] [2022-04-06 23:01:22,955 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [392195373] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 23:01:22,956 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 23:01:22,956 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 23 [2022-04-06 23:01:22,956 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 23:01:22,956 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [53447566] [2022-04-06 23:01:22,956 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [53447566] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:01:22,956 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:01:22,956 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [14] imperfect sequences [] total 14 [2022-04-06 23:01:22,956 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1423469287] [2022-04-06 23:01:22,956 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 23:01:22,956 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2022-04-06 23:01:22,957 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 23:01:22,957 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-04-06 23:01:22,957 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=96, Invalid=410, Unknown=0, NotChecked=0, Total=506 [2022-04-06 23:01:22,957 INFO L87 Difference]: Start difference. First operand 110 states and 126 transitions. Second operand has 14 states, 13 states have (on average 2.0) internal successors, (26), 11 states have internal predecessors, (26), 7 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (14), 6 states have call predecessors, (14), 6 states have call successors, (14) [2022-04-06 23:01:24,293 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 23:01:24,293 INFO L93 Difference]: Finished difference Result 116 states and 131 transitions. [2022-04-06 23:01:24,293 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-04-06 23:01:24,293 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 13 states have (on average 2.0) internal successors, (26), 11 states have internal predecessors, (26), 7 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (14), 6 states have call predecessors, (14), 6 states have call successors, (14) Word has length 86 [2022-04-06 23:01:24,294 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 23:01:24,294 INFO L225 Difference]: With dead ends: 116 [2022-04-06 23:01:24,294 INFO L226 Difference]: Without dead ends: 88 [2022-04-06 23:01:24,295 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 175 GetRequests, 149 SyntacticMatches, 1 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 109 ImplicationChecksByTransitivity, 6.8s TimeCoverageRelationStatistics Valid=135, Invalid=567, Unknown=0, NotChecked=0, Total=702 [2022-04-06 23:01:24,295 INFO L913 BasicCegarLoop]: 36 mSDtfsCounter, 17 mSDsluCounter, 194 mSDsCounter, 0 mSdLazyCounter, 416 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 230 SdHoareTripleChecker+Invalid, 431 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 416 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2022-04-06 23:01:24,295 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [19 Valid, 230 Invalid, 431 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 416 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2022-04-06 23:01:24,296 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 88 states. [2022-04-06 23:01:24,302 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 88 to 88. [2022-04-06 23:01:24,302 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 88 states, 52 states have (on average 1.1153846153846154) internal successors, (58), 55 states have internal predecessors, (58), 23 states have call successors, (23), 13 states have call predecessors, (23), 12 states have return successors, (21), 19 states have call predecessors, (21), 21 states have call successors, (21) [2022-04-06 23:01:24,302 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 88 states to 88 states and 102 transitions. [2022-04-06 23:01:24,303 INFO L78 Accepts]: Start accepts. Automaton has 88 states and 102 transitions. Word has length 86 [2022-04-06 23:01:24,303 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 23:01:24,303 INFO L478 AbstractCegarLoop]: Abstraction has 88 states and 102 transitions. [2022-04-06 23:01:24,303 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 13 states have (on average 2.0) internal successors, (26), 11 states have internal predecessors, (26), 7 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (14), 6 states have call predecessors, (14), 6 states have call successors, (14) [2022-04-06 23:01:24,303 INFO L276 IsEmpty]: Start isEmpty. Operand 88 states and 102 transitions. [2022-04-06 23:01:24,304 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 93 [2022-04-06 23:01:24,304 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:01:24,304 INFO L499 BasicCegarLoop]: trace histogram [12, 11, 11, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:01:24,322 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2022-04-06 23:01:24,512 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:01:24,513 INFO L403 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:01:24,513 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:01:24,513 INFO L85 PathProgramCache]: Analyzing trace with hash 1885636697, now seen corresponding path program 5 times [2022-04-06 23:01:24,513 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:01:24,513 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1957658457] [2022-04-06 23:01:24,514 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 23:01:24,514 INFO L85 PathProgramCache]: Analyzing trace with hash 1885636697, now seen corresponding path program 6 times [2022-04-06 23:01:24,514 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:01:24,514 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [617999614] [2022-04-06 23:01:24,514 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:01:24,514 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:01:24,520 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 23:01:24,520 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [578300050] [2022-04-06 23:01:24,520 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-04-06 23:01:24,520 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:01:24,520 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 23:01:24,521 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 23:01:24,522 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2022-04-06 23:01:24,566 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2022-04-06 23:01:24,567 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 23:01:24,567 INFO L263 TraceCheckSpWp]: Trace formula consists of 139 conjuncts, 26 conjunts are in the unsatisfiable core [2022-04-06 23:01:24,569 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 23:01:37,269 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-04-06 23:01:37,943 INFO L134 CoverageAnalysis]: Checked inductivity of 271 backedges. 55 proven. 9 refuted. 0 times theorem prover too weak. 207 trivial. 0 not checked. [2022-04-06 23:01:37,944 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 23:02:26,956 WARN L232 SmtUtils]: Spent 28.81s on a formula simplification that was a NOOP. DAG size: 51 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-06 23:03:29,751 INFO L134 CoverageAnalysis]: Checked inductivity of 271 backedges. 45 proven. 19 refuted. 0 times theorem prover too weak. 207 trivial. 0 not checked. [2022-04-06 23:03:29,751 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 23:03:29,751 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [617999614] [2022-04-06 23:03:29,752 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 23:03:29,752 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [578300050] [2022-04-06 23:03:29,752 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [578300050] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 23:03:29,752 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 23:03:29,752 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 10] total 15 [2022-04-06 23:03:29,752 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 23:03:29,752 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1957658457] [2022-04-06 23:03:29,752 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1957658457] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:03:29,752 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:03:29,752 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [11] imperfect sequences [] total 11 [2022-04-06 23:03:29,752 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1599611357] [2022-04-06 23:03:29,752 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 23:03:29,753 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2022-04-06 23:03:29,753 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 23:03:29,753 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2022-04-06 23:03:29,753 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=46, Invalid=163, Unknown=1, NotChecked=0, Total=210 [2022-04-06 23:03:29,753 INFO L87 Difference]: Start difference. First operand 88 states and 102 transitions. Second operand has 11 states, 11 states have (on average 2.3636363636363638) internal successors, (26), 10 states have internal predecessors, (26), 5 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2022-04-06 23:03:33,997 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 23:03:33,997 INFO L93 Difference]: Finished difference Result 112 states and 130 transitions. [2022-04-06 23:03:33,997 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-04-06 23:03:33,997 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 2.3636363636363638) internal successors, (26), 10 states have internal predecessors, (26), 5 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) Word has length 92 [2022-04-06 23:03:33,998 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 23:03:33,998 INFO L225 Difference]: With dead ends: 112 [2022-04-06 23:03:33,998 INFO L226 Difference]: Without dead ends: 100 [2022-04-06 23:03:33,999 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 185 GetRequests, 167 SyntacticMatches, 3 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 76 ImplicationChecksByTransitivity, 38.2s TimeCoverageRelationStatistics Valid=59, Invalid=211, Unknown=2, NotChecked=0, Total=272 [2022-04-06 23:03:33,999 INFO L913 BasicCegarLoop]: 35 mSDtfsCounter, 25 mSDsluCounter, 156 mSDsCounter, 0 mSdLazyCounter, 278 mSolverCounterSat, 24 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 37 SdHoareTripleChecker+Valid, 191 SdHoareTripleChecker+Invalid, 302 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 24 IncrementalHoareTripleChecker+Valid, 278 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2022-04-06 23:03:33,999 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [37 Valid, 191 Invalid, 302 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [24 Valid, 278 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2022-04-06 23:03:33,999 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 100 states. [2022-04-06 23:03:34,007 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 100 to 99. [2022-04-06 23:03:34,008 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 99 states, 59 states have (on average 1.11864406779661) internal successors, (66), 63 states have internal predecessors, (66), 26 states have call successors, (26), 14 states have call predecessors, (26), 13 states have return successors, (24), 21 states have call predecessors, (24), 24 states have call successors, (24) [2022-04-06 23:03:34,008 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 99 states to 99 states and 116 transitions. [2022-04-06 23:03:34,008 INFO L78 Accepts]: Start accepts. Automaton has 99 states and 116 transitions. Word has length 92 [2022-04-06 23:03:34,008 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 23:03:34,009 INFO L478 AbstractCegarLoop]: Abstraction has 99 states and 116 transitions. [2022-04-06 23:03:34,009 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 2.3636363636363638) internal successors, (26), 10 states have internal predecessors, (26), 5 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2022-04-06 23:03:34,009 INFO L276 IsEmpty]: Start isEmpty. Operand 99 states and 116 transitions. [2022-04-06 23:03:34,009 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 98 [2022-04-06 23:03:34,009 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:03:34,009 INFO L499 BasicCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:03:34,027 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2022-04-06 23:03:34,223 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,SelfDestructingSolverStorable10 [2022-04-06 23:03:34,223 INFO L403 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:03:34,224 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:03:34,224 INFO L85 PathProgramCache]: Analyzing trace with hash -278824083, now seen corresponding path program 7 times [2022-04-06 23:03:34,224 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:03:34,224 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1307112236] [2022-04-06 23:03:34,225 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 23:03:34,225 INFO L85 PathProgramCache]: Analyzing trace with hash -278824083, now seen corresponding path program 8 times [2022-04-06 23:03:34,225 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:03:34,226 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [203131358] [2022-04-06 23:03:34,226 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:03:34,226 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:03:34,241 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 23:03:34,241 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1902767076] [2022-04-06 23:03:34,241 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 23:03:34,241 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:03:34,242 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 23:03:34,242 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 23:03:34,243 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2022-04-06 23:03:34,316 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 23:03:34,316 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 23:03:34,317 INFO L263 TraceCheckSpWp]: Trace formula consists of 221 conjuncts, 23 conjunts are in the unsatisfiable core [2022-04-06 23:03:34,321 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 23:03:34,710 INFO L134 CoverageAnalysis]: Checked inductivity of 318 backedges. 24 proven. 18 refuted. 0 times theorem prover too weak. 276 trivial. 0 not checked. [2022-04-06 23:03:34,710 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 23:03:36,384 INFO L134 CoverageAnalysis]: Checked inductivity of 318 backedges. 24 proven. 18 refuted. 0 times theorem prover too weak. 276 trivial. 0 not checked. [2022-04-06 23:03:36,384 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 23:03:36,384 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [203131358] [2022-04-06 23:03:36,385 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 23:03:36,385 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1902767076] [2022-04-06 23:03:36,385 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1902767076] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 23:03:36,385 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 23:03:36,385 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 14 [2022-04-06 23:03:36,385 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 23:03:36,385 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1307112236] [2022-04-06 23:03:36,385 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1307112236] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:03:36,385 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:03:36,385 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2022-04-06 23:03:36,385 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1038487027] [2022-04-06 23:03:36,385 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 23:03:36,386 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-04-06 23:03:36,386 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 23:03:36,386 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-04-06 23:03:36,386 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=51, Invalid=131, Unknown=0, NotChecked=0, Total=182 [2022-04-06 23:03:36,386 INFO L87 Difference]: Start difference. First operand 99 states and 116 transitions. Second operand has 9 states, 9 states have (on average 2.6666666666666665) internal successors, (24), 8 states have internal predecessors, (24), 6 states have call successors, (18), 2 states have call predecessors, (18), 1 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) [2022-04-06 23:03:36,685 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 23:03:36,685 INFO L93 Difference]: Finished difference Result 177 states and 223 transitions. [2022-04-06 23:03:36,685 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-04-06 23:03:36,685 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.6666666666666665) internal successors, (24), 8 states have internal predecessors, (24), 6 states have call successors, (18), 2 states have call predecessors, (18), 1 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) Word has length 97 [2022-04-06 23:03:36,685 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 23:03:36,686 INFO L225 Difference]: With dead ends: 177 [2022-04-06 23:03:36,686 INFO L226 Difference]: Without dead ends: 138 [2022-04-06 23:03:36,689 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 196 GetRequests, 180 SyntacticMatches, 1 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=73, Invalid=199, Unknown=0, NotChecked=0, Total=272 [2022-04-06 23:03:36,689 INFO L913 BasicCegarLoop]: 62 mSDtfsCounter, 13 mSDsluCounter, 244 mSDsCounter, 0 mSdLazyCounter, 292 mSolverCounterSat, 17 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 306 SdHoareTripleChecker+Invalid, 309 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 17 IncrementalHoareTripleChecker+Valid, 292 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-04-06 23:03:36,690 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [16 Valid, 306 Invalid, 309 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [17 Valid, 292 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-04-06 23:03:36,690 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 138 states. [2022-04-06 23:03:36,705 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 138 to 138. [2022-04-06 23:03:36,706 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 138 states, 82 states have (on average 1.1219512195121952) internal successors, (92), 88 states have internal predecessors, (92), 39 states have call successors, (39), 17 states have call predecessors, (39), 16 states have return successors, (36), 32 states have call predecessors, (36), 36 states have call successors, (36) [2022-04-06 23:03:36,707 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 138 states to 138 states and 167 transitions. [2022-04-06 23:03:36,707 INFO L78 Accepts]: Start accepts. Automaton has 138 states and 167 transitions. Word has length 97 [2022-04-06 23:03:36,708 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 23:03:36,708 INFO L478 AbstractCegarLoop]: Abstraction has 138 states and 167 transitions. [2022-04-06 23:03:36,708 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.6666666666666665) internal successors, (24), 8 states have internal predecessors, (24), 6 states have call successors, (18), 2 states have call predecessors, (18), 1 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) [2022-04-06 23:03:36,708 INFO L276 IsEmpty]: Start isEmpty. Operand 138 states and 167 transitions. [2022-04-06 23:03:36,709 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 106 [2022-04-06 23:03:36,709 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:03:36,709 INFO L499 BasicCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:03:36,728 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2022-04-06 23:03:36,925 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:03:36,925 INFO L403 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:03:36,926 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:03:36,926 INFO L85 PathProgramCache]: Analyzing trace with hash -367001023, now seen corresponding path program 9 times [2022-04-06 23:03:36,926 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:03:36,926 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [770522753] [2022-04-06 23:03:36,926 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 23:03:36,926 INFO L85 PathProgramCache]: Analyzing trace with hash -367001023, now seen corresponding path program 10 times [2022-04-06 23:03:36,926 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:03:36,926 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [824905027] [2022-04-06 23:03:36,926 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:03:36,927 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:03:36,932 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 23:03:36,932 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1450876183] [2022-04-06 23:03:36,933 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-04-06 23:03:36,933 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:03:36,933 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 23:03:36,935 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 23:03:36,937 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2022-04-06 23:03:36,973 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-04-06 23:03:36,973 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 23:03:36,974 INFO L263 TraceCheckSpWp]: Trace formula consists of 241 conjuncts, 42 conjunts are in the unsatisfiable core [2022-04-06 23:03:36,976 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 23:03:38,394 INFO L134 CoverageAnalysis]: Checked inductivity of 374 backedges. 58 proven. 28 refuted. 0 times theorem prover too weak. 288 trivial. 0 not checked. [2022-04-06 23:03:38,394 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 23:03:53,897 WARN L232 SmtUtils]: Spent 5.79s on a formula simplification that was a NOOP. DAG size: 142 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-06 23:04:25,275 INFO L134 CoverageAnalysis]: Checked inductivity of 374 backedges. 58 proven. 28 refuted. 0 times theorem prover too weak. 288 trivial. 0 not checked. [2022-04-06 23:04:25,275 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 23:04:25,275 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [824905027] [2022-04-06 23:04:25,275 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 23:04:25,275 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1450876183] [2022-04-06 23:04:25,275 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1450876183] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 23:04:25,276 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 23:04:25,276 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15] total 25 [2022-04-06 23:04:25,276 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 23:04:25,276 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [770522753] [2022-04-06 23:04:25,276 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [770522753] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:04:25,276 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:04:25,276 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [15] imperfect sequences [] total 15 [2022-04-06 23:04:25,276 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [52804697] [2022-04-06 23:04:25,276 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 23:04:25,276 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2022-04-06 23:04:25,276 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 23:04:25,277 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2022-04-06 23:04:25,277 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=106, Invalid=494, Unknown=0, NotChecked=0, Total=600 [2022-04-06 23:04:25,277 INFO L87 Difference]: Start difference. First operand 138 states and 167 transitions. Second operand has 15 states, 15 states have (on average 2.0) internal successors, (30), 13 states have internal predecessors, (30), 8 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (17), 6 states have call predecessors, (17), 7 states have call successors, (17) [2022-04-06 23:04:27,348 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 23:04:27,348 INFO L93 Difference]: Finished difference Result 184 states and 208 transitions. [2022-04-06 23:04:27,349 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2022-04-06 23:04:27,349 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.0) internal successors, (30), 13 states have internal predecessors, (30), 8 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (17), 6 states have call predecessors, (17), 7 states have call successors, (17) Word has length 105 [2022-04-06 23:04:27,349 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 23:04:27,350 INFO L225 Difference]: With dead ends: 184 [2022-04-06 23:04:27,350 INFO L226 Difference]: Without dead ends: 147 [2022-04-06 23:04:27,350 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 211 GetRequests, 185 SyntacticMatches, 1 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 124 ImplicationChecksByTransitivity, 15.4s TimeCoverageRelationStatistics Valid=119, Invalid=583, Unknown=0, NotChecked=0, Total=702 [2022-04-06 23:04:27,350 INFO L913 BasicCegarLoop]: 47 mSDtfsCounter, 17 mSDsluCounter, 261 mSDsCounter, 0 mSdLazyCounter, 716 mSolverCounterSat, 17 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 308 SdHoareTripleChecker+Invalid, 733 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 17 IncrementalHoareTripleChecker+Valid, 716 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.5s IncrementalHoareTripleChecker+Time [2022-04-06 23:04:27,351 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [22 Valid, 308 Invalid, 733 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [17 Valid, 716 Invalid, 0 Unknown, 0 Unchecked, 1.5s Time] [2022-04-06 23:04:27,351 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 147 states. [2022-04-06 23:04:27,361 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 147 to 147. [2022-04-06 23:04:27,361 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 147 states, 90 states have (on average 1.0888888888888888) internal successors, (98), 95 states have internal predecessors, (98), 36 states have call successors, (36), 21 states have call predecessors, (36), 20 states have return successors, (33), 30 states have call predecessors, (33), 33 states have call successors, (33) [2022-04-06 23:04:27,362 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 147 states to 147 states and 167 transitions. [2022-04-06 23:04:27,362 INFO L78 Accepts]: Start accepts. Automaton has 147 states and 167 transitions. Word has length 105 [2022-04-06 23:04:27,362 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 23:04:27,362 INFO L478 AbstractCegarLoop]: Abstraction has 147 states and 167 transitions. [2022-04-06 23:04:27,363 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.0) internal successors, (30), 13 states have internal predecessors, (30), 8 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (17), 6 states have call predecessors, (17), 7 states have call successors, (17) [2022-04-06 23:04:27,363 INFO L276 IsEmpty]: Start isEmpty. Operand 147 states and 167 transitions. [2022-04-06 23:04:27,363 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 115 [2022-04-06 23:04:27,363 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:04:27,363 INFO L499 BasicCegarLoop]: trace histogram [16, 15, 15, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:04:27,380 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2022-04-06 23:04:27,571 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,SelfDestructingSolverStorable12 [2022-04-06 23:04:27,574 INFO L403 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:04:27,574 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:04:27,574 INFO L85 PathProgramCache]: Analyzing trace with hash -1683530195, now seen corresponding path program 11 times [2022-04-06 23:04:27,574 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:04:27,575 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [435998650] [2022-04-06 23:04:27,575 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 23:04:27,575 INFO L85 PathProgramCache]: Analyzing trace with hash -1683530195, now seen corresponding path program 12 times [2022-04-06 23:04:27,575 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:04:27,575 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1338333047] [2022-04-06 23:04:27,575 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:04:27,575 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:04:27,591 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 23:04:27,591 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1050608322] [2022-04-06 23:04:27,591 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-04-06 23:04:27,591 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:04:27,592 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 23:04:27,592 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 23:04:27,593 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 23:04:27,657 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 5 check-sat command(s) [2022-04-06 23:04:27,657 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 23:04:27,658 INFO L263 TraceCheckSpWp]: Trace formula consists of 183 conjuncts, 22 conjunts are in the unsatisfiable core [2022-04-06 23:04:27,660 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 23:04:28,047 INFO L134 CoverageAnalysis]: Checked inductivity of 495 backedges. 96 proven. 4 refuted. 0 times theorem prover too weak. 395 trivial. 0 not checked. [2022-04-06 23:04:28,047 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 23:04:28,341 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 23:04:28,342 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1338333047] [2022-04-06 23:04:28,342 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 23:04:28,342 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1050608322] [2022-04-06 23:04:28,342 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1050608322] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-06 23:04:28,342 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-06 23:04:28,342 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2022-04-06 23:04:28,342 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 23:04:28,342 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [435998650] [2022-04-06 23:04:28,342 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [435998650] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:04:28,342 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:04:28,342 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [11] imperfect sequences [] total 11 [2022-04-06 23:04:28,342 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [66738206] [2022-04-06 23:04:28,342 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 23:04:28,343 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2022-04-06 23:04:28,343 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 23:04:28,343 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2022-04-06 23:04:28,343 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=127, Unknown=0, NotChecked=0, Total=156 [2022-04-06 23:04:28,343 INFO L87 Difference]: Start difference. First operand 147 states and 167 transitions. Second operand has 11 states, 10 states have (on average 2.8) internal successors, (28), 9 states have internal predecessors, (28), 6 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (16), 5 states have call predecessors, (16), 5 states have call successors, (16) [2022-04-06 23:04:28,740 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 23:04:28,740 INFO L93 Difference]: Finished difference Result 168 states and 190 transitions. [2022-04-06 23:04:28,740 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-04-06 23:04:28,741 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 2.8) internal successors, (28), 9 states have internal predecessors, (28), 6 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (16), 5 states have call predecessors, (16), 5 states have call successors, (16) Word has length 114 [2022-04-06 23:04:28,741 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 23:04:28,742 INFO L225 Difference]: With dead ends: 168 [2022-04-06 23:04:28,742 INFO L226 Difference]: Without dead ends: 156 [2022-04-06 23:04:28,742 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 121 GetRequests, 105 SyntacticMatches, 2 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 34 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=46, Invalid=194, Unknown=0, NotChecked=0, Total=240 [2022-04-06 23:04:28,742 INFO L913 BasicCegarLoop]: 43 mSDtfsCounter, 20 mSDsluCounter, 164 mSDsCounter, 0 mSdLazyCounter, 273 mSolverCounterSat, 17 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 26 SdHoareTripleChecker+Valid, 207 SdHoareTripleChecker+Invalid, 352 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 17 IncrementalHoareTripleChecker+Valid, 273 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 62 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-04-06 23:04:28,743 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [26 Valid, 207 Invalid, 352 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [17 Valid, 273 Invalid, 0 Unknown, 62 Unchecked, 0.3s Time] [2022-04-06 23:04:28,743 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 156 states. [2022-04-06 23:04:28,755 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 156 to 155. [2022-04-06 23:04:28,755 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 155 states, 95 states have (on average 1.0842105263157895) internal successors, (103), 100 states have internal predecessors, (103), 38 states have call successors, (38), 22 states have call predecessors, (38), 21 states have return successors, (35), 32 states have call predecessors, (35), 35 states have call successors, (35) [2022-04-06 23:04:28,755 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 155 states to 155 states and 176 transitions. [2022-04-06 23:04:28,756 INFO L78 Accepts]: Start accepts. Automaton has 155 states and 176 transitions. Word has length 114 [2022-04-06 23:04:28,756 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 23:04:28,756 INFO L478 AbstractCegarLoop]: Abstraction has 155 states and 176 transitions. [2022-04-06 23:04:28,756 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 2.8) internal successors, (28), 9 states have internal predecessors, (28), 6 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (16), 5 states have call predecessors, (16), 5 states have call successors, (16) [2022-04-06 23:04:28,756 INFO L276 IsEmpty]: Start isEmpty. Operand 155 states and 176 transitions. [2022-04-06 23:04:28,757 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 117 [2022-04-06 23:04:28,757 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:04:28,757 INFO L499 BasicCegarLoop]: trace histogram [16, 15, 15, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:04:28,775 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2022-04-06 23:04:28,972 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,SelfDestructingSolverStorable13 [2022-04-06 23:04:28,973 INFO L403 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:04:28,973 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:04:28,973 INFO L85 PathProgramCache]: Analyzing trace with hash -1619018179, now seen corresponding path program 3 times [2022-04-06 23:04:28,973 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:04:28,973 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [719567333] [2022-04-06 23:04:28,974 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 23:04:28,974 INFO L85 PathProgramCache]: Analyzing trace with hash -1619018179, now seen corresponding path program 4 times [2022-04-06 23:04:28,974 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:04:28,974 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [802980582] [2022-04-06 23:04:28,974 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:04:28,974 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:04:28,987 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 23:04:28,987 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1916786333] [2022-04-06 23:04:28,987 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-04-06 23:04:28,988 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:04:28,988 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 23:04:28,988 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 23:04:28,990 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 23:04:29,041 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-04-06 23:04:29,042 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 23:04:29,043 INFO L263 TraceCheckSpWp]: Trace formula consists of 261 conjuncts, 43 conjunts are in the unsatisfiable core [2022-04-06 23:04:29,045 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 23:04:29,746 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-04-06 23:04:30,615 INFO L134 CoverageAnalysis]: Checked inductivity of 490 backedges. 71 proven. 29 refuted. 0 times theorem prover too weak. 390 trivial. 0 not checked. [2022-04-06 23:04:30,615 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 23:04:30,703 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-04-06 23:04:39,849 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 23:04:39,849 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [802980582] [2022-04-06 23:04:39,849 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 23:04:39,849 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1916786333] [2022-04-06 23:04:39,849 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1916786333] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-06 23:04:39,849 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-06 23:04:39,849 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2022-04-06 23:04:39,849 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 23:04:39,849 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [719567333] [2022-04-06 23:04:39,849 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [719567333] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:04:39,850 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:04:39,850 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [15] imperfect sequences [] total 15 [2022-04-06 23:04:39,850 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [934020174] [2022-04-06 23:04:39,850 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 23:04:39,850 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2022-04-06 23:04:39,850 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 23:04:39,850 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2022-04-06 23:04:39,850 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=153, Invalid=549, Unknown=0, NotChecked=0, Total=702 [2022-04-06 23:04:39,851 INFO L87 Difference]: Start difference. First operand 155 states and 176 transitions. Second operand has 15 states, 14 states have (on average 2.2142857142857144) internal successors, (31), 14 states have internal predecessors, (31), 8 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (19), 7 states have call predecessors, (19), 7 states have call successors, (19) [2022-04-06 23:04:41,786 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 23:04:41,787 INFO L93 Difference]: Finished difference Result 161 states and 181 transitions. [2022-04-06 23:04:41,787 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2022-04-06 23:04:41,787 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 14 states have (on average 2.2142857142857144) internal successors, (31), 14 states have internal predecessors, (31), 8 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (19), 7 states have call predecessors, (19), 7 states have call successors, (19) Word has length 116 [2022-04-06 23:04:41,788 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 23:04:41,788 INFO L225 Difference]: With dead ends: 161 [2022-04-06 23:04:41,789 INFO L226 Difference]: Without dead ends: 124 [2022-04-06 23:04:41,789 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 195 GetRequests, 167 SyntacticMatches, 1 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 1 DeprecatedPredicates, 150 ImplicationChecksByTransitivity, 2.9s TimeCoverageRelationStatistics Valid=167, Invalid=645, Unknown=0, NotChecked=0, Total=812 [2022-04-06 23:04:41,789 INFO L913 BasicCegarLoop]: 44 mSDtfsCounter, 15 mSDsluCounter, 261 mSDsCounter, 0 mSdLazyCounter, 539 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 305 SdHoareTripleChecker+Invalid, 615 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 539 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 62 IncrementalHoareTripleChecker+Unchecked, 1.6s IncrementalHoareTripleChecker+Time [2022-04-06 23:04:41,789 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [15 Valid, 305 Invalid, 615 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 539 Invalid, 0 Unknown, 62 Unchecked, 1.6s Time] [2022-04-06 23:04:41,790 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 124 states. [2022-04-06 23:04:41,798 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 124 to 124. [2022-04-06 23:04:41,799 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 124 states, 75 states have (on average 1.0933333333333333) internal successors, (82), 79 states have internal predecessors, (82), 31 states have call successors, (31), 18 states have call predecessors, (31), 17 states have return successors, (29), 26 states have call predecessors, (29), 29 states have call successors, (29) [2022-04-06 23:04:41,799 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 124 states to 124 states and 142 transitions. [2022-04-06 23:04:41,799 INFO L78 Accepts]: Start accepts. Automaton has 124 states and 142 transitions. Word has length 116 [2022-04-06 23:04:41,799 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 23:04:41,800 INFO L478 AbstractCegarLoop]: Abstraction has 124 states and 142 transitions. [2022-04-06 23:04:41,800 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 14 states have (on average 2.2142857142857144) internal successors, (31), 14 states have internal predecessors, (31), 8 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (19), 7 states have call predecessors, (19), 7 states have call successors, (19) [2022-04-06 23:04:41,800 INFO L276 IsEmpty]: Start isEmpty. Operand 124 states and 142 transitions. [2022-04-06 23:04:41,800 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 121 [2022-04-06 23:04:41,800 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:04:41,800 INFO L499 BasicCegarLoop]: trace histogram [17, 16, 16, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:04:41,820 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 23:04:42,007 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,SelfDestructingSolverStorable14 [2022-04-06 23:04:42,007 INFO L403 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:04:42,008 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:04:42,008 INFO L85 PathProgramCache]: Analyzing trace with hash -1921791003, now seen corresponding path program 5 times [2022-04-06 23:04:42,008 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:04:42,008 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [22739071] [2022-04-06 23:04:42,008 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 23:04:42,008 INFO L85 PathProgramCache]: Analyzing trace with hash -1921791003, now seen corresponding path program 6 times [2022-04-06 23:04:42,008 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:04:42,008 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [472420371] [2022-04-06 23:04:42,008 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:04:42,009 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:04:42,014 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 23:04:42,014 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [64659745] [2022-04-06 23:04:42,015 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-04-06 23:04:42,015 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:04:42,015 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 23:04:42,015 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 23:04:42,016 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 23:04:42,076 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2022-04-06 23:04:42,076 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 23:04:42,077 INFO L263 TraceCheckSpWp]: Trace formula consists of 247 conjuncts, 6 conjunts are in the unsatisfiable core [2022-04-06 23:04:42,079 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 23:04:42,322 INFO L134 CoverageAnalysis]: Checked inductivity of 558 backedges. 62 proven. 4 refuted. 0 times theorem prover too weak. 492 trivial. 0 not checked. [2022-04-06 23:04:42,322 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 23:04:42,531 INFO L134 CoverageAnalysis]: Checked inductivity of 558 backedges. 57 proven. 4 refuted. 0 times theorem prover too weak. 497 trivial. 0 not checked. [2022-04-06 23:04:42,531 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 23:04:42,532 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [472420371] [2022-04-06 23:04:42,532 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 23:04:42,532 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [64659745] [2022-04-06 23:04:42,532 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [64659745] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 23:04:42,532 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 23:04:42,532 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 5] total 6 [2022-04-06 23:04:42,532 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 23:04:42,532 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [22739071] [2022-04-06 23:04:42,532 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [22739071] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:04:42,532 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:04:42,532 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-06 23:04:42,532 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [129053013] [2022-04-06 23:04:42,532 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 23:04:42,533 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-06 23:04:42,533 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 23:04:42,533 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-06 23:04:42,533 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=15, Unknown=0, NotChecked=0, Total=30 [2022-04-06 23:04:42,533 INFO L87 Difference]: Start difference. First operand 124 states and 142 transitions. Second operand has 6 states, 6 states have (on average 4.5) internal successors, (27), 6 states have internal predecessors, (27), 6 states have call successors, (22), 2 states have call predecessors, (22), 1 states have return successors, (20), 5 states have call predecessors, (20), 5 states have call successors, (20) [2022-04-06 23:04:42,602 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 23:04:42,602 INFO L93 Difference]: Finished difference Result 150 states and 178 transitions. [2022-04-06 23:04:42,602 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-04-06 23:04:42,603 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 4.5) internal successors, (27), 6 states have internal predecessors, (27), 6 states have call successors, (22), 2 states have call predecessors, (22), 1 states have return successors, (20), 5 states have call predecessors, (20), 5 states have call successors, (20) Word has length 120 [2022-04-06 23:04:42,603 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 23:04:42,603 INFO L225 Difference]: With dead ends: 150 [2022-04-06 23:04:42,603 INFO L226 Difference]: Without dead ends: 137 [2022-04-06 23:04:42,604 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 239 GetRequests, 230 SyntacticMatches, 5 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=15, Unknown=0, NotChecked=0, Total=30 [2022-04-06 23:04:42,604 INFO L913 BasicCegarLoop]: 66 mSDtfsCounter, 18 mSDsluCounter, 72 mSDsCounter, 0 mSdLazyCounter, 53 mSolverCounterSat, 18 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 23 SdHoareTripleChecker+Valid, 138 SdHoareTripleChecker+Invalid, 71 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 18 IncrementalHoareTripleChecker+Valid, 53 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 23:04:42,604 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [23 Valid, 138 Invalid, 71 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [18 Valid, 53 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 23:04:42,605 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 137 states. [2022-04-06 23:04:42,614 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 137 to 137. [2022-04-06 23:04:42,614 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 137 states, 83 states have (on average 1.108433734939759) internal successors, (92), 87 states have internal predecessors, (92), 36 states have call successors, (36), 18 states have call predecessors, (36), 17 states have return successors, (34), 31 states have call predecessors, (34), 34 states have call successors, (34) [2022-04-06 23:04:42,615 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 137 states to 137 states and 162 transitions. [2022-04-06 23:04:42,615 INFO L78 Accepts]: Start accepts. Automaton has 137 states and 162 transitions. Word has length 120 [2022-04-06 23:04:42,615 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 23:04:42,615 INFO L478 AbstractCegarLoop]: Abstraction has 137 states and 162 transitions. [2022-04-06 23:04:42,615 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 4.5) internal successors, (27), 6 states have internal predecessors, (27), 6 states have call successors, (22), 2 states have call predecessors, (22), 1 states have return successors, (20), 5 states have call predecessors, (20), 5 states have call successors, (20) [2022-04-06 23:04:42,615 INFO L276 IsEmpty]: Start isEmpty. Operand 137 states and 162 transitions. [2022-04-06 23:04:42,616 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 123 [2022-04-06 23:04:42,616 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:04:42,616 INFO L499 BasicCegarLoop]: trace histogram [17, 16, 16, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:04:42,632 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 23:04:42,823 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,SelfDestructingSolverStorable15 [2022-04-06 23:04:42,823 INFO L403 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:04:42,824 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:04:42,824 INFO L85 PathProgramCache]: Analyzing trace with hash 515319041, now seen corresponding path program 13 times [2022-04-06 23:04:42,824 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:04:42,824 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1913241796] [2022-04-06 23:04:42,824 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 23:04:42,824 INFO L85 PathProgramCache]: Analyzing trace with hash 515319041, now seen corresponding path program 14 times [2022-04-06 23:04:42,824 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:04:42,825 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1238220755] [2022-04-06 23:04:42,825 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:04:42,825 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:04:42,830 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 23:04:42,830 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1551625278] [2022-04-06 23:04:42,830 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 23:04:42,830 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:04:42,830 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 23:04:42,831 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 23:04:42,832 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 23:04:42,880 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 23:04:42,880 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 23:04:42,881 INFO L263 TraceCheckSpWp]: Trace formula consists of 274 conjuncts, 41 conjunts are in the unsatisfiable core [2022-04-06 23:04:42,883 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 23:04:43,551 INFO L134 CoverageAnalysis]: Checked inductivity of 563 backedges. 32 proven. 39 refuted. 0 times theorem prover too weak. 492 trivial. 0 not checked. [2022-04-06 23:04:43,551 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 23:05:20,201 WARN L232 SmtUtils]: Spent 9.74s on a formula simplification that was a NOOP. DAG size: 142 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-06 23:05:50,425 INFO L134 CoverageAnalysis]: Checked inductivity of 563 backedges. 32 proven. 39 refuted. 0 times theorem prover too weak. 492 trivial. 0 not checked. [2022-04-06 23:05:50,425 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 23:05:50,425 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1238220755] [2022-04-06 23:05:50,426 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 23:05:50,426 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1551625278] [2022-04-06 23:05:50,426 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1551625278] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 23:05:50,426 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 23:05:50,426 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 22 [2022-04-06 23:05:50,426 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 23:05:50,426 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1913241796] [2022-04-06 23:05:50,426 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1913241796] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:05:50,426 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:05:50,426 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [13] imperfect sequences [] total 13 [2022-04-06 23:05:50,426 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [581946871] [2022-04-06 23:05:50,426 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 23:05:50,427 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2022-04-06 23:05:50,427 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 23:05:50,427 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2022-04-06 23:05:50,427 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=109, Invalid=353, Unknown=0, NotChecked=0, Total=462 [2022-04-06 23:05:50,427 INFO L87 Difference]: Start difference. First operand 137 states and 162 transitions. Second operand has 13 states, 13 states have (on average 2.230769230769231) internal successors, (29), 12 states have internal predecessors, (29), 8 states have call successors, (22), 2 states have call predecessors, (22), 1 states have return successors, (20), 7 states have call predecessors, (20), 7 states have call successors, (20) [2022-04-06 23:05:51,294 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 23:05:51,294 INFO L93 Difference]: Finished difference Result 241 states and 293 transitions. [2022-04-06 23:05:51,295 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-04-06 23:05:51,295 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 2.230769230769231) internal successors, (29), 12 states have internal predecessors, (29), 8 states have call successors, (22), 2 states have call predecessors, (22), 1 states have return successors, (20), 7 states have call predecessors, (20), 7 states have call successors, (20) Word has length 122 [2022-04-06 23:05:51,295 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 23:05:51,296 INFO L225 Difference]: With dead ends: 241 [2022-04-06 23:05:51,296 INFO L226 Difference]: Without dead ends: 195 [2022-04-06 23:05:51,297 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 244 GetRequests, 222 SyntacticMatches, 1 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 73 ImplicationChecksByTransitivity, 18.6s TimeCoverageRelationStatistics Valid=113, Invalid=393, Unknown=0, NotChecked=0, Total=506 [2022-04-06 23:05:51,297 INFO L913 BasicCegarLoop]: 62 mSDtfsCounter, 12 mSDsluCounter, 271 mSDsCounter, 0 mSdLazyCounter, 583 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 333 SdHoareTripleChecker+Invalid, 605 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 583 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2022-04-06 23:05:51,297 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [17 Valid, 333 Invalid, 605 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 583 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2022-04-06 23:05:51,298 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 195 states. [2022-04-06 23:05:51,325 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 195 to 192. [2022-04-06 23:05:51,325 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 192 states, 118 states have (on average 1.1101694915254237) internal successors, (131), 123 states have internal predecessors, (131), 49 states have call successors, (49), 25 states have call predecessors, (49), 24 states have return successors, (47), 43 states have call predecessors, (47), 47 states have call successors, (47) [2022-04-06 23:05:51,326 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 192 states to 192 states and 227 transitions. [2022-04-06 23:05:51,326 INFO L78 Accepts]: Start accepts. Automaton has 192 states and 227 transitions. Word has length 122 [2022-04-06 23:05:51,326 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 23:05:51,326 INFO L478 AbstractCegarLoop]: Abstraction has 192 states and 227 transitions. [2022-04-06 23:05:51,326 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 2.230769230769231) internal successors, (29), 12 states have internal predecessors, (29), 8 states have call successors, (22), 2 states have call predecessors, (22), 1 states have return successors, (20), 7 states have call predecessors, (20), 7 states have call successors, (20) [2022-04-06 23:05:51,326 INFO L276 IsEmpty]: Start isEmpty. Operand 192 states and 227 transitions. [2022-04-06 23:05:51,327 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 128 [2022-04-06 23:05:51,327 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:05:51,327 INFO L499 BasicCegarLoop]: trace histogram [18, 17, 17, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:05:51,343 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 23:05:51,527 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable16,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:05:51,530 INFO L403 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:05:51,530 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:05:51,530 INFO L85 PathProgramCache]: Analyzing trace with hash -1224833083, now seen corresponding path program 15 times [2022-04-06 23:05:51,530 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:05:51,530 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1087300915] [2022-04-06 23:05:51,530 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 23:05:51,530 INFO L85 PathProgramCache]: Analyzing trace with hash -1224833083, now seen corresponding path program 16 times [2022-04-06 23:05:51,531 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:05:51,531 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [142660971] [2022-04-06 23:05:51,531 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:05:51,531 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:05:51,537 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 23:05:51,537 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [479908528] [2022-04-06 23:05:51,537 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-04-06 23:05:51,538 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:05:51,538 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 23:05:51,538 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 23:05:51,539 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 23:05:51,590 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-04-06 23:05:51,591 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 23:05:51,592 INFO L263 TraceCheckSpWp]: Trace formula consists of 283 conjuncts, 32 conjunts are in the unsatisfiable core [2022-04-06 23:05:51,593 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 23:05:51,977 INFO L134 CoverageAnalysis]: Checked inductivity of 631 backedges. 34 proven. 41 refuted. 0 times theorem prover too weak. 556 trivial. 0 not checked. [2022-04-06 23:05:51,977 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 23:06:06,486 INFO L134 CoverageAnalysis]: Checked inductivity of 631 backedges. 34 proven. 41 refuted. 0 times theorem prover too weak. 556 trivial. 0 not checked. [2022-04-06 23:06:06,486 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 23:06:06,487 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [142660971] [2022-04-06 23:06:06,487 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 23:06:06,487 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [479908528] [2022-04-06 23:06:06,487 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [479908528] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 23:06:06,487 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 23:06:06,487 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11] total 19 [2022-04-06 23:06:06,487 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 23:06:06,487 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1087300915] [2022-04-06 23:06:06,487 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1087300915] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:06:06,487 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:06:06,487 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [12] imperfect sequences [] total 12 [2022-04-06 23:06:06,487 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2011290084] [2022-04-06 23:06:06,487 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 23:06:06,488 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-04-06 23:06:06,488 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 23:06:06,488 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-04-06 23:06:06,488 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=91, Invalid=251, Unknown=0, NotChecked=0, Total=342 [2022-04-06 23:06:06,488 INFO L87 Difference]: Start difference. First operand 192 states and 227 transitions. Second operand has 12 states, 12 states have (on average 2.4166666666666665) internal successors, (29), 11 states have internal predecessors, (29), 8 states have call successors, (23), 2 states have call predecessors, (23), 1 states have return successors, (21), 8 states have call predecessors, (21), 8 states have call successors, (21) [2022-04-06 23:06:06,857 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 23:06:06,858 INFO L93 Difference]: Finished difference Result 238 states and 285 transitions. [2022-04-06 23:06:06,858 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-04-06 23:06:06,858 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 2.4166666666666665) internal successors, (29), 11 states have internal predecessors, (29), 8 states have call successors, (23), 2 states have call predecessors, (23), 1 states have return successors, (21), 8 states have call predecessors, (21), 8 states have call successors, (21) Word has length 127 [2022-04-06 23:06:06,858 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 23:06:06,859 INFO L225 Difference]: With dead ends: 238 [2022-04-06 23:06:06,859 INFO L226 Difference]: Without dead ends: 209 [2022-04-06 23:06:06,860 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 254 GetRequests, 235 SyntacticMatches, 1 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 57 ImplicationChecksByTransitivity, 3.2s TimeCoverageRelationStatistics Valid=95, Invalid=285, Unknown=0, NotChecked=0, Total=380 [2022-04-06 23:06:06,860 INFO L913 BasicCegarLoop]: 72 mSDtfsCounter, 12 mSDsluCounter, 312 mSDsCounter, 0 mSdLazyCounter, 432 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 384 SdHoareTripleChecker+Invalid, 446 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 432 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-04-06 23:06:06,860 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [16 Valid, 384 Invalid, 446 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 432 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-04-06 23:06:06,861 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 209 states. [2022-04-06 23:06:06,875 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 209 to 207. [2022-04-06 23:06:06,876 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 207 states, 128 states have (on average 1.1015625) internal successors, (141), 135 states have internal predecessors, (141), 52 states have call successors, (52), 27 states have call predecessors, (52), 26 states have return successors, (49), 44 states have call predecessors, (49), 49 states have call successors, (49) [2022-04-06 23:06:06,877 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 207 states to 207 states and 242 transitions. [2022-04-06 23:06:06,877 INFO L78 Accepts]: Start accepts. Automaton has 207 states and 242 transitions. Word has length 127 [2022-04-06 23:06:06,877 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 23:06:06,877 INFO L478 AbstractCegarLoop]: Abstraction has 207 states and 242 transitions. [2022-04-06 23:06:06,877 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 2.4166666666666665) internal successors, (29), 11 states have internal predecessors, (29), 8 states have call successors, (23), 2 states have call predecessors, (23), 1 states have return successors, (21), 8 states have call predecessors, (21), 8 states have call successors, (21) [2022-04-06 23:06:06,877 INFO L276 IsEmpty]: Start isEmpty. Operand 207 states and 242 transitions. [2022-04-06 23:06:06,878 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 136 [2022-04-06 23:06:06,878 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:06:06,878 INFO L499 BasicCegarLoop]: trace histogram [19, 18, 18, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:06:06,894 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 23:06:07,094 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,SelfDestructingSolverStorable17 [2022-04-06 23:06:07,094 INFO L403 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:06:07,095 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:06:07,095 INFO L85 PathProgramCache]: Analyzing trace with hash -243845479, now seen corresponding path program 17 times [2022-04-06 23:06:07,095 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:06:07,095 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [746520294] [2022-04-06 23:06:07,095 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 23:06:07,095 INFO L85 PathProgramCache]: Analyzing trace with hash -243845479, now seen corresponding path program 18 times [2022-04-06 23:06:07,095 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:06:07,095 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [931515284] [2022-04-06 23:06:07,095 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:06:07,096 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:06:07,101 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 23:06:07,101 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1925079017] [2022-04-06 23:06:07,102 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-04-06 23:06:07,102 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:06:07,102 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 23:06:07,106 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 23:06:07,107 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 23:06:07,311 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 10 check-sat command(s) [2022-04-06 23:06:07,311 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 23:06:07,313 INFO L263 TraceCheckSpWp]: Trace formula consists of 303 conjuncts, 69 conjunts are in the unsatisfiable core [2022-04-06 23:06:07,315 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 23:06:08,827 INFO L134 CoverageAnalysis]: Checked inductivity of 711 backedges. 171 proven. 57 refuted. 0 times theorem prover too weak. 483 trivial. 0 not checked. [2022-04-06 23:06:08,828 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 23:07:19,903 WARN L232 SmtUtils]: Spent 34.24s on a formula simplification that was a NOOP. DAG size: 54 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-06 23:13:13,134 WARN L855 $PredicateComparison]: unable to prove that (let ((.cse13 (mod c_main_~B~0 4294967296)) (.cse10 (mod c_main_~A~0 4294967296))) (or (let ((.cse1 (div c_main_~p~0 2)) (.cse5 (= (mod c_main_~d~0 2) 0)) (.cse7 (div c_main_~d~0 2))) (let ((.cse3 (+ .cse7 1)) (.cse6 (not .cse5)) (.cse0 (* (- 1) .cse1)) (.cse2 (= (mod c_main_~p~0 2) 0)) (.cse14 (< c_main_~p~0 0))) (and (let ((.cse12 (+ .cse1 1))) (let ((.cse4 (* .cse12 .cse13))) (or (<= (div (+ (- 1) .cse0) (- 2)) (+ (div (+ (- 1) .cse1) 2) 1)) .cse2 (and (or (not (= .cse3 .cse4)) .cse5) (or .cse6 (not (= .cse4 .cse7)))) (let ((.cse8 (* (- 1) (div .cse4 2))) (.cse9 (* (+ c_main_~q~0 (div .cse12 2) 1) .cse13)) (.cse11 (= (mod .cse4 2) 0))) (and (or (= (+ .cse8 c_main_~r~0 .cse9) .cse10) (not .cse11)) (or (= (+ (- 1) .cse8 c_main_~r~0 .cse9) .cse10) .cse11))) (not .cse14)))) (let ((.cse18 (* .cse13 .cse1))) (or (let ((.cse15 (= (mod .cse18 2) 0)) (.cse16 (* (+ c_main_~q~0 (div .cse1 2) 1) .cse13)) (.cse17 (* (- 1) (div .cse18 2)))) (and (or (not .cse15) (= (+ .cse16 .cse17 c_main_~r~0) .cse10)) (or .cse15 (= .cse10 (+ (- 1) .cse16 .cse17 c_main_~r~0))))) (= .cse1 1) (let ((.cse19 (< c_main_~d~0 0))) (and (or (not (= .cse3 .cse18)) .cse5 (not .cse19)) (or (and .cse19 .cse6) (not (= .cse7 .cse18))))) (<= (div .cse0 (- 2)) (+ (div (+ (- 2) .cse1) 2) 1)) (and (not .cse2) .cse14)))))) (not (= (+ c_main_~r~0 (* c_main_~q~0 .cse13)) .cse10)))) is different from true [2022-04-06 23:14:08,280 WARN L232 SmtUtils]: Spent 11.43s on a formula simplification that was a NOOP. DAG size: 101 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-06 23:15:26,415 WARN L232 SmtUtils]: Spent 37.67s on a formula simplification that was a NOOP. DAG size: 208 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate)