/usr/bin/java -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data --core.log.level.for.class de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN -tc ../../../trunk/examples/toolchains/AutomizerC.xml -s ../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationQvasr_64.epf -i ../../../trunk/examples/svcomp/nla-digbench-scaling/ps5-ll_valuebound50.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-b030c9e [2022-03-20 23:07:28,353 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-03-20 23:07:28,355 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-03-20 23:07:28,395 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-03-20 23:07:28,396 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-03-20 23:07:28,396 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-03-20 23:07:28,398 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-03-20 23:07:28,399 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-03-20 23:07:28,400 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-03-20 23:07:28,401 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-03-20 23:07:28,401 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-03-20 23:07:28,402 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-03-20 23:07:28,402 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-03-20 23:07:28,403 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-03-20 23:07:28,404 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-03-20 23:07:28,405 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-03-20 23:07:28,405 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-03-20 23:07:28,406 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-03-20 23:07:28,407 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-03-20 23:07:28,409 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-03-20 23:07:28,410 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-03-20 23:07:28,410 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-03-20 23:07:28,411 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-03-20 23:07:28,412 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-03-20 23:07:28,413 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-03-20 23:07:28,415 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-03-20 23:07:28,415 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-03-20 23:07:28,415 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-03-20 23:07:28,416 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-03-20 23:07:28,416 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-03-20 23:07:28,417 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-03-20 23:07:28,417 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-03-20 23:07:28,418 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-03-20 23:07:28,418 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-03-20 23:07:28,419 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-03-20 23:07:28,420 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-03-20 23:07:28,420 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-03-20 23:07:28,420 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-03-20 23:07:28,420 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-03-20 23:07:28,421 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-03-20 23:07:28,421 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-03-20 23:07:28,422 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-03-20 23:07:28,422 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationQvasr_64.epf [2022-03-20 23:07:28,429 INFO L113 SettingsManager]: Loading preferences was successful [2022-03-20 23:07:28,430 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-03-20 23:07:28,431 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-03-20 23:07:28,431 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-03-20 23:07:28,431 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-03-20 23:07:28,431 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-03-20 23:07:28,431 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-03-20 23:07:28,432 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-03-20 23:07:28,432 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-03-20 23:07:28,432 INFO L138 SettingsManager]: * Use constant arrays=true [2022-03-20 23:07:28,432 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-03-20 23:07:28,432 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-03-20 23:07:28,432 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-03-20 23:07:28,432 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-03-20 23:07:28,433 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-03-20 23:07:28,433 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-20 23:07:28,433 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-03-20 23:07:28,433 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_NestedInterpolation [2022-03-20 23:07:28,433 INFO L138 SettingsManager]: * Trace refinement strategy=ACCELERATED_INTERPOLATION [2022-03-20 23:07:28,433 INFO L138 SettingsManager]: * Trace refinement strategy used in Accelerated Interpolation=CAMEL [2022-03-20 23:07:28,433 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-03-20 23:07:28,433 INFO L138 SettingsManager]: * Loop acceleration method that is used by accelerated interpolation=QVASR [2022-03-20 23:07:28,434 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-03-20 23:07:28,718 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-03-20 23:07:28,744 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-03-20 23:07:28,746 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-03-20 23:07:28,747 INFO L271 PluginConnector]: Initializing CDTParser... [2022-03-20 23:07:28,747 INFO L275 PluginConnector]: CDTParser initialized [2022-03-20 23:07:28,749 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/ps5-ll_valuebound50.c [2022-03-20 23:07:28,803 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/ca90f1086/19a39596f9b54a0aac2a105ca762684a/FLAG6a3736d97 [2022-03-20 23:07:29,414 INFO L306 CDTParser]: Found 1 translation units. [2022-03-20 23:07:29,443 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/ps5-ll_valuebound50.c [2022-03-20 23:07:29,449 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/ca90f1086/19a39596f9b54a0aac2a105ca762684a/FLAG6a3736d97 [2022-03-20 23:07:29,850 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/ca90f1086/19a39596f9b54a0aac2a105ca762684a [2022-03-20 23:07:29,853 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-03-20 23:07:29,855 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-03-20 23:07:29,857 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-03-20 23:07:29,857 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-03-20 23:07:29,861 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-03-20 23:07:29,861 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.03 11:07:29" (1/1) ... [2022-03-20 23:07:29,863 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@4facf2f6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 11:07:29, skipping insertion in model container [2022-03-20 23:07:29,863 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.03 11:07:29" (1/1) ... [2022-03-20 23:07:29,868 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-03-20 23:07:29,897 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-03-20 23:07:30,058 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/ps5-ll_valuebound50.c[458,471] [2022-03-20 23:07:30,091 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-20 23:07:30,100 INFO L203 MainTranslator]: Completed pre-run [2022-03-20 23:07:30,109 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/ps5-ll_valuebound50.c[458,471] [2022-03-20 23:07:30,116 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-20 23:07:30,132 INFO L208 MainTranslator]: Completed translation [2022-03-20 23:07:30,132 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 11:07:30 WrapperNode [2022-03-20 23:07:30,132 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-03-20 23:07:30,134 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-03-20 23:07:30,134 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-03-20 23:07:30,134 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-03-20 23:07:30,144 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 11:07:30" (1/1) ... [2022-03-20 23:07:30,144 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 11:07:30" (1/1) ... [2022-03-20 23:07:30,151 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 11:07:30" (1/1) ... [2022-03-20 23:07:30,152 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 11:07:30" (1/1) ... [2022-03-20 23:07:30,162 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 11:07:30" (1/1) ... [2022-03-20 23:07:30,165 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 11:07:30" (1/1) ... [2022-03-20 23:07:30,168 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 11:07:30" (1/1) ... [2022-03-20 23:07:30,173 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-03-20 23:07:30,174 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-03-20 23:07:30,175 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-03-20 23:07:30,175 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-03-20 23:07:30,176 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 11:07:30" (1/1) ... [2022-03-20 23:07:30,181 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-20 23:07:30,190 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 23:07:30,201 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-03-20 23:07:30,219 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-03-20 23:07:30,239 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-03-20 23:07:30,239 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-03-20 23:07:30,239 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-03-20 23:07:30,239 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-03-20 23:07:30,239 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-03-20 23:07:30,240 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-03-20 23:07:30,240 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-03-20 23:07:30,240 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-03-20 23:07:30,240 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-03-20 23:07:30,240 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-03-20 23:07:30,240 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_short [2022-03-20 23:07:30,240 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-03-20 23:07:30,241 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-03-20 23:07:30,241 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-03-20 23:07:30,241 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-03-20 23:07:30,242 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-03-20 23:07:30,242 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-03-20 23:07:30,242 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-03-20 23:07:30,242 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-03-20 23:07:30,242 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-03-20 23:07:30,293 INFO L234 CfgBuilder]: Building ICFG [2022-03-20 23:07:30,295 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-03-20 23:07:30,429 INFO L275 CfgBuilder]: Performing block encoding [2022-03-20 23:07:30,433 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-03-20 23:07:30,433 INFO L299 CfgBuilder]: Removed 1 assume(true) statements. [2022-03-20 23:07:30,435 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.03 11:07:30 BoogieIcfgContainer [2022-03-20 23:07:30,435 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-03-20 23:07:30,436 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-03-20 23:07:30,436 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-03-20 23:07:30,439 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-03-20 23:07:30,439 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 20.03 11:07:29" (1/3) ... [2022-03-20 23:07:30,440 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@c2625f9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.03 11:07:30, skipping insertion in model container [2022-03-20 23:07:30,440 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 11:07:30" (2/3) ... [2022-03-20 23:07:30,440 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@c2625f9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.03 11:07:30, skipping insertion in model container [2022-03-20 23:07:30,440 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.03 11:07:30" (3/3) ... [2022-03-20 23:07:30,441 INFO L111 eAbstractionObserver]: Analyzing ICFG ps5-ll_valuebound50.c [2022-03-20 23:07:30,445 INFO L205 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:Craig_NestedInterpolation Determinization: PREDICATE_ABSTRACTION [2022-03-20 23:07:30,445 INFO L164 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-03-20 23:07:30,477 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-03-20 23:07:30,482 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-03-20 23:07:30,483 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-03-20 23:07:30,493 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-03-20 23:07:30,498 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2022-03-20 23:07:30,499 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 23:07:30,499 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-03-20 23:07:30,500 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 23:07:30,503 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 23:07:30,504 INFO L85 PathProgramCache]: Analyzing trace with hash 1098891495, now seen corresponding path program 1 times [2022-03-20 23:07:30,510 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 23:07:30,510 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1186134242] [2022-03-20 23:07:30,518 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 23:07:30,519 INFO L85 PathProgramCache]: Analyzing trace with hash 1098891495, now seen corresponding path program 2 times [2022-03-20 23:07:30,521 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 23:07:30,521 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [67158019] [2022-03-20 23:07:30,521 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 23:07:30,522 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 23:07:30,588 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 23:07:30,645 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-20 23:07:30,651 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 23:07:30,657 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-03-20 23:07:30,659 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 23:07:30,665 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2022-03-20 23:07:30,667 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 23:07:30,677 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-20 23:07:30,677 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 23:07:30,678 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [67158019] [2022-03-20 23:07:30,678 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [67158019] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 23:07:30,679 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 23:07:30,679 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-03-20 23:07:30,681 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 23:07:30,681 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1186134242] [2022-03-20 23:07:30,681 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1186134242] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 23:07:30,681 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 23:07:30,682 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-03-20 23:07:30,682 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1298026124] [2022-03-20 23:07:30,682 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 23:07:30,686 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-03-20 23:07:30,686 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 23:07:30,712 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-03-20 23:07:30,713 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-03-20 23:07:30,715 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-03-20 23:07:30,809 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 23:07:30,809 INFO L93 Difference]: Finished difference Result 51 states and 69 transitions. [2022-03-20 23:07:30,811 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-03-20 23:07:30,812 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-03-20 23:07:30,812 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 23:07:30,826 INFO L225 Difference]: With dead ends: 51 [2022-03-20 23:07:30,826 INFO L226 Difference]: Without dead ends: 24 [2022-03-20 23:07:30,829 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-03-20 23:07:30,834 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.1s IncrementalHoareTripleChecker+Time [2022-03-20 23:07:30,836 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.1s Time] [2022-03-20 23:07:30,848 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states. [2022-03-20 23:07:30,865 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2022-03-20 23:07:30,866 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-03-20 23:07:30,867 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 27 transitions. [2022-03-20 23:07:30,868 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 27 transitions. Word has length 22 [2022-03-20 23:07:30,869 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 23:07:30,869 INFO L478 AbstractCegarLoop]: Abstraction has 24 states and 27 transitions. [2022-03-20 23:07:30,869 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-03-20 23:07:30,869 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 27 transitions. [2022-03-20 23:07:30,871 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2022-03-20 23:07:30,871 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 23:07:30,871 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-03-20 23:07:30,872 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-03-20 23:07:30,872 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 23:07:30,874 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 23:07:30,875 INFO L85 PathProgramCache]: Analyzing trace with hash 769620075, now seen corresponding path program 1 times [2022-03-20 23:07:30,875 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 23:07:30,875 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1217917080] [2022-03-20 23:07:30,879 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 23:07:30,880 INFO L85 PathProgramCache]: Analyzing trace with hash 769620075, now seen corresponding path program 2 times [2022-03-20 23:07:30,880 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 23:07:30,880 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1925920023] [2022-03-20 23:07:30,880 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 23:07:30,880 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 23:07:30,910 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 23:07:30,911 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1813200272] [2022-03-20 23:07:30,911 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 23:07:30,911 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 23:07:30,912 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 23:07:30,918 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-03-20 23:07:30,982 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-03-20 23:07:31,001 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2022-03-20 23:07:31,002 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 23:07:31,005 INFO L263 TraceCheckSpWp]: Trace formula consists of 68 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-20 23:07:31,009 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 23:07:31,271 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-20 23:07:31,272 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-20 23:07:31,272 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 23:07:31,272 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1925920023] [2022-03-20 23:07:31,272 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 23:07:31,272 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1813200272] [2022-03-20 23:07:31,273 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1813200272] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 23:07:31,273 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 23:07:31,273 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-20 23:07:31,274 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 23:07:31,274 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1217917080] [2022-03-20 23:07:31,274 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1217917080] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 23:07:31,274 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 23:07:31,274 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-20 23:07:31,274 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [14030507] [2022-03-20 23:07:31,274 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 23:07:31,275 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-20 23:07:31,275 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 23:07:31,275 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-20 23:07:31,275 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-03-20 23:07:31,276 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-03-20 23:07:31,337 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 23:07:31,337 INFO L93 Difference]: Finished difference Result 35 states and 40 transitions. [2022-03-20 23:07:31,337 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-20 23:07:31,337 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-03-20 23:07:31,338 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 23:07:31,346 INFO L225 Difference]: With dead ends: 35 [2022-03-20 23:07:31,346 INFO L226 Difference]: Without dead ends: 31 [2022-03-20 23:07:31,346 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-03-20 23:07:31,347 INFO L913 BasicCegarLoop]: 24 mSDtfsCounter, 6 mSDsluCounter, 67 mSDsCounter, 0 mSdLazyCounter, 22 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 91 SdHoareTripleChecker+Invalid, 24 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 22 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 23:07:31,348 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [8 Valid, 91 Invalid, 24 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 22 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 23:07:31,348 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2022-03-20 23:07:31,354 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 31. [2022-03-20 23:07:31,355 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-03-20 23:07:31,356 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 34 transitions. [2022-03-20 23:07:31,356 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 34 transitions. Word has length 22 [2022-03-20 23:07:31,356 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 23:07:31,356 INFO L478 AbstractCegarLoop]: Abstraction has 31 states and 34 transitions. [2022-03-20 23:07:31,356 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-03-20 23:07:31,356 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 34 transitions. [2022-03-20 23:07:31,357 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2022-03-20 23:07:31,357 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 23:07:31,357 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-03-20 23:07:31,380 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-03-20 23:07:31,578 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-03-20 23:07:31,579 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 23:07:31,579 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 23:07:31,579 INFO L85 PathProgramCache]: Analyzing trace with hash 645812411, now seen corresponding path program 1 times [2022-03-20 23:07:31,579 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 23:07:31,579 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [825726264] [2022-03-20 23:07:31,580 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 23:07:31,580 INFO L85 PathProgramCache]: Analyzing trace with hash 645812411, now seen corresponding path program 2 times [2022-03-20 23:07:31,580 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 23:07:31,580 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [743634043] [2022-03-20 23:07:31,580 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 23:07:31,581 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 23:07:31,591 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 23:07:31,591 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1111789808] [2022-03-20 23:07:31,591 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 23:07:31,591 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 23:07:31,591 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 23:07:31,593 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-03-20 23:07:31,594 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-03-20 23:07:31,650 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 23:07:31,651 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 23:07:31,652 INFO L263 TraceCheckSpWp]: Trace formula consists of 94 conjuncts, 11 conjunts are in the unsatisfiable core [2022-03-20 23:07:31,654 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 23:07:31,770 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-20 23:07:31,770 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 23:07:31,918 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2022-03-20 23:07:31,919 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 23:07:31,919 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [743634043] [2022-03-20 23:07:31,919 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 23:07:31,919 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1111789808] [2022-03-20 23:07:31,919 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1111789808] provided 1 perfect and 1 imperfect interpolant sequences [2022-03-20 23:07:31,920 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-03-20 23:07:31,920 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2022-03-20 23:07:31,920 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 23:07:31,920 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [825726264] [2022-03-20 23:07:31,920 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [825726264] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 23:07:31,920 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 23:07:31,920 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-20 23:07:31,921 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1062722331] [2022-03-20 23:07:31,921 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 23:07:31,921 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-20 23:07:31,921 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 23:07:31,921 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-20 23:07:31,922 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2022-03-20 23:07:31,922 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-03-20 23:07:33,997 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 23:07:34,064 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 23:07:34,064 INFO L93 Difference]: Finished difference Result 37 states and 39 transitions. [2022-03-20 23:07:34,064 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-20 23:07:34,064 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-03-20 23:07:34,065 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 23:07:34,065 INFO L225 Difference]: With dead ends: 37 [2022-03-20 23:07:34,065 INFO L226 Difference]: Without dead ends: 33 [2022-03-20 23:07:34,066 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 58 GetRequests, 50 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2022-03-20 23:07:34,067 INFO L913 BasicCegarLoop]: 22 mSDtfsCounter, 6 mSDsluCounter, 59 mSDsCounter, 0 mSdLazyCounter, 18 mSolverCounterSat, 1 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 81 SdHoareTripleChecker+Invalid, 20 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 18 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.1s IncrementalHoareTripleChecker+Time [2022-03-20 23:07:34,067 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [7 Valid, 81 Invalid, 20 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 18 Invalid, 1 Unknown, 0 Unchecked, 2.1s Time] [2022-03-20 23:07:34,068 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2022-03-20 23:07:34,076 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 33. [2022-03-20 23:07:34,077 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-03-20 23:07:34,077 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 35 transitions. [2022-03-20 23:07:34,078 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 35 transitions. Word has length 29 [2022-03-20 23:07:34,078 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 23:07:34,078 INFO L478 AbstractCegarLoop]: Abstraction has 33 states and 35 transitions. [2022-03-20 23:07:34,078 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-03-20 23:07:34,078 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 35 transitions. [2022-03-20 23:07:34,079 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2022-03-20 23:07:34,079 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 23:07:34,079 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-03-20 23:07:34,084 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2022-03-20 23:07:34,280 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-03-20 23:07:34,280 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 23:07:34,281 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 23:07:34,281 INFO L85 PathProgramCache]: Analyzing trace with hash 463554397, now seen corresponding path program 1 times [2022-03-20 23:07:34,281 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 23:07:34,281 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [997706235] [2022-03-20 23:07:34,282 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 23:07:34,282 INFO L85 PathProgramCache]: Analyzing trace with hash 463554397, now seen corresponding path program 2 times [2022-03-20 23:07:34,282 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 23:07:34,282 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1429813854] [2022-03-20 23:07:34,282 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 23:07:34,283 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 23:07:34,297 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 23:07:34,297 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1793444832] [2022-03-20 23:07:34,298 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 23:07:34,298 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 23:07:34,298 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 23:07:34,306 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-03-20 23:07:34,307 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-03-20 23:07:34,350 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 23:07:34,351 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 23:07:34,352 INFO L263 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 12 conjunts are in the unsatisfiable core [2022-03-20 23:07:34,353 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 23:07:34,508 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 6 proven. 3 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2022-03-20 23:07:34,508 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 23:07:34,721 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 23:07:34,721 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1429813854] [2022-03-20 23:07:34,721 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 23:07:34,721 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1793444832] [2022-03-20 23:07:34,722 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1793444832] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 23:07:34,722 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 23:07:34,722 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2022-03-20 23:07:34,722 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 23:07:34,722 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [997706235] [2022-03-20 23:07:34,722 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [997706235] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 23:07:34,723 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 23:07:34,723 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2022-03-20 23:07:34,723 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [595322425] [2022-03-20 23:07:34,723 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 23:07:34,723 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-03-20 23:07:34,723 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 23:07:34,724 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-03-20 23:07:34,724 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=66, Unknown=0, NotChecked=0, Total=90 [2022-03-20 23:07:34,724 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-03-20 23:07:34,811 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 23:07:34,811 INFO L93 Difference]: Finished difference Result 42 states and 46 transitions. [2022-03-20 23:07:34,812 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-03-20 23:07:34,812 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-03-20 23:07:34,813 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 23:07:34,815 INFO L225 Difference]: With dead ends: 42 [2022-03-20 23:07:34,815 INFO L226 Difference]: Without dead ends: 36 [2022-03-20 23:07:34,818 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-03-20 23:07:34,821 INFO L913 BasicCegarLoop]: 30 mSDtfsCounter, 2 mSDsluCounter, 125 mSDsCounter, 0 mSdLazyCounter, 39 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 155 SdHoareTripleChecker+Invalid, 40 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 39 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 23:07:34,822 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 155 Invalid, 40 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 23:07:34,825 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36 states. [2022-03-20 23:07:34,837 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36 to 36. [2022-03-20 23:07:34,838 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-03-20 23:07:34,844 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 39 transitions. [2022-03-20 23:07:34,844 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 39 transitions. Word has length 40 [2022-03-20 23:07:34,844 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 23:07:34,845 INFO L478 AbstractCegarLoop]: Abstraction has 36 states and 39 transitions. [2022-03-20 23:07:34,845 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-03-20 23:07:34,845 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 39 transitions. [2022-03-20 23:07:34,848 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2022-03-20 23:07:34,848 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 23:07:34,848 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-03-20 23:07:34,869 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-03-20 23:07:35,066 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-03-20 23:07:35,067 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 23:07:35,068 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 23:07:35,068 INFO L85 PathProgramCache]: Analyzing trace with hash 1886956461, now seen corresponding path program 3 times [2022-03-20 23:07:35,068 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 23:07:35,068 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [718434186] [2022-03-20 23:07:35,069 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 23:07:35,069 INFO L85 PathProgramCache]: Analyzing trace with hash 1886956461, now seen corresponding path program 4 times [2022-03-20 23:07:35,069 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 23:07:35,069 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [350100342] [2022-03-20 23:07:35,069 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 23:07:35,069 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 23:07:35,079 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 23:07:35,079 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1767381870] [2022-03-20 23:07:35,079 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-03-20 23:07:35,080 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 23:07:35,080 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 23:07:35,098 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-03-20 23:07:35,160 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-03-20 23:07:35,168 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-03-20 23:07:35,169 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 23:07:35,169 INFO L263 TraceCheckSpWp]: Trace formula consists of 79 conjuncts, 16 conjunts are in the unsatisfiable core [2022-03-20 23:07:35,171 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 23:07:35,351 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 8 proven. 9 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2022-03-20 23:07:35,352 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 23:07:35,499 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 23:07:35,499 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [350100342] [2022-03-20 23:07:35,499 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 23:07:35,499 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1767381870] [2022-03-20 23:07:35,499 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1767381870] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 23:07:35,499 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 23:07:35,499 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8] total 8 [2022-03-20 23:07:35,500 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 23:07:35,500 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [718434186] [2022-03-20 23:07:35,500 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [718434186] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 23:07:35,500 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 23:07:35,500 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2022-03-20 23:07:35,500 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [142895397] [2022-03-20 23:07:35,500 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 23:07:35,500 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-03-20 23:07:35,501 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 23:07:35,501 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-03-20 23:07:35,501 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2022-03-20 23:07:35,501 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-03-20 23:07:35,571 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 23:07:35,571 INFO L93 Difference]: Finished difference Result 45 states and 50 transitions. [2022-03-20 23:07:35,572 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-03-20 23:07:35,572 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-03-20 23:07:35,572 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 23:07:35,573 INFO L225 Difference]: With dead ends: 45 [2022-03-20 23:07:35,573 INFO L226 Difference]: Without dead ends: 39 [2022-03-20 23:07:35,573 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-03-20 23:07:35,574 INFO L913 BasicCegarLoop]: 33 mSDtfsCounter, 2 mSDsluCounter, 162 mSDsCounter, 0 mSdLazyCounter, 58 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 195 SdHoareTripleChecker+Invalid, 59 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 58 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 23:07:35,574 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 195 Invalid, 59 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 58 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 23:07:35,575 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2022-03-20 23:07:35,580 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 39. [2022-03-20 23:07:35,581 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-03-20 23:07:35,581 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 43 transitions. [2022-03-20 23:07:35,581 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 43 transitions. Word has length 47 [2022-03-20 23:07:35,581 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 23:07:35,582 INFO L478 AbstractCegarLoop]: Abstraction has 39 states and 43 transitions. [2022-03-20 23:07:35,582 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-03-20 23:07:35,582 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 43 transitions. [2022-03-20 23:07:35,582 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2022-03-20 23:07:35,582 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 23:07:35,583 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-03-20 23:07:35,618 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-03-20 23:07:35,803 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-03-20 23:07:35,803 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 23:07:35,803 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 23:07:35,803 INFO L85 PathProgramCache]: Analyzing trace with hash -1213805219, now seen corresponding path program 5 times [2022-03-20 23:07:35,804 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 23:07:35,804 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1861452062] [2022-03-20 23:07:35,804 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 23:07:35,804 INFO L85 PathProgramCache]: Analyzing trace with hash -1213805219, now seen corresponding path program 6 times [2022-03-20 23:07:35,804 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 23:07:35,804 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [50895877] [2022-03-20 23:07:35,804 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 23:07:35,805 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 23:07:35,814 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 23:07:35,814 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1811401118] [2022-03-20 23:07:35,814 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-03-20 23:07:35,815 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 23:07:35,815 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 23:07:35,816 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-03-20 23:07:35,844 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-03-20 23:07:36,427 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2022-03-20 23:07:36,428 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 23:07:36,429 INFO L263 TraceCheckSpWp]: Trace formula consists of 147 conjuncts, 20 conjunts are in the unsatisfiable core [2022-03-20 23:07:36,431 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 23:07:36,624 INFO L134 CoverageAnalysis]: Checked inductivity of 72 backedges. 10 proven. 18 refuted. 0 times theorem prover too weak. 44 trivial. 0 not checked. [2022-03-20 23:07:36,626 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 23:07:36,771 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 23:07:36,772 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [50895877] [2022-03-20 23:07:36,772 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 23:07:36,772 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1811401118] [2022-03-20 23:07:36,772 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1811401118] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 23:07:36,772 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 23:07:36,772 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2022-03-20 23:07:36,772 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 23:07:36,773 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1861452062] [2022-03-20 23:07:36,773 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1861452062] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 23:07:36,773 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 23:07:36,773 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2022-03-20 23:07:36,773 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2079333435] [2022-03-20 23:07:36,773 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 23:07:36,773 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-03-20 23:07:36,773 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 23:07:36,774 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-03-20 23:07:36,774 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2022-03-20 23:07:36,774 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-03-20 23:07:36,893 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 23:07:36,893 INFO L93 Difference]: Finished difference Result 48 states and 54 transitions. [2022-03-20 23:07:36,894 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-03-20 23:07:36,895 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-03-20 23:07:36,895 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 23:07:36,895 INFO L225 Difference]: With dead ends: 48 [2022-03-20 23:07:36,895 INFO L226 Difference]: Without dead ends: 42 [2022-03-20 23:07:36,896 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-03-20 23:07:36,896 INFO L913 BasicCegarLoop]: 36 mSDtfsCounter, 2 mSDsluCounter, 203 mSDsCounter, 0 mSdLazyCounter, 81 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 239 SdHoareTripleChecker+Invalid, 82 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 81 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 23:07:36,896 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 239 Invalid, 82 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 81 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 23:07:36,897 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states. [2022-03-20 23:07:36,902 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 42. [2022-03-20 23:07:36,902 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-03-20 23:07:36,902 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 42 states to 42 states and 47 transitions. [2022-03-20 23:07:36,902 INFO L78 Accepts]: Start accepts. Automaton has 42 states and 47 transitions. Word has length 54 [2022-03-20 23:07:36,902 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 23:07:36,902 INFO L478 AbstractCegarLoop]: Abstraction has 42 states and 47 transitions. [2022-03-20 23:07:36,903 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-03-20 23:07:36,903 INFO L276 IsEmpty]: Start isEmpty. Operand 42 states and 47 transitions. [2022-03-20 23:07:36,903 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 62 [2022-03-20 23:07:36,903 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 23:07:36,903 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-03-20 23:07:36,911 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2022-03-20 23:07:37,110 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-03-20 23:07:37,110 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 23:07:37,111 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 23:07:37,111 INFO L85 PathProgramCache]: Analyzing trace with hash 307258797, now seen corresponding path program 7 times [2022-03-20 23:07:37,111 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 23:07:37,111 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [75740385] [2022-03-20 23:07:37,111 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 23:07:37,111 INFO L85 PathProgramCache]: Analyzing trace with hash 307258797, now seen corresponding path program 8 times [2022-03-20 23:07:37,111 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 23:07:37,112 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [723729295] [2022-03-20 23:07:37,112 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 23:07:37,112 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 23:07:37,120 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 23:07:37,120 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [877165041] [2022-03-20 23:07:37,120 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 23:07:37,120 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 23:07:37,120 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 23:07:37,121 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-03-20 23:07:37,129 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-03-20 23:07:37,413 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 23:07:37,414 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 23:07:37,415 INFO L263 TraceCheckSpWp]: Trace formula consists of 164 conjuncts, 24 conjunts are in the unsatisfiable core [2022-03-20 23:07:37,417 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 23:07:37,603 INFO L134 CoverageAnalysis]: Checked inductivity of 106 backedges. 12 proven. 30 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2022-03-20 23:07:37,603 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 23:07:37,721 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 23:07:37,722 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [723729295] [2022-03-20 23:07:37,722 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 23:07:37,722 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [877165041] [2022-03-20 23:07:37,722 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [877165041] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 23:07:37,722 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 23:07:37,722 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2022-03-20 23:07:37,722 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 23:07:37,722 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [75740385] [2022-03-20 23:07:37,722 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [75740385] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 23:07:37,722 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 23:07:37,722 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [] total 10 [2022-03-20 23:07:37,722 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [166705587] [2022-03-20 23:07:37,723 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 23:07:37,723 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-03-20 23:07:37,723 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 23:07:37,723 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-03-20 23:07:37,723 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=123, Unknown=0, NotChecked=0, Total=156 [2022-03-20 23:07:37,723 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-03-20 23:07:37,838 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 23:07:37,838 INFO L93 Difference]: Finished difference Result 51 states and 58 transitions. [2022-03-20 23:07:37,838 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-03-20 23:07:37,839 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-03-20 23:07:37,839 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 23:07:37,839 INFO L225 Difference]: With dead ends: 51 [2022-03-20 23:07:37,839 INFO L226 Difference]: Without dead ends: 45 [2022-03-20 23:07:37,840 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-03-20 23:07:37,840 INFO L913 BasicCegarLoop]: 39 mSDtfsCounter, 2 mSDsluCounter, 248 mSDsCounter, 0 mSdLazyCounter, 108 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 287 SdHoareTripleChecker+Invalid, 109 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 108 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 23:07:37,840 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 287 Invalid, 109 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 108 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 23:07:37,841 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2022-03-20 23:07:37,845 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 45. [2022-03-20 23:07:37,846 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-03-20 23:07:37,846 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 51 transitions. [2022-03-20 23:07:37,846 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 51 transitions. Word has length 61 [2022-03-20 23:07:37,846 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 23:07:37,846 INFO L478 AbstractCegarLoop]: Abstraction has 45 states and 51 transitions. [2022-03-20 23:07:37,846 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-03-20 23:07:37,847 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 51 transitions. [2022-03-20 23:07:37,847 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 69 [2022-03-20 23:07:37,847 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 23:07:37,847 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-03-20 23:07:37,867 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2022-03-20 23:07:38,053 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-03-20 23:07:38,053 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 23:07:38,054 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 23:07:38,054 INFO L85 PathProgramCache]: Analyzing trace with hash 1082774365, now seen corresponding path program 9 times [2022-03-20 23:07:38,054 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 23:07:38,054 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [78421157] [2022-03-20 23:07:38,054 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 23:07:38,054 INFO L85 PathProgramCache]: Analyzing trace with hash 1082774365, now seen corresponding path program 10 times [2022-03-20 23:07:38,054 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 23:07:38,054 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1286352704] [2022-03-20 23:07:38,054 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 23:07:38,055 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 23:07:38,061 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 23:07:38,062 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [539291782] [2022-03-20 23:07:38,062 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-03-20 23:07:38,062 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 23:07:38,062 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 23:07:38,063 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-03-20 23:07:38,064 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-03-20 23:07:38,094 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-03-20 23:07:38,094 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 23:07:38,095 INFO L263 TraceCheckSpWp]: Trace formula consists of 118 conjuncts, 28 conjunts are in the unsatisfiable core [2022-03-20 23:07:38,096 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 23:07:38,289 INFO L134 CoverageAnalysis]: Checked inductivity of 147 backedges. 14 proven. 45 refuted. 0 times theorem prover too weak. 88 trivial. 0 not checked. [2022-03-20 23:07:38,289 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 23:07:38,410 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 23:07:38,411 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1286352704] [2022-03-20 23:07:38,411 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 23:07:38,411 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [539291782] [2022-03-20 23:07:38,411 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [539291782] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 23:07:38,411 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 23:07:38,411 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2022-03-20 23:07:38,411 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 23:07:38,412 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [78421157] [2022-03-20 23:07:38,412 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [78421157] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 23:07:38,412 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 23:07:38,412 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [11] imperfect sequences [] total 11 [2022-03-20 23:07:38,412 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1727743195] [2022-03-20 23:07:38,412 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 23:07:38,412 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2022-03-20 23:07:38,412 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 23:07:38,412 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2022-03-20 23:07:38,413 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=36, Invalid=146, Unknown=0, NotChecked=0, Total=182 [2022-03-20 23:07:38,413 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-03-20 23:07:38,544 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 23:07:38,545 INFO L93 Difference]: Finished difference Result 54 states and 62 transitions. [2022-03-20 23:07:38,545 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-03-20 23:07:38,545 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-03-20 23:07:38,545 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 23:07:38,546 INFO L225 Difference]: With dead ends: 54 [2022-03-20 23:07:38,546 INFO L226 Difference]: Without dead ends: 48 [2022-03-20 23:07:38,546 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-03-20 23:07:38,547 INFO L913 BasicCegarLoop]: 42 mSDtfsCounter, 2 mSDsluCounter, 297 mSDsCounter, 0 mSdLazyCounter, 139 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 339 SdHoareTripleChecker+Invalid, 140 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 139 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 23:07:38,547 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 339 Invalid, 140 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 139 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 23:07:38,547 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2022-03-20 23:07:38,554 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 48. [2022-03-20 23:07:38,554 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-03-20 23:07:38,555 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 55 transitions. [2022-03-20 23:07:38,555 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 55 transitions. Word has length 68 [2022-03-20 23:07:38,555 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 23:07:38,555 INFO L478 AbstractCegarLoop]: Abstraction has 48 states and 55 transitions. [2022-03-20 23:07:38,556 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-03-20 23:07:38,556 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 55 transitions. [2022-03-20 23:07:38,556 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2022-03-20 23:07:38,556 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 23:07:38,557 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-03-20 23:07:38,577 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-03-20 23:07:38,767 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-03-20 23:07:38,768 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 23:07:38,768 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 23:07:38,768 INFO L85 PathProgramCache]: Analyzing trace with hash -1692754003, now seen corresponding path program 11 times [2022-03-20 23:07:38,768 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 23:07:38,768 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [304203637] [2022-03-20 23:07:38,768 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 23:07:38,769 INFO L85 PathProgramCache]: Analyzing trace with hash -1692754003, now seen corresponding path program 12 times [2022-03-20 23:07:38,769 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 23:07:38,769 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1919302117] [2022-03-20 23:07:38,769 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 23:07:38,769 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 23:07:38,784 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 23:07:38,784 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1938413224] [2022-03-20 23:07:38,784 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-03-20 23:07:38,784 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 23:07:38,784 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 23:07:38,789 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-03-20 23:07:38,790 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-03-20 23:07:52,066 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2022-03-20 23:07:52,066 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 23:07:52,075 INFO L263 TraceCheckSpWp]: Trace formula consists of 198 conjuncts, 32 conjunts are in the unsatisfiable core [2022-03-20 23:07:52,077 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 23:07:52,307 INFO L134 CoverageAnalysis]: Checked inductivity of 195 backedges. 16 proven. 63 refuted. 0 times theorem prover too weak. 116 trivial. 0 not checked. [2022-03-20 23:07:52,307 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 23:07:52,422 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 23:07:52,423 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1919302117] [2022-03-20 23:07:52,423 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 23:07:52,423 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1938413224] [2022-03-20 23:07:52,423 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1938413224] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 23:07:52,423 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 23:07:52,423 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2022-03-20 23:07:52,423 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 23:07:52,423 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [304203637] [2022-03-20 23:07:52,423 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [304203637] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 23:07:52,424 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 23:07:52,424 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [12] imperfect sequences [] total 12 [2022-03-20 23:07:52,424 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1448361812] [2022-03-20 23:07:52,424 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 23:07:52,424 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-03-20 23:07:52,424 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 23:07:52,424 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-03-20 23:07:52,425 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=39, Invalid=171, Unknown=0, NotChecked=0, Total=210 [2022-03-20 23:07:52,425 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-03-20 23:07:52,556 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 23:07:52,556 INFO L93 Difference]: Finished difference Result 57 states and 66 transitions. [2022-03-20 23:07:52,557 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-03-20 23:07:52,557 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-03-20 23:07:52,559 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 23:07:52,560 INFO L225 Difference]: With dead ends: 57 [2022-03-20 23:07:52,560 INFO L226 Difference]: Without dead ends: 51 [2022-03-20 23:07:52,561 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 94 GetRequests, 78 SyntacticMatches, 1 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=49, Invalid=223, Unknown=0, NotChecked=0, Total=272 [2022-03-20 23:07:52,561 INFO L913 BasicCegarLoop]: 45 mSDtfsCounter, 2 mSDsluCounter, 350 mSDsCounter, 0 mSdLazyCounter, 174 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 395 SdHoareTripleChecker+Invalid, 175 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 174 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 23:07:52,561 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 395 Invalid, 175 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 174 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 23:07:52,562 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2022-03-20 23:07:52,567 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 51. [2022-03-20 23:07:52,570 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-03-20 23:07:52,571 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 59 transitions. [2022-03-20 23:07:52,571 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 59 transitions. Word has length 75 [2022-03-20 23:07:52,571 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 23:07:52,571 INFO L478 AbstractCegarLoop]: Abstraction has 51 states and 59 transitions. [2022-03-20 23:07:52,571 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-03-20 23:07:52,572 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 59 transitions. [2022-03-20 23:07:52,572 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 83 [2022-03-20 23:07:52,572 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 23:07:52,572 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-03-20 23:07:52,583 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-03-20 23:07:52,773 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-03-20 23:07:52,773 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 23:07:52,773 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 23:07:52,773 INFO L85 PathProgramCache]: Analyzing trace with hash 615143773, now seen corresponding path program 13 times [2022-03-20 23:07:52,773 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 23:07:52,774 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [143683490] [2022-03-20 23:07:52,774 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 23:07:52,774 INFO L85 PathProgramCache]: Analyzing trace with hash 615143773, now seen corresponding path program 14 times [2022-03-20 23:07:52,774 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 23:07:52,774 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1422998124] [2022-03-20 23:07:52,774 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 23:07:52,774 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 23:07:52,784 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 23:07:52,784 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1762926967] [2022-03-20 23:07:52,784 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 23:07:52,785 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 23:07:52,785 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 23:07:52,786 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-03-20 23:07:52,801 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-03-20 23:07:56,965 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 23:07:56,965 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 23:07:56,971 INFO L263 TraceCheckSpWp]: Trace formula consists of 215 conjuncts, 36 conjunts are in the unsatisfiable core [2022-03-20 23:07:56,973 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 23:07:57,269 INFO L134 CoverageAnalysis]: Checked inductivity of 250 backedges. 18 proven. 84 refuted. 0 times theorem prover too weak. 148 trivial. 0 not checked. [2022-03-20 23:07:57,270 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 23:07:57,435 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 23:07:57,435 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1422998124] [2022-03-20 23:07:57,435 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 23:07:57,435 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1762926967] [2022-03-20 23:07:57,435 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1762926967] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 23:07:57,436 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 23:07:57,436 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2022-03-20 23:07:57,436 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 23:07:57,436 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [143683490] [2022-03-20 23:07:57,436 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [143683490] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 23:07:57,436 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 23:07:57,436 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [13] imperfect sequences [] total 13 [2022-03-20 23:07:57,436 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1478731707] [2022-03-20 23:07:57,436 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 23:07:57,437 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2022-03-20 23:07:57,437 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 23:07:57,437 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2022-03-20 23:07:57,437 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=42, Invalid=198, Unknown=0, NotChecked=0, Total=240 [2022-03-20 23:07:57,437 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-03-20 23:07:57,627 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 23:07:57,627 INFO L93 Difference]: Finished difference Result 60 states and 70 transitions. [2022-03-20 23:07:57,627 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-03-20 23:07:57,627 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-03-20 23:07:57,627 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 23:07:57,628 INFO L225 Difference]: With dead ends: 60 [2022-03-20 23:07:57,628 INFO L226 Difference]: Without dead ends: 54 [2022-03-20 23:07:57,628 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-03-20 23:07:57,629 INFO L913 BasicCegarLoop]: 48 mSDtfsCounter, 2 mSDsluCounter, 407 mSDsCounter, 0 mSdLazyCounter, 213 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 455 SdHoareTripleChecker+Invalid, 214 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 213 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-03-20 23:07:57,629 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 455 Invalid, 214 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 213 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-03-20 23:07:57,629 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2022-03-20 23:07:57,635 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 54. [2022-03-20 23:07:57,635 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-03-20 23:07:57,635 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 63 transitions. [2022-03-20 23:07:57,635 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 63 transitions. Word has length 82 [2022-03-20 23:07:57,635 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 23:07:57,636 INFO L478 AbstractCegarLoop]: Abstraction has 54 states and 63 transitions. [2022-03-20 23:07:57,636 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-03-20 23:07:57,636 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 63 transitions. [2022-03-20 23:07:57,636 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 90 [2022-03-20 23:07:57,636 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 23:07:57,636 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-03-20 23:07:57,644 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2022-03-20 23:07:57,837 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-03-20 23:07:57,838 INFO L403 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 23:07:57,838 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 23:07:57,838 INFO L85 PathProgramCache]: Analyzing trace with hash -1334355539, now seen corresponding path program 15 times [2022-03-20 23:07:57,838 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 23:07:57,838 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [396869715] [2022-03-20 23:07:57,839 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 23:07:57,839 INFO L85 PathProgramCache]: Analyzing trace with hash -1334355539, now seen corresponding path program 16 times [2022-03-20 23:07:57,839 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 23:07:57,839 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1275849684] [2022-03-20 23:07:57,839 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 23:07:57,839 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 23:07:57,846 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 23:07:57,846 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [590725557] [2022-03-20 23:07:57,846 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-03-20 23:07:57,846 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 23:07:57,846 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 23:07:57,847 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-03-20 23:07:57,876 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-03-20 23:07:57,892 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-03-20 23:07:57,892 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 23:07:57,893 INFO L263 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 40 conjunts are in the unsatisfiable core [2022-03-20 23:07:57,895 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 23:07:58,194 INFO L134 CoverageAnalysis]: Checked inductivity of 312 backedges. 20 proven. 108 refuted. 0 times theorem prover too weak. 184 trivial. 0 not checked. [2022-03-20 23:07:58,194 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 23:07:58,333 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 23:07:58,334 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1275849684] [2022-03-20 23:07:58,334 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 23:07:58,334 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [590725557] [2022-03-20 23:07:58,334 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [590725557] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 23:07:58,334 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 23:07:58,334 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14] total 14 [2022-03-20 23:07:58,334 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 23:07:58,334 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [396869715] [2022-03-20 23:07:58,335 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [396869715] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 23:07:58,335 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 23:07:58,335 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [14] imperfect sequences [] total 14 [2022-03-20 23:07:58,335 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1129580778] [2022-03-20 23:07:58,335 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 23:07:58,335 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2022-03-20 23:07:58,335 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 23:07:58,336 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-03-20 23:07:58,336 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=45, Invalid=227, Unknown=0, NotChecked=0, Total=272 [2022-03-20 23:07:58,336 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-03-20 23:07:58,506 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 23:07:58,506 INFO L93 Difference]: Finished difference Result 63 states and 74 transitions. [2022-03-20 23:07:58,507 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2022-03-20 23:07:58,507 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-03-20 23:07:58,507 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 23:07:58,507 INFO L225 Difference]: With dead ends: 63 [2022-03-20 23:07:58,508 INFO L226 Difference]: Without dead ends: 57 [2022-03-20 23:07:58,508 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-03-20 23:07:58,508 INFO L913 BasicCegarLoop]: 51 mSDtfsCounter, 2 mSDsluCounter, 468 mSDsCounter, 0 mSdLazyCounter, 256 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 519 SdHoareTripleChecker+Invalid, 257 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 256 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 23:07:58,508 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 519 Invalid, 257 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 256 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 23:07:58,509 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 57 states. [2022-03-20 23:07:58,515 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 57 to 57. [2022-03-20 23:07:58,515 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-03-20 23:07:58,515 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 67 transitions. [2022-03-20 23:07:58,515 INFO L78 Accepts]: Start accepts. Automaton has 57 states and 67 transitions. Word has length 89 [2022-03-20 23:07:58,515 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 23:07:58,516 INFO L478 AbstractCegarLoop]: Abstraction has 57 states and 67 transitions. [2022-03-20 23:07:58,516 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-03-20 23:07:58,516 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 67 transitions. [2022-03-20 23:07:58,527 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 97 [2022-03-20 23:07:58,527 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 23:07:58,527 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-03-20 23:07:58,553 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-03-20 23:07:58,728 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-03-20 23:07:58,728 INFO L403 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 23:07:58,728 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 23:07:58,729 INFO L85 PathProgramCache]: Analyzing trace with hash 711483229, now seen corresponding path program 17 times [2022-03-20 23:07:58,729 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 23:07:58,729 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [2100386738] [2022-03-20 23:07:58,729 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 23:07:58,729 INFO L85 PathProgramCache]: Analyzing trace with hash 711483229, now seen corresponding path program 18 times [2022-03-20 23:07:58,729 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 23:07:58,729 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1477710267] [2022-03-20 23:07:58,729 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 23:07:58,730 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 23:07:58,736 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 23:07:58,737 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [715698522] [2022-03-20 23:07:58,737 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-03-20 23:07:58,737 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 23:07:58,737 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 23:07:58,743 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-03-20 23:07:58,744 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process