/usr/bin/java -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data --core.log.level.for.class de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN -tc ../../../trunk/examples/toolchains/AutomizerC.xml -s ../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationJordan_32.epf -i ../../../trunk/examples/svcomp/nla-digbench-scaling/ps6-ll_valuebound100.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-34549b5 [2022-04-06 18:35:28,241 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-06 18:35:28,242 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-06 18:35:28,274 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-06 18:35:28,274 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-06 18:35:28,275 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-06 18:35:28,278 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-06 18:35:28,283 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-06 18:35:28,284 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-06 18:35:28,287 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-06 18:35:28,288 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-06 18:35:28,289 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-06 18:35:28,289 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-06 18:35:28,291 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-06 18:35:28,291 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-06 18:35:28,292 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-06 18:35:28,292 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-06 18:35:28,293 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-06 18:35:28,296 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-06 18:35:28,300 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-06 18:35:28,301 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-06 18:35:28,302 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-06 18:35:28,302 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-06 18:35:28,303 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-06 18:35:28,304 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-06 18:35:28,308 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-06 18:35:28,309 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-06 18:35:28,309 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-06 18:35:28,310 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-06 18:35:28,310 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-06 18:35:28,311 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-06 18:35:28,311 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-06 18:35:28,312 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-06 18:35:28,313 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-06 18:35:28,313 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-06 18:35:28,313 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-06 18:35:28,313 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-06 18:35:28,314 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-06 18:35:28,314 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-06 18:35:28,314 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-06 18:35:28,314 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-06 18:35:28,316 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-06 18:35:28,316 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationJordan_32.epf [2022-04-06 18:35:28,325 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-06 18:35:28,325 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-06 18:35:28,326 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-06 18:35:28,326 INFO L138 SettingsManager]: * sizeof long=4 [2022-04-06 18:35:28,326 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-06 18:35:28,326 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-04-06 18:35:28,327 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-06 18:35:28,327 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-06 18:35:28,327 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-06 18:35:28,327 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-06 18:35:28,327 INFO L138 SettingsManager]: * sizeof long double=12 [2022-04-06 18:35:28,328 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-06 18:35:28,328 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-06 18:35:28,328 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-06 18:35:28,328 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-06 18:35:28,328 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-06 18:35:28,328 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-04-06 18:35:28,328 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-06 18:35:28,328 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-06 18:35:28,328 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-06 18:35:28,328 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_NestedInterpolation [2022-04-06 18:35:28,328 INFO L138 SettingsManager]: * Trace refinement strategy=ACCELERATED_INTERPOLATION [2022-04-06 18:35:28,328 INFO L138 SettingsManager]: * Trace refinement strategy used in Accelerated Interpolation=CAMEL [2022-04-06 18:35:28,329 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-04-06 18:35:28,329 INFO L138 SettingsManager]: * Loop acceleration method that is used by accelerated interpolation=JORDAN [2022-04-06 18:35:28,329 INFO L138 SettingsManager]: * Use separate solver for trace checks=false WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.core: Log level for class -> de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN; [2022-04-06 18:35:28,536 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-06 18:35:28,552 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-06 18:35:28,554 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-06 18:35:28,555 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-06 18:35:28,555 INFO L275 PluginConnector]: CDTParser initialized [2022-04-06 18:35:28,557 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/ps6-ll_valuebound100.c [2022-04-06 18:35:28,599 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/967db3725/7949fedf02744ea7a93d3f66f2f3afab/FLAGcd54747c1 [2022-04-06 18:35:28,945 INFO L306 CDTParser]: Found 1 translation units. [2022-04-06 18:35:28,945 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/ps6-ll_valuebound100.c [2022-04-06 18:35:28,957 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/967db3725/7949fedf02744ea7a93d3f66f2f3afab/FLAGcd54747c1 [2022-04-06 18:35:28,972 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/967db3725/7949fedf02744ea7a93d3f66f2f3afab [2022-04-06 18:35:28,974 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-06 18:35:28,975 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-04-06 18:35:28,977 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-06 18:35:28,977 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-06 18:35:28,979 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-06 18:35:28,980 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.04 06:35:28" (1/1) ... [2022-04-06 18:35:28,981 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@4283c4e4 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 06:35:28, skipping insertion in model container [2022-04-06 18:35:28,981 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.04 06:35:28" (1/1) ... [2022-04-06 18:35:28,986 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-06 18:35:28,998 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-06 18:35:29,118 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/ps6-ll_valuebound100.c[458,471] [2022-04-06 18:35:29,129 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-06 18:35:29,134 INFO L203 MainTranslator]: Completed pre-run [2022-04-06 18:35:29,141 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/ps6-ll_valuebound100.c[458,471] [2022-04-06 18:35:29,146 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-06 18:35:29,154 INFO L208 MainTranslator]: Completed translation [2022-04-06 18:35:29,155 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 06:35:29 WrapperNode [2022-04-06 18:35:29,155 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-06 18:35:29,156 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-06 18:35:29,156 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-06 18:35:29,156 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-06 18:35:29,163 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 06:35:29" (1/1) ... [2022-04-06 18:35:29,163 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 06:35:29" (1/1) ... [2022-04-06 18:35:29,167 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 06:35:29" (1/1) ... [2022-04-06 18:35:29,167 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 06:35:29" (1/1) ... [2022-04-06 18:35:29,172 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 06:35:29" (1/1) ... [2022-04-06 18:35:29,174 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 06:35:29" (1/1) ... [2022-04-06 18:35:29,175 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 06:35:29" (1/1) ... [2022-04-06 18:35:29,176 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-06 18:35:29,177 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-06 18:35:29,177 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-06 18:35:29,177 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-06 18:35:29,178 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 06:35:29" (1/1) ... [2022-04-06 18:35:29,183 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-06 18:35:29,189 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:35:29,197 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2022-04-06 18:35:29,199 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2022-04-06 18:35:29,222 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-06 18:35:29,222 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-06 18:35:29,222 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-06 18:35:29,222 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-06 18:35:29,222 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-06 18:35:29,223 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-06 18:35:29,223 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-06 18:35:29,223 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-06 18:35:29,223 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-06 18:35:29,223 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-06 18:35:29,223 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_short [2022-04-06 18:35:29,223 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-06 18:35:29,223 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-06 18:35:29,223 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-06 18:35:29,223 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-06 18:35:29,223 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-06 18:35:29,223 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-06 18:35:29,223 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-06 18:35:29,223 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-06 18:35:29,224 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-06 18:35:29,273 INFO L234 CfgBuilder]: Building ICFG [2022-04-06 18:35:29,274 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-06 18:35:29,371 INFO L275 CfgBuilder]: Performing block encoding [2022-04-06 18:35:29,375 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-06 18:35:29,376 INFO L299 CfgBuilder]: Removed 1 assume(true) statements. [2022-04-06 18:35:29,377 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.04 06:35:29 BoogieIcfgContainer [2022-04-06 18:35:29,377 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-06 18:35:29,378 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-06 18:35:29,378 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-06 18:35:29,415 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-06 18:35:29,416 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 06.04 06:35:28" (1/3) ... [2022-04-06 18:35:29,416 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3cf781ec and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.04 06:35:29, skipping insertion in model container [2022-04-06 18:35:29,416 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 06:35:29" (2/3) ... [2022-04-06 18:35:29,417 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3cf781ec and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.04 06:35:29, skipping insertion in model container [2022-04-06 18:35:29,417 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.04 06:35:29" (3/3) ... [2022-04-06 18:35:29,419 INFO L111 eAbstractionObserver]: Analyzing ICFG ps6-ll_valuebound100.c [2022-04-06 18:35:29,422 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:Craig_NestedInterpolation Determinization: PREDICATE_ABSTRACTION [2022-04-06 18:35:29,422 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-06 18:35:29,458 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-06 18:35:29,467 INFO L340 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=Craig_NestedInterpolation, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=All, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP [2022-04-06 18:35:29,467 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-06 18:35:29,481 INFO L276 IsEmpty]: Start isEmpty. Operand has 29 states, 16 states have (on average 1.375) internal successors, (22), 17 states have internal predecessors, (22), 7 states have call successors, (7), 4 states have call predecessors, (7), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-06 18:35:29,494 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2022-04-06 18:35:29,494 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:35:29,495 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:35:29,495 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:35:29,499 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:35:29,499 INFO L85 PathProgramCache]: Analyzing trace with hash 1098891495, now seen corresponding path program 1 times [2022-04-06 18:35:29,505 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:35:29,506 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [295047128] [2022-04-06 18:35:29,514 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 18:35:29,514 INFO L85 PathProgramCache]: Analyzing trace with hash 1098891495, now seen corresponding path program 2 times [2022-04-06 18:35:29,516 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:35:29,516 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1949533031] [2022-04-06 18:35:29,516 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:35:29,517 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:35:29,601 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 18:35:29,661 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-06 18:35:29,673 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 18:35:29,689 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-06 18:35:29,690 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 18:35:29,696 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2022-04-06 18:35:29,698 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 18:35:29,708 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-06 18:35:29,709 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:35:29,709 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1949533031] [2022-04-06 18:35:29,709 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1949533031] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:35:29,709 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:35:29,709 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-06 18:35:29,711 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:35:29,711 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [295047128] [2022-04-06 18:35:29,711 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [295047128] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:35:29,711 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:35:29,712 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-06 18:35:29,712 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [158037531] [2022-04-06 18:35:29,712 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:35:29,716 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-06 18:35:29,717 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:35:29,737 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-06 18:35:29,737 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-06 18:35:29,739 INFO L87 Difference]: Start difference. First operand has 29 states, 16 states have (on average 1.375) internal successors, (22), 17 states have internal predecessors, (22), 7 states have call successors, (7), 4 states have call predecessors, (7), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-06 18:35:29,803 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:35:29,803 INFO L93 Difference]: Finished difference Result 51 states and 69 transitions. [2022-04-06 18:35:29,805 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-06 18:35:29,807 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 22 [2022-04-06 18:35:29,807 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:35:29,812 INFO L225 Difference]: With dead ends: 51 [2022-04-06 18:35:29,812 INFO L226 Difference]: Without dead ends: 24 [2022-04-06 18:35:29,815 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-06 18:35:29,821 INFO L913 BasicCegarLoop]: 27 mSDtfsCounter, 15 mSDsluCounter, 3 mSDsCounter, 0 mSdLazyCounter, 7 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 20 SdHoareTripleChecker+Valid, 30 SdHoareTripleChecker+Invalid, 13 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 7 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 18:35:29,822 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [20 Valid, 30 Invalid, 13 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 7 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 18:35:29,833 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states. [2022-04-06 18:35:29,855 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2022-04-06 18:35:29,856 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24 states, 13 states have (on average 1.1538461538461537) internal successors, (15), 14 states have internal predecessors, (15), 7 states have call successors, (7), 4 states have call predecessors, (7), 3 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-06 18:35:29,857 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 27 transitions. [2022-04-06 18:35:29,858 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 27 transitions. Word has length 22 [2022-04-06 18:35:29,858 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:35:29,858 INFO L478 AbstractCegarLoop]: Abstraction has 24 states and 27 transitions. [2022-04-06 18:35:29,859 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-06 18:35:29,859 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 27 transitions. [2022-04-06 18:35:29,860 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2022-04-06 18:35:29,860 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:35:29,861 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:35:29,861 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-06 18:35:29,861 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:35:29,862 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:35:29,863 INFO L85 PathProgramCache]: Analyzing trace with hash 769620075, now seen corresponding path program 1 times [2022-04-06 18:35:29,863 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:35:29,863 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [706700444] [2022-04-06 18:35:29,865 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 18:35:29,865 INFO L85 PathProgramCache]: Analyzing trace with hash 769620075, now seen corresponding path program 2 times [2022-04-06 18:35:29,865 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:35:29,865 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1955446872] [2022-04-06 18:35:29,866 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:35:29,866 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:35:29,880 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:35:29,880 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1122857211] [2022-04-06 18:35:29,880 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 18:35:29,881 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:35:29,881 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:35:29,892 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 18:35:29,897 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2022-04-06 18:35:29,936 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2022-04-06 18:35:29,936 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:35:29,938 INFO L263 TraceCheckSpWp]: Trace formula consists of 68 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-06 18:35:29,942 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:35:30,034 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-06 18:35:30,035 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-06 18:35:30,035 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:35:30,035 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1955446872] [2022-04-06 18:35:30,035 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:35:30,035 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1122857211] [2022-04-06 18:35:30,035 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1122857211] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:35:30,036 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:35:30,036 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 18:35:30,036 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:35:30,036 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [706700444] [2022-04-06 18:35:30,036 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [706700444] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:35:30,037 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:35:30,037 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 18:35:30,037 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2099296859] [2022-04-06 18:35:30,037 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:35:30,037 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 18:35:30,037 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:35:30,038 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 18:35:30,038 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-06 18:35:30,038 INFO L87 Difference]: Start difference. First operand 24 states and 27 transitions. Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2022-04-06 18:35:30,073 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:35:30,088 INFO L93 Difference]: Finished difference Result 35 states and 40 transitions. [2022-04-06 18:35:30,089 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-06 18:35:30,089 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 22 [2022-04-06 18:35:30,089 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:35:30,090 INFO L225 Difference]: With dead ends: 35 [2022-04-06 18:35:30,090 INFO L226 Difference]: Without dead ends: 31 [2022-04-06 18:35:30,090 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 22 GetRequests, 18 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-04-06 18:35:30,091 INFO L913 BasicCegarLoop]: 24 mSDtfsCounter, 6 mSDsluCounter, 61 mSDsCounter, 0 mSdLazyCounter, 28 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 85 SdHoareTripleChecker+Invalid, 30 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 28 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 18:35:30,092 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [8 Valid, 85 Invalid, 30 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 28 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 18:35:30,092 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2022-04-06 18:35:30,099 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 31. [2022-04-06 18:35:30,100 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 31 states, 18 states have (on average 1.1111111111111112) internal successors, (20), 19 states have internal predecessors, (20), 8 states have call successors, (8), 5 states have call predecessors, (8), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-06 18:35:30,101 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 34 transitions. [2022-04-06 18:35:30,101 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 34 transitions. Word has length 22 [2022-04-06 18:35:30,101 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:35:30,101 INFO L478 AbstractCegarLoop]: Abstraction has 31 states and 34 transitions. [2022-04-06 18:35:30,101 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2022-04-06 18:35:30,101 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 34 transitions. [2022-04-06 18:35:30,102 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2022-04-06 18:35:30,102 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:35:30,102 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:35:30,123 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 18:35:30,311 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:35:30,312 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:35:30,315 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:35:30,315 INFO L85 PathProgramCache]: Analyzing trace with hash 645812411, now seen corresponding path program 1 times [2022-04-06 18:35:30,316 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:35:30,316 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1197005324] [2022-04-06 18:35:30,316 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 18:35:30,316 INFO L85 PathProgramCache]: Analyzing trace with hash 645812411, now seen corresponding path program 2 times [2022-04-06 18:35:30,316 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:35:30,317 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1212403431] [2022-04-06 18:35:30,317 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:35:30,317 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:35:30,326 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:35:30,326 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1875954773] [2022-04-06 18:35:30,326 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 18:35:30,326 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:35:30,327 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:35:30,343 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 18:35:30,348 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2022-04-06 18:35:30,380 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 18:35:30,380 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:35:30,381 INFO L263 TraceCheckSpWp]: Trace formula consists of 94 conjuncts, 11 conjunts are in the unsatisfiable core [2022-04-06 18:35:30,382 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:35:30,472 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-06 18:35:30,472 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 18:35:30,942 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2022-04-06 18:35:30,943 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:35:30,943 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1212403431] [2022-04-06 18:35:30,943 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:35:30,943 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1875954773] [2022-04-06 18:35:30,943 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1875954773] provided 1 perfect and 1 imperfect interpolant sequences [2022-04-06 18:35:30,943 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-04-06 18:35:30,943 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2022-04-06 18:35:30,944 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:35:30,944 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1197005324] [2022-04-06 18:35:30,944 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1197005324] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:35:30,944 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:35:30,944 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 18:35:30,944 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [616417084] [2022-04-06 18:35:30,944 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:35:30,945 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 18:35:30,945 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:35:30,945 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 18:35:30,945 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2022-04-06 18:35:30,945 INFO L87 Difference]: Start difference. First operand 31 states and 34 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, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-06 18:35:30,981 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:35:30,981 INFO L93 Difference]: Finished difference Result 37 states and 39 transitions. [2022-04-06 18:35:30,981 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-06 18:35:30,982 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, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 29 [2022-04-06 18:35:30,982 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:35:30,982 INFO L225 Difference]: With dead ends: 37 [2022-04-06 18:35:30,982 INFO L226 Difference]: Without dead ends: 33 [2022-04-06 18:35:30,983 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 58 GetRequests, 50 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2022-04-06 18:35:30,984 INFO L913 BasicCegarLoop]: 22 mSDtfsCounter, 6 mSDsluCounter, 53 mSDsCounter, 0 mSdLazyCounter, 25 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 75 SdHoareTripleChecker+Invalid, 26 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 25 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 18:35:30,984 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [7 Valid, 75 Invalid, 26 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 25 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 18:35:30,984 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2022-04-06 18:35:30,990 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 33. [2022-04-06 18:35:30,990 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 33 states, 20 states have (on average 1.05) internal successors, (21), 20 states have internal predecessors, (21), 8 states have call successors, (8), 6 states have call predecessors, (8), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-06 18:35:30,991 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 35 transitions. [2022-04-06 18:35:30,991 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 35 transitions. Word has length 29 [2022-04-06 18:35:30,991 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:35:30,991 INFO L478 AbstractCegarLoop]: Abstraction has 33 states and 35 transitions. [2022-04-06 18:35:30,991 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, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-06 18:35:30,992 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 35 transitions. [2022-04-06 18:35:30,992 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2022-04-06 18:35:30,992 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:35:30,992 INFO L499 BasicCegarLoop]: trace histogram [4, 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 18:35:31,013 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2022-04-06 18:35:31,209 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2022-04-06 18:35:31,209 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:35:31,210 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:35:31,210 INFO L85 PathProgramCache]: Analyzing trace with hash 463554397, now seen corresponding path program 1 times [2022-04-06 18:35:31,210 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:35:31,210 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1397185650] [2022-04-06 18:35:31,210 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 18:35:31,210 INFO L85 PathProgramCache]: Analyzing trace with hash 463554397, now seen corresponding path program 2 times [2022-04-06 18:35:31,211 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:35:31,211 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [541401727] [2022-04-06 18:35:31,211 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:35:31,211 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:35:31,222 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:35:31,222 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [544402387] [2022-04-06 18:35:31,222 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 18:35:31,222 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:35:31,222 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:35:31,239 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 18:35:31,262 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2022-04-06 18:35:31,288 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 18:35:31,288 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:35:31,289 INFO L263 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 12 conjunts are in the unsatisfiable core [2022-04-06 18:35:31,292 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:35:31,477 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 6 proven. 3 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2022-04-06 18:35:31,478 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 18:35:31,605 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:35:31,605 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [541401727] [2022-04-06 18:35:31,606 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:35:31,607 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [544402387] [2022-04-06 18:35:31,608 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [544402387] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-06 18:35:31,611 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-06 18:35:31,612 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2022-04-06 18:35:31,612 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:35:31,612 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1397185650] [2022-04-06 18:35:31,614 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1397185650] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:35:31,614 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:35:31,614 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2022-04-06 18:35:31,614 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [827254423] [2022-04-06 18:35:31,615 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:35:31,615 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-04-06 18:35:31,615 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:35:31,616 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-04-06 18:35:31,616 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=66, Unknown=0, NotChecked=0, Total=90 [2022-04-06 18:35:31,616 INFO L87 Difference]: Start difference. First operand 33 states and 35 transitions. Second operand has 7 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 6 states have internal predecessors, (17), 4 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 4 states have call predecessors, (6), 4 states have call successors, (6) [2022-04-06 18:35:31,695 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:35:31,696 INFO L93 Difference]: Finished difference Result 42 states and 46 transitions. [2022-04-06 18:35:31,696 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-04-06 18:35:31,696 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 6 states have internal predecessors, (17), 4 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 4 states have call predecessors, (6), 4 states have call successors, (6) Word has length 40 [2022-04-06 18:35:31,696 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:35:31,697 INFO L225 Difference]: With dead ends: 42 [2022-04-06 18:35:31,697 INFO L226 Difference]: Without dead ends: 36 [2022-04-06 18:35:31,701 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 59 GetRequests, 48 SyntacticMatches, 1 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=34, Invalid=98, Unknown=0, NotChecked=0, Total=132 [2022-04-06 18:35:31,703 INFO L913 BasicCegarLoop]: 30 mSDtfsCounter, 2 mSDsluCounter, 105 mSDsCounter, 0 mSdLazyCounter, 59 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 135 SdHoareTripleChecker+Invalid, 60 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 59 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 18:35:31,704 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 135 Invalid, 60 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 59 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 18:35:31,706 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36 states. [2022-04-06 18:35:31,718 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36 to 36. [2022-04-06 18:35:31,718 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 36 states, 22 states have (on average 1.0454545454545454) internal successors, (23), 22 states have internal predecessors, (23), 9 states have call successors, (9), 6 states have call predecessors, (9), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-06 18:35:31,726 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 39 transitions. [2022-04-06 18:35:31,726 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 39 transitions. Word has length 40 [2022-04-06 18:35:31,727 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:35:31,727 INFO L478 AbstractCegarLoop]: Abstraction has 36 states and 39 transitions. [2022-04-06 18:35:31,727 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 6 states have internal predecessors, (17), 4 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 4 states have call predecessors, (6), 4 states have call successors, (6) [2022-04-06 18:35:31,727 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 39 transitions. [2022-04-06 18:35:31,728 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2022-04-06 18:35:31,728 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:35:31,729 INFO L499 BasicCegarLoop]: trace histogram [5, 4, 4, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:35:31,745 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2022-04-06 18:35:31,935 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:35:31,935 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:35:31,936 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:35:31,936 INFO L85 PathProgramCache]: Analyzing trace with hash 1886956461, now seen corresponding path program 3 times [2022-04-06 18:35:31,936 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:35:31,936 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1863509701] [2022-04-06 18:35:31,936 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 18:35:31,936 INFO L85 PathProgramCache]: Analyzing trace with hash 1886956461, now seen corresponding path program 4 times [2022-04-06 18:35:31,937 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:35:31,937 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1504405461] [2022-04-06 18:35:31,937 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:35:31,937 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:35:31,945 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:35:31,945 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1938160759] [2022-04-06 18:35:31,945 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-04-06 18:35:31,946 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:35:31,946 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:35:31,949 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 18:35:31,950 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2022-04-06 18:35:31,987 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-04-06 18:35:31,987 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:35:31,988 INFO L263 TraceCheckSpWp]: Trace formula consists of 79 conjuncts, 16 conjunts are in the unsatisfiable core [2022-04-06 18:35:31,990 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:35:32,134 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 8 proven. 9 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2022-04-06 18:35:32,134 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 18:35:32,266 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:35:32,266 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1504405461] [2022-04-06 18:35:32,266 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:35:32,266 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1938160759] [2022-04-06 18:35:32,266 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1938160759] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-06 18:35:32,266 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-06 18:35:32,266 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8] total 8 [2022-04-06 18:35:32,267 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:35:32,267 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1863509701] [2022-04-06 18:35:32,267 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1863509701] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:35:32,267 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:35:32,267 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2022-04-06 18:35:32,267 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2008057465] [2022-04-06 18:35:32,267 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:35:32,267 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-04-06 18:35:32,267 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:35:32,267 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-04-06 18:35:32,268 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2022-04-06 18:35:32,268 INFO L87 Difference]: Start difference. First operand 36 states and 39 transitions. Second operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 7 states have internal predecessors, (19), 5 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 5 states have call predecessors, (7), 5 states have call successors, (7) [2022-04-06 18:35:32,339 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:35:32,339 INFO L93 Difference]: Finished difference Result 45 states and 50 transitions. [2022-04-06 18:35:32,339 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-04-06 18:35:32,340 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 7 states have internal predecessors, (19), 5 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 5 states have call predecessors, (7), 5 states have call successors, (7) Word has length 47 [2022-04-06 18:35:32,340 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:35:32,340 INFO L225 Difference]: With dead ends: 45 [2022-04-06 18:35:32,340 INFO L226 Difference]: Without dead ends: 39 [2022-04-06 18:35:32,341 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 66 GetRequests, 54 SyntacticMatches, 1 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=37, Invalid=119, Unknown=0, NotChecked=0, Total=156 [2022-04-06 18:35:32,341 INFO L913 BasicCegarLoop]: 33 mSDtfsCounter, 2 mSDsluCounter, 133 mSDsCounter, 0 mSdLazyCounter, 87 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 166 SdHoareTripleChecker+Invalid, 88 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 87 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 18:35:32,341 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 166 Invalid, 88 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 87 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 18:35:32,342 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2022-04-06 18:35:32,347 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 39. [2022-04-06 18:35:32,347 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 39 states, 24 states have (on average 1.0416666666666667) internal successors, (25), 24 states have internal predecessors, (25), 10 states have call successors, (10), 6 states have call predecessors, (10), 4 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-06 18:35:32,348 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 43 transitions. [2022-04-06 18:35:32,348 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 43 transitions. Word has length 47 [2022-04-06 18:35:32,348 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:35:32,348 INFO L478 AbstractCegarLoop]: Abstraction has 39 states and 43 transitions. [2022-04-06 18:35:32,348 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 7 states have internal predecessors, (19), 5 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 5 states have call predecessors, (7), 5 states have call successors, (7) [2022-04-06 18:35:32,348 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 43 transitions. [2022-04-06 18:35:32,349 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2022-04-06 18:35:32,349 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:35:32,349 INFO L499 BasicCegarLoop]: trace histogram [6, 5, 5, 4, 4, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:35:32,367 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2022-04-06 18:35:32,549 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:35:32,550 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:35:32,550 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:35:32,550 INFO L85 PathProgramCache]: Analyzing trace with hash -1213805219, now seen corresponding path program 5 times [2022-04-06 18:35:32,550 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:35:32,550 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [200274673] [2022-04-06 18:35:32,551 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 18:35:32,551 INFO L85 PathProgramCache]: Analyzing trace with hash -1213805219, now seen corresponding path program 6 times [2022-04-06 18:35:32,551 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:35:32,551 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1503853075] [2022-04-06 18:35:32,551 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:35:32,551 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:35:32,559 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:35:32,559 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1265798721] [2022-04-06 18:35:32,560 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-04-06 18:35:32,560 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:35:32,560 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:35:32,564 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 18:35:32,565 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2022-04-06 18:35:32,707 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2022-04-06 18:35:32,707 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:35:32,711 INFO L263 TraceCheckSpWp]: Trace formula consists of 147 conjuncts, 20 conjunts are in the unsatisfiable core [2022-04-06 18:35:32,721 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:35:32,922 INFO L134 CoverageAnalysis]: Checked inductivity of 72 backedges. 10 proven. 18 refuted. 0 times theorem prover too weak. 44 trivial. 0 not checked. [2022-04-06 18:35:32,922 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 18:35:33,055 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:35:33,055 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1503853075] [2022-04-06 18:35:33,055 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:35:33,055 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1265798721] [2022-04-06 18:35:33,055 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1265798721] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-06 18:35:33,055 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-06 18:35:33,055 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2022-04-06 18:35:33,055 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:35:33,055 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [200274673] [2022-04-06 18:35:33,055 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [200274673] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:35:33,056 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:35:33,056 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2022-04-06 18:35:33,056 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [451668215] [2022-04-06 18:35:33,056 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:35:33,056 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-04-06 18:35:33,056 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:35:33,056 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-04-06 18:35:33,057 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2022-04-06 18:35:33,057 INFO L87 Difference]: Start difference. First operand 39 states and 43 transitions. Second operand has 9 states, 8 states have (on average 2.625) internal successors, (21), 8 states have internal predecessors, (21), 6 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 6 states have call predecessors, (8), 6 states have call successors, (8) [2022-04-06 18:35:33,164 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:35:33,164 INFO L93 Difference]: Finished difference Result 48 states and 54 transitions. [2022-04-06 18:35:33,165 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-04-06 18:35:33,165 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 2.625) internal successors, (21), 8 states have internal predecessors, (21), 6 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 6 states have call predecessors, (8), 6 states have call successors, (8) Word has length 54 [2022-04-06 18:35:33,166 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:35:33,166 INFO L225 Difference]: With dead ends: 48 [2022-04-06 18:35:33,166 INFO L226 Difference]: Without dead ends: 42 [2022-04-06 18:35:33,166 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 73 GetRequests, 60 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=40, Invalid=142, Unknown=0, NotChecked=0, Total=182 [2022-04-06 18:35:33,167 INFO L913 BasicCegarLoop]: 36 mSDtfsCounter, 2 mSDsluCounter, 163 mSDsCounter, 0 mSdLazyCounter, 121 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 199 SdHoareTripleChecker+Invalid, 122 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 121 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 18:35:33,167 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 199 Invalid, 122 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 121 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 18:35:33,167 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states. [2022-04-06 18:35:33,173 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 42. [2022-04-06 18:35:33,174 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 42 states, 26 states have (on average 1.0384615384615385) internal successors, (27), 26 states have internal predecessors, (27), 11 states have call successors, (11), 6 states have call predecessors, (11), 4 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-06 18:35:33,176 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 42 states to 42 states and 47 transitions. [2022-04-06 18:35:33,176 INFO L78 Accepts]: Start accepts. Automaton has 42 states and 47 transitions. Word has length 54 [2022-04-06 18:35:33,176 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:35:33,176 INFO L478 AbstractCegarLoop]: Abstraction has 42 states and 47 transitions. [2022-04-06 18:35:33,177 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 2.625) internal successors, (21), 8 states have internal predecessors, (21), 6 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 6 states have call predecessors, (8), 6 states have call successors, (8) [2022-04-06 18:35:33,177 INFO L276 IsEmpty]: Start isEmpty. Operand 42 states and 47 transitions. [2022-04-06 18:35:33,180 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 62 [2022-04-06 18:35:33,180 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:35:33,180 INFO L499 BasicCegarLoop]: trace histogram [7, 6, 6, 5, 5, 5, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:35:33,187 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2022-04-06 18:35:33,386 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:35:33,386 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:35:33,386 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:35:33,386 INFO L85 PathProgramCache]: Analyzing trace with hash 307258797, now seen corresponding path program 7 times [2022-04-06 18:35:33,386 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:35:33,386 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1584347234] [2022-04-06 18:35:33,387 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 18:35:33,387 INFO L85 PathProgramCache]: Analyzing trace with hash 307258797, now seen corresponding path program 8 times [2022-04-06 18:35:33,387 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:35:33,387 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2055074233] [2022-04-06 18:35:33,387 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:35:33,387 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:35:33,394 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:35:33,394 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1059832470] [2022-04-06 18:35:33,395 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 18:35:33,395 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:35:33,395 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:35:33,396 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 18:35:33,397 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2022-04-06 18:35:33,622 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 18:35:33,623 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:35:33,624 INFO L263 TraceCheckSpWp]: Trace formula consists of 164 conjuncts, 24 conjunts are in the unsatisfiable core [2022-04-06 18:35:33,626 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:35:33,805 INFO L134 CoverageAnalysis]: Checked inductivity of 106 backedges. 12 proven. 30 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2022-04-06 18:35:33,805 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 18:35:33,913 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:35:33,914 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2055074233] [2022-04-06 18:35:33,914 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:35:33,914 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1059832470] [2022-04-06 18:35:33,914 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1059832470] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-06 18:35:33,914 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-06 18:35:33,914 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2022-04-06 18:35:33,914 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:35:33,914 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1584347234] [2022-04-06 18:35:33,914 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1584347234] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:35:33,914 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:35:33,914 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [] total 10 [2022-04-06 18:35:33,914 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1729030955] [2022-04-06 18:35:33,914 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:35:33,915 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-04-06 18:35:33,915 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:35:33,915 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-04-06 18:35:33,915 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=123, Unknown=0, NotChecked=0, Total=156 [2022-04-06 18:35:33,915 INFO L87 Difference]: Start difference. First operand 42 states and 47 transitions. Second operand has 10 states, 9 states have (on average 2.5555555555555554) internal successors, (23), 9 states have internal predecessors, (23), 7 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 7 states have call predecessors, (9), 7 states have call successors, (9) [2022-04-06 18:35:34,050 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:35:34,050 INFO L93 Difference]: Finished difference Result 51 states and 58 transitions. [2022-04-06 18:35:34,050 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-04-06 18:35:34,050 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 2.5555555555555554) internal successors, (23), 9 states have internal predecessors, (23), 7 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 7 states have call predecessors, (9), 7 states have call successors, (9) Word has length 61 [2022-04-06 18:35:34,051 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:35:34,051 INFO L225 Difference]: With dead ends: 51 [2022-04-06 18:35:34,051 INFO L226 Difference]: Without dead ends: 45 [2022-04-06 18:35:34,051 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 80 GetRequests, 66 SyntacticMatches, 1 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=43, Invalid=167, Unknown=0, NotChecked=0, Total=210 [2022-04-06 18:35:34,052 INFO L913 BasicCegarLoop]: 39 mSDtfsCounter, 2 mSDsluCounter, 195 mSDsCounter, 0 mSdLazyCounter, 161 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 234 SdHoareTripleChecker+Invalid, 162 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 161 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 18:35:34,052 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 234 Invalid, 162 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 161 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 18:35:34,052 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2022-04-06 18:35:34,058 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 45. [2022-04-06 18:35:34,058 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 28 states have (on average 1.0357142857142858) internal successors, (29), 28 states have internal predecessors, (29), 12 states have call successors, (12), 6 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 18:35:34,058 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 51 transitions. [2022-04-06 18:35:34,058 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 51 transitions. Word has length 61 [2022-04-06 18:35:34,058 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:35:34,059 INFO L478 AbstractCegarLoop]: Abstraction has 45 states and 51 transitions. [2022-04-06 18:35:34,059 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 2.5555555555555554) internal successors, (23), 9 states have internal predecessors, (23), 7 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 7 states have call predecessors, (9), 7 states have call successors, (9) [2022-04-06 18:35:34,059 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 51 transitions. [2022-04-06 18:35:34,059 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 69 [2022-04-06 18:35:34,059 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:35:34,059 INFO L499 BasicCegarLoop]: trace histogram [8, 7, 7, 6, 6, 6, 5, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:35:34,065 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2022-04-06 18:35:34,263 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:35:34,264 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:35:34,264 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:35:34,264 INFO L85 PathProgramCache]: Analyzing trace with hash 1082774365, now seen corresponding path program 9 times [2022-04-06 18:35:34,264 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:35:34,264 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [620831504] [2022-04-06 18:35:34,265 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 18:35:34,265 INFO L85 PathProgramCache]: Analyzing trace with hash 1082774365, now seen corresponding path program 10 times [2022-04-06 18:35:34,265 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:35:34,265 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [542849010] [2022-04-06 18:35:34,265 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:35:34,265 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:35:34,272 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:35:34,272 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [139329178] [2022-04-06 18:35:34,272 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-04-06 18:35:34,272 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:35:34,272 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:35:34,273 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 18:35:34,274 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2022-04-06 18:35:34,304 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-04-06 18:35:34,304 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:35:34,305 INFO L263 TraceCheckSpWp]: Trace formula consists of 118 conjuncts, 28 conjunts are in the unsatisfiable core [2022-04-06 18:35:34,307 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:35:34,509 INFO L134 CoverageAnalysis]: Checked inductivity of 147 backedges. 14 proven. 45 refuted. 0 times theorem prover too weak. 88 trivial. 0 not checked. [2022-04-06 18:35:34,510 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 18:35:34,617 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:35:34,617 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [542849010] [2022-04-06 18:35:34,617 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:35:34,617 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [139329178] [2022-04-06 18:35:34,618 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [139329178] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-06 18:35:34,618 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-06 18:35:34,618 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2022-04-06 18:35:34,618 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:35:34,618 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [620831504] [2022-04-06 18:35:34,618 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [620831504] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:35:34,618 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:35:34,618 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [11] imperfect sequences [] total 11 [2022-04-06 18:35:34,618 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1208335946] [2022-04-06 18:35:34,618 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:35:34,618 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2022-04-06 18:35:34,619 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:35:34,619 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2022-04-06 18:35:34,619 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=36, Invalid=146, Unknown=0, NotChecked=0, Total=182 [2022-04-06 18:35:34,619 INFO L87 Difference]: Start difference. First operand 45 states and 51 transitions. Second operand has 11 states, 10 states have (on average 2.5) internal successors, (25), 10 states have internal predecessors, (25), 8 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (10), 8 states have call predecessors, (10), 8 states have call successors, (10) [2022-04-06 18:35:34,758 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:35:34,758 INFO L93 Difference]: Finished difference Result 54 states and 62 transitions. [2022-04-06 18:35:34,758 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-04-06 18:35:34,758 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 2.5) internal successors, (25), 10 states have internal predecessors, (25), 8 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (10), 8 states have call predecessors, (10), 8 states have call successors, (10) Word has length 68 [2022-04-06 18:35:34,759 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:35:34,759 INFO L225 Difference]: With dead ends: 54 [2022-04-06 18:35:34,759 INFO L226 Difference]: Without dead ends: 48 [2022-04-06 18:35:34,760 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 87 GetRequests, 72 SyntacticMatches, 1 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=46, Invalid=194, Unknown=0, NotChecked=0, Total=240 [2022-04-06 18:35:34,760 INFO L913 BasicCegarLoop]: 42 mSDtfsCounter, 2 mSDsluCounter, 229 mSDsCounter, 0 mSdLazyCounter, 207 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 271 SdHoareTripleChecker+Invalid, 208 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 207 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 18:35:34,760 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 271 Invalid, 208 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 207 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 18:35:34,760 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2022-04-06 18:35:34,766 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 48. [2022-04-06 18:35:34,766 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 48 states, 30 states have (on average 1.0333333333333334) internal successors, (31), 30 states have internal predecessors, (31), 13 states have call successors, (13), 6 states have call predecessors, (13), 4 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-06 18:35:34,766 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 55 transitions. [2022-04-06 18:35:34,767 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 55 transitions. Word has length 68 [2022-04-06 18:35:34,767 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:35:34,767 INFO L478 AbstractCegarLoop]: Abstraction has 48 states and 55 transitions. [2022-04-06 18:35:34,767 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 2.5) internal successors, (25), 10 states have internal predecessors, (25), 8 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (10), 8 states have call predecessors, (10), 8 states have call successors, (10) [2022-04-06 18:35:34,767 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 55 transitions. [2022-04-06 18:35:34,767 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2022-04-06 18:35:34,768 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:35:34,768 INFO L499 BasicCegarLoop]: trace histogram [9, 8, 8, 7, 7, 7, 6, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:35:34,789 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2022-04-06 18:35:34,979 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:35:34,980 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:35:34,980 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:35:34,980 INFO L85 PathProgramCache]: Analyzing trace with hash -1692754003, now seen corresponding path program 11 times [2022-04-06 18:35:34,980 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:35:34,980 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [366461520] [2022-04-06 18:35:34,980 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 18:35:34,980 INFO L85 PathProgramCache]: Analyzing trace with hash -1692754003, now seen corresponding path program 12 times [2022-04-06 18:35:34,981 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:35:34,981 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [611748654] [2022-04-06 18:35:34,981 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:35:34,981 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:35:34,988 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:35:34,988 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [483126942] [2022-04-06 18:35:34,988 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-04-06 18:35:34,988 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:35:34,988 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:35:34,989 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 18:35:34,990 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2022-04-06 18:35:35,375 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2022-04-06 18:35:35,376 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:35:35,377 INFO L263 TraceCheckSpWp]: Trace formula consists of 198 conjuncts, 34 conjunts are in the unsatisfiable core [2022-04-06 18:35:35,379 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:35:35,620 INFO L134 CoverageAnalysis]: Checked inductivity of 195 backedges. 16 proven. 63 refuted. 0 times theorem prover too weak. 116 trivial. 0 not checked. [2022-04-06 18:35:35,620 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 18:35:36,154 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:35:36,155 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [611748654] [2022-04-06 18:35:36,155 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:35:36,155 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [483126942] [2022-04-06 18:35:36,155 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [483126942] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-06 18:35:36,155 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-06 18:35:36,155 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2022-04-06 18:35:36,155 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:35:36,155 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [366461520] [2022-04-06 18:35:36,155 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [366461520] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:35:36,155 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:35:36,156 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [12] imperfect sequences [] total 12 [2022-04-06 18:35:36,156 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1158082024] [2022-04-06 18:35:36,156 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:35:36,156 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-04-06 18:35:36,156 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:35:36,156 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-04-06 18:35:36,156 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=81, Invalid=299, Unknown=0, NotChecked=0, Total=380 [2022-04-06 18:35:36,157 INFO L87 Difference]: Start difference. First operand 48 states and 55 transitions. Second operand has 12 states, 11 states have (on average 2.4545454545454546) internal successors, (27), 11 states have internal predecessors, (27), 9 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (11), 9 states have call predecessors, (11), 9 states have call successors, (11) [2022-04-06 18:35:36,349 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:35:36,349 INFO L93 Difference]: Finished difference Result 57 states and 66 transitions. [2022-04-06 18:35:36,349 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-04-06 18:35:36,349 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 2.4545454545454546) internal successors, (27), 11 states have internal predecessors, (27), 9 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (11), 9 states have call predecessors, (11), 9 states have call successors, (11) Word has length 75 [2022-04-06 18:35:36,349 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:35:36,350 INFO L225 Difference]: With dead ends: 57 [2022-04-06 18:35:36,350 INFO L226 Difference]: Without dead ends: 51 [2022-04-06 18:35:36,350 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 129 GetRequests, 108 SyntacticMatches, 1 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=91, Invalid=371, Unknown=0, NotChecked=0, Total=462 [2022-04-06 18:35:36,351 INFO L913 BasicCegarLoop]: 45 mSDtfsCounter, 2 mSDsluCounter, 255 mSDsCounter, 0 mSdLazyCounter, 269 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 300 SdHoareTripleChecker+Invalid, 270 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 269 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-04-06 18:35:36,351 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 300 Invalid, 270 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 269 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-04-06 18:35:36,351 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2022-04-06 18:35:36,357 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 51. [2022-04-06 18:35:36,357 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 51 states, 32 states have (on average 1.03125) internal successors, (33), 32 states have internal predecessors, (33), 14 states have call successors, (14), 6 states have call predecessors, (14), 4 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-06 18:35:36,358 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 59 transitions. [2022-04-06 18:35:36,358 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 59 transitions. Word has length 75 [2022-04-06 18:35:36,358 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:35:36,358 INFO L478 AbstractCegarLoop]: Abstraction has 51 states and 59 transitions. [2022-04-06 18:35:36,358 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 2.4545454545454546) internal successors, (27), 11 states have internal predecessors, (27), 9 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (11), 9 states have call predecessors, (11), 9 states have call successors, (11) [2022-04-06 18:35:36,358 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 59 transitions. [2022-04-06 18:35:36,359 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 83 [2022-04-06 18:35:36,359 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:35:36,359 INFO L499 BasicCegarLoop]: trace histogram [10, 9, 9, 8, 8, 8, 7, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:35:36,367 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2022-04-06 18:35:36,563 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2022-04-06 18:35:36,564 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:35:36,564 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:35:36,565 INFO L85 PathProgramCache]: Analyzing trace with hash 615143773, now seen corresponding path program 13 times [2022-04-06 18:35:36,565 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:35:36,565 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [471320660] [2022-04-06 18:35:36,565 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 18:35:36,565 INFO L85 PathProgramCache]: Analyzing trace with hash 615143773, now seen corresponding path program 14 times [2022-04-06 18:35:36,565 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:35:36,565 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1529189422] [2022-04-06 18:35:36,565 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:35:36,566 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:35:36,573 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:35:36,573 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [483969688] [2022-04-06 18:35:36,573 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 18:35:36,573 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:35:36,573 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:35:36,574 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 18:35:36,576 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2022-04-06 18:35:37,315 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 18:35:37,315 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:35:37,316 INFO L263 TraceCheckSpWp]: Trace formula consists of 215 conjuncts, 36 conjunts are in the unsatisfiable core [2022-04-06 18:35:37,318 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:35:37,597 INFO L134 CoverageAnalysis]: Checked inductivity of 250 backedges. 18 proven. 84 refuted. 0 times theorem prover too weak. 148 trivial. 0 not checked. [2022-04-06 18:35:37,597 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 18:35:37,783 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:35:37,784 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1529189422] [2022-04-06 18:35:37,784 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:35:37,784 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [483969688] [2022-04-06 18:35:37,784 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [483969688] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-06 18:35:37,784 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-06 18:35:37,784 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2022-04-06 18:35:37,784 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:35:37,784 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [471320660] [2022-04-06 18:35:37,784 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [471320660] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:35:37,784 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:35:37,784 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [13] imperfect sequences [] total 13 [2022-04-06 18:35:37,784 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2037859994] [2022-04-06 18:35:37,784 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:35:37,785 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2022-04-06 18:35:37,785 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:35:37,785 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2022-04-06 18:35:37,785 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=42, Invalid=198, Unknown=0, NotChecked=0, Total=240 [2022-04-06 18:35:37,785 INFO L87 Difference]: Start difference. First operand 51 states and 59 transitions. Second operand has 13 states, 12 states have (on average 2.4166666666666665) internal successors, (29), 12 states have internal predecessors, (29), 10 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (12), 10 states have call predecessors, (12), 10 states have call successors, (12) [2022-04-06 18:35:37,979 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:35:37,980 INFO L93 Difference]: Finished difference Result 60 states and 70 transitions. [2022-04-06 18:35:37,980 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-04-06 18:35:37,980 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 12 states have (on average 2.4166666666666665) internal successors, (29), 12 states have internal predecessors, (29), 10 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (12), 10 states have call predecessors, (12), 10 states have call successors, (12) Word has length 82 [2022-04-06 18:35:37,980 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:35:37,981 INFO L225 Difference]: With dead ends: 60 [2022-04-06 18:35:37,981 INFO L226 Difference]: Without dead ends: 54 [2022-04-06 18:35:37,981 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 101 GetRequests, 84 SyntacticMatches, 1 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=52, Invalid=254, Unknown=0, NotChecked=0, Total=306 [2022-04-06 18:35:37,981 INFO L913 BasicCegarLoop]: 48 mSDtfsCounter, 2 mSDsluCounter, 303 mSDsCounter, 0 mSdLazyCounter, 317 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 351 SdHoareTripleChecker+Invalid, 318 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 317 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-04-06 18:35:37,982 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 351 Invalid, 318 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 317 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-04-06 18:35:37,982 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2022-04-06 18:35:37,988 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 54. [2022-04-06 18:35:37,988 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 34 states have (on average 1.0294117647058822) internal successors, (35), 34 states have internal predecessors, (35), 15 states have call successors, (15), 6 states have call predecessors, (15), 4 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-06 18:35:37,989 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 63 transitions. [2022-04-06 18:35:37,989 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 63 transitions. Word has length 82 [2022-04-06 18:35:37,989 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:35:37,989 INFO L478 AbstractCegarLoop]: Abstraction has 54 states and 63 transitions. [2022-04-06 18:35:37,989 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 12 states have (on average 2.4166666666666665) internal successors, (29), 12 states have internal predecessors, (29), 10 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (12), 10 states have call predecessors, (12), 10 states have call successors, (12) [2022-04-06 18:35:37,989 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 63 transitions. [2022-04-06 18:35:37,990 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 90 [2022-04-06 18:35:37,990 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:35:37,990 INFO L499 BasicCegarLoop]: trace histogram [11, 10, 10, 9, 9, 9, 8, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:35:37,997 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 18:35:38,195 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2022-04-06 18:35:38,196 INFO L403 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:35:38,196 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:35:38,196 INFO L85 PathProgramCache]: Analyzing trace with hash -1334355539, now seen corresponding path program 15 times [2022-04-06 18:35:38,196 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:35:38,196 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1928194597] [2022-04-06 18:35:38,196 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 18:35:38,196 INFO L85 PathProgramCache]: Analyzing trace with hash -1334355539, now seen corresponding path program 16 times [2022-04-06 18:35:38,196 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:35:38,197 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1033456274] [2022-04-06 18:35:38,197 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:35:38,197 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:35:38,204 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:35:38,204 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [552816011] [2022-04-06 18:35:38,204 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-04-06 18:35:38,204 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:35:38,204 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:35:38,210 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 18:35:38,212 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2022-04-06 18:35:38,249 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-04-06 18:35:38,250 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:35:38,251 INFO L263 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 40 conjunts are in the unsatisfiable core [2022-04-06 18:35:38,252 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:35:38,549 INFO L134 CoverageAnalysis]: Checked inductivity of 312 backedges. 20 proven. 108 refuted. 0 times theorem prover too weak. 184 trivial. 0 not checked. [2022-04-06 18:35:38,549 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 18:35:38,667 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:35:38,668 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1033456274] [2022-04-06 18:35:38,668 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:35:38,668 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [552816011] [2022-04-06 18:35:38,668 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [552816011] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-06 18:35:38,668 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-06 18:35:38,668 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14] total 14 [2022-04-06 18:35:38,668 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:35:38,668 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1928194597] [2022-04-06 18:35:38,668 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1928194597] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:35:38,668 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:35:38,668 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [14] imperfect sequences [] total 14 [2022-04-06 18:35:38,668 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [565031389] [2022-04-06 18:35:38,668 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:35:38,669 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2022-04-06 18:35:38,669 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:35:38,669 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-04-06 18:35:38,669 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=45, Invalid=227, Unknown=0, NotChecked=0, Total=272 [2022-04-06 18:35:38,669 INFO L87 Difference]: Start difference. First operand 54 states and 63 transitions. Second operand has 14 states, 13 states have (on average 2.3846153846153846) internal successors, (31), 13 states have internal predecessors, (31), 11 states have call successors, (15), 2 states have call predecessors, (15), 1 states have return successors, (13), 11 states have call predecessors, (13), 11 states have call successors, (13) [2022-04-06 18:35:38,891 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:35:38,891 INFO L93 Difference]: Finished difference Result 63 states and 74 transitions. [2022-04-06 18:35:38,892 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2022-04-06 18:35:38,892 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 13 states have (on average 2.3846153846153846) internal successors, (31), 13 states have internal predecessors, (31), 11 states have call successors, (15), 2 states have call predecessors, (15), 1 states have return successors, (13), 11 states have call predecessors, (13), 11 states have call successors, (13) Word has length 89 [2022-04-06 18:35:38,892 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:35:38,893 INFO L225 Difference]: With dead ends: 63 [2022-04-06 18:35:38,893 INFO L226 Difference]: Without dead ends: 57 [2022-04-06 18:35:38,893 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 108 GetRequests, 90 SyntacticMatches, 1 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=55, Invalid=287, Unknown=0, NotChecked=0, Total=342 [2022-04-06 18:35:38,894 INFO L913 BasicCegarLoop]: 51 mSDtfsCounter, 2 mSDsluCounter, 343 mSDsCounter, 0 mSdLazyCounter, 381 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 394 SdHoareTripleChecker+Invalid, 382 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 381 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-04-06 18:35:38,894 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 394 Invalid, 382 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 381 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-04-06 18:35:38,894 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 57 states. [2022-04-06 18:35:38,900 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 57 to 57. [2022-04-06 18:35:38,900 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 57 states, 36 states have (on average 1.0277777777777777) internal successors, (37), 36 states have internal predecessors, (37), 16 states have call successors, (16), 6 states have call predecessors, (16), 4 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) [2022-04-06 18:35:38,901 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 67 transitions. [2022-04-06 18:35:38,901 INFO L78 Accepts]: Start accepts. Automaton has 57 states and 67 transitions. Word has length 89 [2022-04-06 18:35:38,901 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:35:38,901 INFO L478 AbstractCegarLoop]: Abstraction has 57 states and 67 transitions. [2022-04-06 18:35:38,901 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 13 states have (on average 2.3846153846153846) internal successors, (31), 13 states have internal predecessors, (31), 11 states have call successors, (15), 2 states have call predecessors, (15), 1 states have return successors, (13), 11 states have call predecessors, (13), 11 states have call successors, (13) [2022-04-06 18:35:38,901 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 67 transitions. [2022-04-06 18:35:38,902 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 97 [2022-04-06 18:35:38,902 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:35:38,902 INFO L499 BasicCegarLoop]: trace histogram [12, 11, 11, 10, 10, 10, 9, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:35:38,921 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2022-04-06 18:35:39,118 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2022-04-06 18:35:39,119 INFO L403 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:35:39,119 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:35:39,119 INFO L85 PathProgramCache]: Analyzing trace with hash 711483229, now seen corresponding path program 17 times [2022-04-06 18:35:39,119 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:35:39,120 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [195273074] [2022-04-06 18:35:39,120 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 18:35:39,120 INFO L85 PathProgramCache]: Analyzing trace with hash 711483229, now seen corresponding path program 18 times [2022-04-06 18:35:39,120 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:35:39,120 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1009679143] [2022-04-06 18:35:39,120 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:35:39,120 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:35:39,127 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:35:39,127 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [913073818] [2022-04-06 18:35:39,127 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-04-06 18:35:39,127 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:35:39,128 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:35:39,128 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 18:35:39,129 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2022-04-06 18:35:39,981 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 10 check-sat command(s) [2022-04-06 18:35:39,982 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:35:39,984 INFO L263 TraceCheckSpWp]: Trace formula consists of 249 conjuncts, 45 conjunts are in the unsatisfiable core [2022-04-06 18:35:39,986 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:35:40,335 INFO L134 CoverageAnalysis]: Checked inductivity of 381 backedges. 22 proven. 135 refuted. 0 times theorem prover too weak. 224 trivial. 0 not checked. [2022-04-06 18:35:40,335 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 18:35:40,882 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:35:40,882 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1009679143] [2022-04-06 18:35:40,882 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:35:40,882 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [913073818] [2022-04-06 18:35:40,882 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [913073818] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-06 18:35:40,882 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-06 18:35:40,882 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2022-04-06 18:35:40,882 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:35:40,883 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [195273074] [2022-04-06 18:35:40,883 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [195273074] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:35:40,883 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:35:40,883 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [15] imperfect sequences [] total 15 [2022-04-06 18:35:40,883 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [146739315] [2022-04-06 18:35:40,883 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:35:40,883 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2022-04-06 18:35:40,883 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:35:40,883 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2022-04-06 18:35:40,884 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=115, Invalid=437, Unknown=0, NotChecked=0, Total=552 [2022-04-06 18:35:40,884 INFO L87 Difference]: Start difference. First operand 57 states and 67 transitions. Second operand has 15 states, 14 states have (on average 2.357142857142857) internal successors, (33), 14 states have internal predecessors, (33), 12 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (14), 12 states have call predecessors, (14), 12 states have call successors, (14) [2022-04-06 18:35:41,164 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:35:41,165 INFO L93 Difference]: Finished difference Result 66 states and 78 transitions. [2022-04-06 18:35:41,165 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2022-04-06 18:35:41,165 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 14 states have (on average 2.357142857142857) internal successors, (33), 14 states have internal predecessors, (33), 12 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (14), 12 states have call predecessors, (14), 12 states have call successors, (14) Word has length 96 [2022-04-06 18:35:41,165 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:35:41,166 INFO L225 Difference]: With dead ends: 66 [2022-04-06 18:35:41,166 INFO L226 Difference]: Without dead ends: 60 [2022-04-06 18:35:41,166 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 157 GetRequests, 132 SyntacticMatches, 1 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=125, Invalid=525, Unknown=0, NotChecked=0, Total=650 [2022-04-06 18:35:41,166 INFO L913 BasicCegarLoop]: 54 mSDtfsCounter, 2 mSDsluCounter, 373 mSDsCounter, 0 mSdLazyCounter, 463 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 427 SdHoareTripleChecker+Invalid, 464 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 463 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-04-06 18:35:41,167 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 427 Invalid, 464 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 463 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-04-06 18:35:41,167 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 60 states. [2022-04-06 18:35:41,176 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 60 to 60. [2022-04-06 18:35:41,177 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 60 states, 38 states have (on average 1.0263157894736843) internal successors, (39), 38 states have internal predecessors, (39), 17 states have call successors, (17), 6 states have call predecessors, (17), 4 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2022-04-06 18:35:41,177 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 60 states to 60 states and 71 transitions. [2022-04-06 18:35:41,178 INFO L78 Accepts]: Start accepts. Automaton has 60 states and 71 transitions. Word has length 96 [2022-04-06 18:35:41,178 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:35:41,178 INFO L478 AbstractCegarLoop]: Abstraction has 60 states and 71 transitions. [2022-04-06 18:35:41,178 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 14 states have (on average 2.357142857142857) internal successors, (33), 14 states have internal predecessors, (33), 12 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (14), 12 states have call predecessors, (14), 12 states have call successors, (14) [2022-04-06 18:35:41,178 INFO L276 IsEmpty]: Start isEmpty. Operand 60 states and 71 transitions. [2022-04-06 18:35:41,179 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 104 [2022-04-06 18:35:41,179 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:35:41,179 INFO L499 BasicCegarLoop]: trace histogram [13, 12, 12, 11, 11, 11, 10, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:35:41,188 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2022-04-06 18:35:41,385 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2022-04-06 18:35:41,386 INFO L403 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:35:41,386 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:35:41,386 INFO L85 PathProgramCache]: Analyzing trace with hash -1610181715, now seen corresponding path program 19 times [2022-04-06 18:35:41,386 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:35:41,386 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [592307964] [2022-04-06 18:35:41,386 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 18:35:41,386 INFO L85 PathProgramCache]: Analyzing trace with hash -1610181715, now seen corresponding path program 20 times [2022-04-06 18:35:41,387 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:35:41,387 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1762252107] [2022-04-06 18:35:41,387 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:35:41,387 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:35:41,402 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:35:41,402 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1485840153] [2022-04-06 18:35:41,403 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 18:35:41,403 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:35:41,403 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:35:41,415 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 18:35:41,417 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2022-04-06 18:35:42,403 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 18:35:42,403 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:35:42,405 INFO L263 TraceCheckSpWp]: Trace formula consists of 266 conjuncts, 48 conjunts are in the unsatisfiable core [2022-04-06 18:35:42,407 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:35:42,731 INFO L134 CoverageAnalysis]: Checked inductivity of 457 backedges. 24 proven. 165 refuted. 0 times theorem prover too weak. 268 trivial. 0 not checked. [2022-04-06 18:35:42,731 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 18:35:42,906 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:35:42,906 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1762252107] [2022-04-06 18:35:42,906 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:35:42,906 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1485840153] [2022-04-06 18:35:42,906 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1485840153] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-06 18:35:42,906 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-06 18:35:42,906 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16] total 16 [2022-04-06 18:35:42,907 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:35:42,907 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [592307964] [2022-04-06 18:35:42,907 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [592307964] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:35:42,907 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:35:42,907 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [16] imperfect sequences [] total 16 [2022-04-06 18:35:42,907 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [665404145] [2022-04-06 18:35:42,907 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:35:42,907 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2022-04-06 18:35:42,907 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:35:42,907 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2022-04-06 18:35:42,908 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=51, Invalid=291, Unknown=0, NotChecked=0, Total=342 [2022-04-06 18:35:42,908 INFO L87 Difference]: Start difference. First operand 60 states and 71 transitions. Second operand has 16 states, 15 states have (on average 2.3333333333333335) internal successors, (35), 15 states have internal predecessors, (35), 13 states have call successors, (17), 2 states have call predecessors, (17), 1 states have return successors, (15), 13 states have call predecessors, (15), 13 states have call successors, (15) [2022-04-06 18:35:43,218 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:35:43,218 INFO L93 Difference]: Finished difference Result 69 states and 82 transitions. [2022-04-06 18:35:43,218 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2022-04-06 18:35:43,219 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 15 states have (on average 2.3333333333333335) internal successors, (35), 15 states have internal predecessors, (35), 13 states have call successors, (17), 2 states have call predecessors, (17), 1 states have return successors, (15), 13 states have call predecessors, (15), 13 states have call successors, (15) Word has length 103 [2022-04-06 18:35:43,219 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:35:43,219 INFO L225 Difference]: With dead ends: 69 [2022-04-06 18:35:43,219 INFO L226 Difference]: Without dead ends: 63 [2022-04-06 18:35:43,220 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 122 GetRequests, 102 SyntacticMatches, 1 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=61, Invalid=359, Unknown=0, NotChecked=0, Total=420 [2022-04-06 18:35:43,220 INFO L913 BasicCegarLoop]: 57 mSDtfsCounter, 2 mSDsluCounter, 429 mSDsCounter, 0 mSdLazyCounter, 527 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 486 SdHoareTripleChecker+Invalid, 528 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 527 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-04-06 18:35:43,220 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 486 Invalid, 528 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 527 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-04-06 18:35:43,220 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2022-04-06 18:35:43,226 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 63. [2022-04-06 18:35:43,227 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 63 states, 40 states have (on average 1.025) internal successors, (41), 40 states have internal predecessors, (41), 18 states have call successors, (18), 6 states have call predecessors, (18), 4 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2022-04-06 18:35:43,227 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 75 transitions. [2022-04-06 18:35:43,227 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 75 transitions. Word has length 103 [2022-04-06 18:35:43,227 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:35:43,227 INFO L478 AbstractCegarLoop]: Abstraction has 63 states and 75 transitions. [2022-04-06 18:35:43,227 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 15 states have (on average 2.3333333333333335) internal successors, (35), 15 states have internal predecessors, (35), 13 states have call successors, (17), 2 states have call predecessors, (17), 1 states have return successors, (15), 13 states have call predecessors, (15), 13 states have call successors, (15) [2022-04-06 18:35:43,228 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 75 transitions. [2022-04-06 18:35:43,228 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 111 [2022-04-06 18:35:43,228 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:35:43,228 INFO L499 BasicCegarLoop]: trace histogram [14, 13, 13, 12, 12, 12, 11, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:35:43,235 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2022-04-06 18:35:43,435 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2022-04-06 18:35:43,436 INFO L403 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:35:43,436 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:35:43,436 INFO L85 PathProgramCache]: Analyzing trace with hash 1881400669, now seen corresponding path program 21 times [2022-04-06 18:35:43,436 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:35:43,436 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [999594992] [2022-04-06 18:35:43,436 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 18:35:43,436 INFO L85 PathProgramCache]: Analyzing trace with hash 1881400669, now seen corresponding path program 22 times [2022-04-06 18:35:43,437 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:35:43,437 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [867256031] [2022-04-06 18:35:43,437 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:35:43,437 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:35:43,445 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:35:43,445 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [170813287] [2022-04-06 18:35:43,445 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-04-06 18:35:43,445 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:35:43,445 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:35:43,446 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 18:35:43,447 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2022-04-06 18:35:43,490 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-04-06 18:35:43,490 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 18:35:43,492 INFO L263 TraceCheckSpWp]: Trace formula consists of 196 conjuncts, 52 conjunts are in the unsatisfiable core [2022-04-06 18:35:43,493 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 18:35:43,840 INFO L134 CoverageAnalysis]: Checked inductivity of 540 backedges. 26 proven. 198 refuted. 0 times theorem prover too weak. 316 trivial. 0 not checked. [2022-04-06 18:35:43,841 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 18:35:43,972 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 18:35:43,972 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [867256031] [2022-04-06 18:35:43,972 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 18:35:43,972 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [170813287] [2022-04-06 18:35:43,972 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [170813287] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-06 18:35:43,972 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-06 18:35:43,972 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17] total 17 [2022-04-06 18:35:43,973 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 18:35:43,973 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [999594992] [2022-04-06 18:35:43,974 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [999594992] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 18:35:43,974 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 18:35:43,974 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [17] imperfect sequences [] total 17 [2022-04-06 18:35:43,974 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1156452282] [2022-04-06 18:35:43,974 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 18:35:43,974 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2022-04-06 18:35:43,974 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 18:35:43,975 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2022-04-06 18:35:43,975 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=54, Invalid=326, Unknown=0, NotChecked=0, Total=380 [2022-04-06 18:35:43,975 INFO L87 Difference]: Start difference. First operand 63 states and 75 transitions. Second operand has 17 states, 16 states have (on average 2.3125) internal successors, (37), 16 states have internal predecessors, (37), 14 states have call successors, (18), 2 states have call predecessors, (18), 1 states have return successors, (16), 14 states have call predecessors, (16), 14 states have call successors, (16) [2022-04-06 18:35:44,351 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 18:35:44,351 INFO L93 Difference]: Finished difference Result 72 states and 86 transitions. [2022-04-06 18:35:44,353 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2022-04-06 18:35:44,354 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 16 states have (on average 2.3125) internal successors, (37), 16 states have internal predecessors, (37), 14 states have call successors, (18), 2 states have call predecessors, (18), 1 states have return successors, (16), 14 states have call predecessors, (16), 14 states have call successors, (16) Word has length 110 [2022-04-06 18:35:44,354 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 18:35:44,354 INFO L225 Difference]: With dead ends: 72 [2022-04-06 18:35:44,354 INFO L226 Difference]: Without dead ends: 66 [2022-04-06 18:35:44,355 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 129 GetRequests, 108 SyntacticMatches, 1 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=64, Invalid=398, Unknown=0, NotChecked=0, Total=462 [2022-04-06 18:35:44,355 INFO L913 BasicCegarLoop]: 60 mSDtfsCounter, 2 mSDsluCounter, 475 mSDsCounter, 0 mSdLazyCounter, 609 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 535 SdHoareTripleChecker+Invalid, 610 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 609 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-04-06 18:35:44,355 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 535 Invalid, 610 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 609 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-04-06 18:35:44,356 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 66 states. [2022-04-06 18:35:44,363 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 66 to 66. [2022-04-06 18:35:44,364 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 66 states, 42 states have (on average 1.0238095238095237) internal successors, (43), 42 states have internal predecessors, (43), 19 states have call successors, (19), 6 states have call predecessors, (19), 4 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2022-04-06 18:35:44,364 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 66 states to 66 states and 79 transitions. [2022-04-06 18:35:44,365 INFO L78 Accepts]: Start accepts. Automaton has 66 states and 79 transitions. Word has length 110 [2022-04-06 18:35:44,365 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 18:35:44,365 INFO L478 AbstractCegarLoop]: Abstraction has 66 states and 79 transitions. [2022-04-06 18:35:44,365 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 16 states have (on average 2.3125) internal successors, (37), 16 states have internal predecessors, (37), 14 states have call successors, (18), 2 states have call predecessors, (18), 1 states have return successors, (16), 14 states have call predecessors, (16), 14 states have call successors, (16) [2022-04-06 18:35:44,365 INFO L276 IsEmpty]: Start isEmpty. Operand 66 states and 79 transitions. [2022-04-06 18:35:44,366 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 118 [2022-04-06 18:35:44,366 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 18:35:44,366 INFO L499 BasicCegarLoop]: trace histogram [15, 14, 14, 13, 13, 13, 12, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 18:35:44,385 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2022-04-06 18:35:44,582 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2022-04-06 18:35:44,583 INFO L403 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 18:35:44,583 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 18:35:44,583 INFO L85 PathProgramCache]: Analyzing trace with hash 1600671149, now seen corresponding path program 23 times [2022-04-06 18:35:44,583 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 18:35:44,583 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [679340953] [2022-04-06 18:35:44,583 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 18:35:44,583 INFO L85 PathProgramCache]: Analyzing trace with hash 1600671149, now seen corresponding path program 24 times [2022-04-06 18:35:44,583 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 18:35:44,583 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1889313598] [2022-04-06 18:35:44,584 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 18:35:44,584 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 18:35:44,590 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 18:35:44,590 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [688117677] [2022-04-06 18:35:44,590 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-04-06 18:35:44,590 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 18:35:44,590 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 18:35:44,595 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 18:35:44,600 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process