/usr/bin/java -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data -s ../../../trunk/examples/settings/automizer/mcr/svcomp-Reach-32bit-Automizer_Default-noMmResRef-FA-McrAutomaton-WP.epf -tc ../../../trunk/examples/toolchains/AutomizerBplInline.xml -i ../../../trunk/examples/concurrent/bpl/weaver-benchmarks/generated/bench/exp3x3-opt.wvr.bpl -------------------------------------------------------------------------------- This is Ultimate 0.2.2-wip.dk.mcr-reduction-c7b2d19 [2022-03-15 20:56:29,273 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-03-15 20:56:29,275 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-03-15 20:56:29,308 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-03-15 20:56:29,308 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-03-15 20:56:29,309 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-03-15 20:56:29,310 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-03-15 20:56:29,311 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-03-15 20:56:29,312 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-03-15 20:56:29,313 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-03-15 20:56:29,313 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-03-15 20:56:29,314 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-03-15 20:56:29,314 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-03-15 20:56:29,315 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-03-15 20:56:29,316 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-03-15 20:56:29,316 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-03-15 20:56:29,317 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-03-15 20:56:29,317 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-03-15 20:56:29,318 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-03-15 20:56:29,319 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-03-15 20:56:29,320 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-03-15 20:56:29,322 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-03-15 20:56:29,323 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-03-15 20:56:29,324 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-03-15 20:56:29,325 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-03-15 20:56:29,325 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-03-15 20:56:29,326 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-03-15 20:56:29,326 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-03-15 20:56:29,326 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-03-15 20:56:29,327 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-03-15 20:56:29,327 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-03-15 20:56:29,328 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-03-15 20:56:29,328 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-03-15 20:56:29,328 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-03-15 20:56:29,329 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-03-15 20:56:29,329 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-03-15 20:56:29,330 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-03-15 20:56:29,330 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-03-15 20:56:29,330 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-03-15 20:56:29,331 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-03-15 20:56:29,331 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-03-15 20:56:29,332 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/mcr/svcomp-Reach-32bit-Automizer_Default-noMmResRef-FA-McrAutomaton-WP.epf [2022-03-15 20:56:29,345 INFO L113 SettingsManager]: Loading preferences was successful [2022-03-15 20:56:29,345 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-03-15 20:56:29,345 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-03-15 20:56:29,346 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-03-15 20:56:29,346 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-03-15 20:56:29,346 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-03-15 20:56:29,346 INFO L138 SettingsManager]: * Use SBE=true [2022-03-15 20:56:29,346 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-03-15 20:56:29,346 INFO L138 SettingsManager]: * sizeof long=4 [2022-03-15 20:56:29,347 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-03-15 20:56:29,347 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-03-15 20:56:29,347 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-03-15 20:56:29,347 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-03-15 20:56:29,347 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-03-15 20:56:29,347 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-03-15 20:56:29,347 INFO L138 SettingsManager]: * sizeof long double=12 [2022-03-15 20:56:29,347 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-03-15 20:56:29,347 INFO L138 SettingsManager]: * Use constant arrays=true [2022-03-15 20:56:29,348 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-03-15 20:56:29,348 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-03-15 20:56:29,348 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-03-15 20:56:29,348 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-03-15 20:56:29,348 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-03-15 20:56:29,348 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-15 20:56:29,348 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-03-15 20:56:29,348 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_NestedInterpolation [2022-03-15 20:56:29,349 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-03-15 20:56:29,349 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-03-15 20:56:29,349 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2022-03-15 20:56:29,349 INFO L138 SettingsManager]: * Override the interpolant automaton setting of the refinement strategy=true [2022-03-15 20:56:29,349 INFO L138 SettingsManager]: * Large block encoding in concurrent analysis=VARIABLE_BASED_MOVER_CHECK [2022-03-15 20:56:29,349 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-03-15 20:56:29,349 INFO L138 SettingsManager]: * Interpolant automaton=MCR 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 [2022-03-15 20:56:29,513 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-03-15 20:56:29,528 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-03-15 20:56:29,530 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-03-15 20:56:29,530 INFO L271 PluginConnector]: Initializing Boogie PL CUP Parser... [2022-03-15 20:56:29,532 INFO L275 PluginConnector]: Boogie PL CUP Parser initialized [2022-03-15 20:56:29,533 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/concurrent/bpl/weaver-benchmarks/generated/bench/exp3x3-opt.wvr.bpl [2022-03-15 20:56:29,533 INFO L110 BoogieParser]: Parsing: '/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/concurrent/bpl/weaver-benchmarks/generated/bench/exp3x3-opt.wvr.bpl' [2022-03-15 20:56:29,551 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-03-15 20:56:29,552 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-03-15 20:56:29,556 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2022-03-15 20:56:29,556 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2022-03-15 20:56:29,556 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2022-03-15 20:56:29,572 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "exp3x3-opt.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.03 08:56:29" (1/1) ... [2022-03-15 20:56:29,576 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "exp3x3-opt.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.03 08:56:29" (1/1) ... [2022-03-15 20:56:29,582 INFO L137 Inliner]: procedures = 7, calls = 6, calls flagged for inlining = 0, calls inlined = 0, statements flattened = 0 [2022-03-15 20:56:29,583 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2022-03-15 20:56:29,585 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-03-15 20:56:29,585 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-03-15 20:56:29,585 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-03-15 20:56:29,590 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "exp3x3-opt.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.03 08:56:29" (1/1) ... [2022-03-15 20:56:29,590 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "exp3x3-opt.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.03 08:56:29" (1/1) ... [2022-03-15 20:56:29,596 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "exp3x3-opt.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.03 08:56:29" (1/1) ... [2022-03-15 20:56:29,597 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "exp3x3-opt.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.03 08:56:29" (1/1) ... [2022-03-15 20:56:29,600 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "exp3x3-opt.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.03 08:56:29" (1/1) ... [2022-03-15 20:56:29,603 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "exp3x3-opt.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.03 08:56:29" (1/1) ... [2022-03-15 20:56:29,607 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "exp3x3-opt.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.03 08:56:29" (1/1) ... [2022-03-15 20:56:29,608 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-03-15 20:56:29,610 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-03-15 20:56:29,610 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-03-15 20:56:29,610 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-03-15 20:56:29,611 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "exp3x3-opt.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.03 08:56:29" (1/1) ... [2022-03-15 20:56:29,616 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-15 20:56:29,624 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 20:56:29,636 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-15 20:56:29,641 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-15 20:56:29,669 INFO L124 BoogieDeclarations]: Specification and implementation of procedure thread1 given in one single declaration [2022-03-15 20:56:29,669 INFO L130 BoogieDeclarations]: Found specification of procedure thread1 [2022-03-15 20:56:29,669 INFO L138 BoogieDeclarations]: Found implementation of procedure thread1 [2022-03-15 20:56:29,669 INFO L124 BoogieDeclarations]: Specification and implementation of procedure thread2 given in one single declaration [2022-03-15 20:56:29,670 INFO L130 BoogieDeclarations]: Found specification of procedure thread2 [2022-03-15 20:56:29,670 INFO L138 BoogieDeclarations]: Found implementation of procedure thread2 [2022-03-15 20:56:29,670 INFO L124 BoogieDeclarations]: Specification and implementation of procedure ULTIMATE.start given in one single declaration [2022-03-15 20:56:29,670 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-03-15 20:56:29,670 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-03-15 20:56:29,670 INFO L124 BoogieDeclarations]: Specification and implementation of procedure thread3 given in one single declaration [2022-03-15 20:56:29,670 INFO L130 BoogieDeclarations]: Found specification of procedure thread3 [2022-03-15 20:56:29,670 INFO L138 BoogieDeclarations]: Found implementation of procedure thread3 [2022-03-15 20:56:29,670 INFO L124 BoogieDeclarations]: Specification and implementation of procedure thread4 given in one single declaration [2022-03-15 20:56:29,671 INFO L130 BoogieDeclarations]: Found specification of procedure thread4 [2022-03-15 20:56:29,671 INFO L138 BoogieDeclarations]: Found implementation of procedure thread4 [2022-03-15 20:56:29,671 INFO L124 BoogieDeclarations]: Specification and implementation of procedure thread5 given in one single declaration [2022-03-15 20:56:29,671 INFO L130 BoogieDeclarations]: Found specification of procedure thread5 [2022-03-15 20:56:29,671 INFO L138 BoogieDeclarations]: Found implementation of procedure thread5 [2022-03-15 20:56:29,672 INFO L124 BoogieDeclarations]: Specification and implementation of procedure thread6 given in one single declaration [2022-03-15 20:56:29,673 INFO L130 BoogieDeclarations]: Found specification of procedure thread6 [2022-03-15 20:56:29,673 INFO L138 BoogieDeclarations]: Found implementation of procedure thread6 [2022-03-15 20:56:29,673 WARN L208 CfgBuilder]: User set CodeBlockSize to SequenceOfStatements but program contains fork statements. Overwriting the user preferences and setting CodeBlockSize to SingleStatement [2022-03-15 20:56:29,708 INFO L234 CfgBuilder]: Building ICFG [2022-03-15 20:56:29,709 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-03-15 20:56:29,782 INFO L275 CfgBuilder]: Performing block encoding [2022-03-15 20:56:29,795 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-03-15 20:56:29,795 INFO L299 CfgBuilder]: Removed 6 assume(true) statements. [2022-03-15 20:56:29,795 WARN L329 CfgBuilder]: Unexpected successor node of atomic block begin: thread1EXIT is neither atomic block end nor error location. [2022-03-15 20:56:29,796 WARN L329 CfgBuilder]: Unexpected successor node of atomic block begin: thread2EXIT is neither atomic block end nor error location. [2022-03-15 20:56:29,796 WARN L329 CfgBuilder]: Unexpected successor node of atomic block begin: thread3EXIT is neither atomic block end nor error location. [2022-03-15 20:56:29,796 WARN L329 CfgBuilder]: Unexpected successor node of atomic block begin: thread4EXIT is neither atomic block end nor error location. [2022-03-15 20:56:29,796 WARN L329 CfgBuilder]: Unexpected successor node of atomic block begin: thread5EXIT is neither atomic block end nor error location. [2022-03-15 20:56:29,796 WARN L329 CfgBuilder]: Unexpected successor node of atomic block begin: thread6EXIT is neither atomic block end nor error location. [2022-03-15 20:56:29,798 INFO L202 PluginConnector]: Adding new model exp3x3-opt.wvr.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 15.03 08:56:29 BoogieIcfgContainer [2022-03-15 20:56:29,798 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-03-15 20:56:29,799 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-03-15 20:56:29,799 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-03-15 20:56:29,801 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-03-15 20:56:29,801 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "exp3x3-opt.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.03 08:56:29" (1/2) ... [2022-03-15 20:56:29,802 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@f8e8239 and model type exp3x3-opt.wvr.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 15.03 08:56:29, skipping insertion in model container [2022-03-15 20:56:29,802 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "exp3x3-opt.wvr.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 15.03 08:56:29" (2/2) ... [2022-03-15 20:56:29,803 INFO L111 eAbstractionObserver]: Analyzing ICFG exp3x3-opt.wvr.bpl [2022-03-15 20:56:29,806 WARN L150 ceAbstractionStarter]: Switching off computation of Hoare annotation because input is a concurrent program [2022-03-15 20:56:29,806 INFO L205 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:Craig_NestedInterpolation Determinization: PREDICATE_ABSTRACTION [2022-03-15 20:56:29,807 INFO L164 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-03-15 20:56:29,807 INFO L534 ceAbstractionStarter]: Constructing petrified ICFG for 1 thread instances. [2022-03-15 20:56:29,842 INFO L148 ThreadInstanceAdder]: Constructed 6 joinOtherThreadTransitions. [2022-03-15 20:56:29,874 INFO L338 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-03-15 20:56:29,879 INFO L339 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=Craig_NestedInterpolation, mInterpolantAutomaton=MCR, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=FINITE_AUTOMATA, mLazyFiniteAutomaton=false, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopsAndPotentialCycles, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=true, mMcrInterpolantMethod=WP, mLoopAccelerationTechnique=FAST_UPR, mMcrOptimizeForkJoin=true, mMcrOverapproximateWrwc=true [2022-03-15 20:56:29,879 INFO L340 AbstractCegarLoop]: Starting to check reachability of 7 error locations. [2022-03-15 20:56:29,890 INFO L126 etLargeBlockEncoding]: Petri net LBE is using variable-based independence relation. [2022-03-15 20:56:29,897 INFO L133 etLargeBlockEncoding]: Starting large block encoding on Petri net that has 48 places, 35 transitions, 118 flow [2022-03-15 20:56:29,902 INFO L110 LiptonReduction]: Starting Lipton reduction on Petri net that has 48 places, 35 transitions, 118 flow [2022-03-15 20:56:29,903 INFO L74 FinitePrefix]: Start finitePrefix. Operand has 48 places, 35 transitions, 118 flow [2022-03-15 20:56:29,927 INFO L129 PetriNetUnfolder]: 6/29 cut-off events. [2022-03-15 20:56:29,927 INFO L130 PetriNetUnfolder]: For 6/6 co-relation queries the response was YES. [2022-03-15 20:56:29,935 INFO L84 FinitePrefix]: Finished finitePrefix Result has 54 conditions, 29 events. 6/29 cut-off events. For 6/6 co-relation queries the response was YES. Maximal size of possible extension queue 3. Compared 17 event pairs, 0 based on Foata normal form. 0/22 useless extension candidates. Maximal degree in co-relation 27. Up to 2 conditions per place. [2022-03-15 20:56:29,936 INFO L116 LiptonReduction]: Number of co-enabled transitions 240 [2022-03-15 20:56:30,059 INFO L131 LiptonReduction]: Checked pairs total: 270 [2022-03-15 20:56:30,059 INFO L133 LiptonReduction]: Total number of compositions: 3 [2022-03-15 20:56:30,064 INFO L111 iNet2FiniteAutomaton]: Start petriNet2FiniteAutomaton. Operand has 46 places, 33 transitions, 114 flow [2022-03-15 20:56:30,106 INFO L133 iNet2FiniteAutomaton]: Finished petriNet2FiniteAutomaton. Result has 192 states, 191 states have (on average 5.382198952879581) internal successors, (1028), 191 states have internal predecessors, (1028), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:56:30,111 INFO L276 IsEmpty]: Start isEmpty. Operand has 192 states, 191 states have (on average 5.382198952879581) internal successors, (1028), 191 states have internal predecessors, (1028), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:56:30,120 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2022-03-15 20:56:30,120 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 20:56:30,120 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 20:56:30,121 INFO L402 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr2INUSE_VIOLATION (and 3 more)] === [2022-03-15 20:56:30,130 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 20:56:30,130 INFO L85 PathProgramCache]: Analyzing trace with hash -168589376, now seen corresponding path program 1 times [2022-03-15 20:56:30,142 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 20:56:30,142 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2081204047] [2022-03-15 20:56:30,142 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 20:56:30,143 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 20:56:30,208 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 20:56:30,256 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 20:56:30,256 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 20:56:30,257 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2081204047] [2022-03-15 20:56:30,259 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2081204047] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-15 20:56:30,259 INFO L191 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-15 20:56:30,259 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2022-03-15 20:56:30,261 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [804402327] [2022-03-15 20:56:30,261 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 20:56:30,267 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 20:56:30,302 INFO L252 McrAutomatonBuilder]: Finished intersection with 192 states and 578 transitions. [2022-03-15 20:56:30,302 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 20:56:31,231 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 0 new interpolants: [] [2022-03-15 20:56:31,234 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-03-15 20:56:31,235 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 20:56:31,247 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-03-15 20:56:31,248 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-03-15 20:56:31,250 INFO L87 Difference]: Start difference. First operand has 192 states, 191 states have (on average 5.382198952879581) internal successors, (1028), 191 states have internal predecessors, (1028), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Second operand has 3 states, 2 states have (on average 10.0) internal successors, (20), 2 states have internal predecessors, (20), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:56:31,294 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 20:56:31,294 INFO L93 Difference]: Finished difference Result 375 states and 2037 transitions. [2022-03-15 20:56:31,295 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-03-15 20:56:31,296 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 2 states have (on average 10.0) internal successors, (20), 2 states have internal predecessors, (20), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 20 [2022-03-15 20:56:31,296 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 20:56:31,304 INFO L225 Difference]: With dead ends: 375 [2022-03-15 20:56:31,304 INFO L226 Difference]: Without dead ends: 324 [2022-03-15 20:56:31,305 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 172 GetRequests, 171 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-15 20:56:31,307 INFO L933 BasicCegarLoop]: 7 mSDtfsCounter, 4 mSDsluCounter, 19 mSDsCounter, 0 mSdLazyCounter, 35 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 13 SdHoareTripleChecker+Invalid, 35 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 35 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-15 20:56:31,307 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [4 Valid, 13 Invalid, 35 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 35 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-15 20:56:31,319 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 324 states. [2022-03-15 20:56:31,345 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 324 to 324. [2022-03-15 20:56:31,346 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 324 states, 323 states have (on average 5.486068111455109) internal successors, (1772), 323 states have internal predecessors, (1772), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:56:31,348 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 324 states to 324 states and 1772 transitions. [2022-03-15 20:56:31,349 INFO L78 Accepts]: Start accepts. Automaton has 324 states and 1772 transitions. Word has length 20 [2022-03-15 20:56:31,349 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 20:56:31,349 INFO L470 AbstractCegarLoop]: Abstraction has 324 states and 1772 transitions. [2022-03-15 20:56:31,349 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 2 states have (on average 10.0) internal successors, (20), 2 states have internal predecessors, (20), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:56:31,349 INFO L276 IsEmpty]: Start isEmpty. Operand 324 states and 1772 transitions. [2022-03-15 20:56:31,352 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2022-03-15 20:56:31,352 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 20:56:31,352 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 20:56:31,352 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-03-15 20:56:31,353 INFO L402 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr2INUSE_VIOLATION (and 3 more)] === [2022-03-15 20:56:31,353 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 20:56:31,353 INFO L85 PathProgramCache]: Analyzing trace with hash -922098845, now seen corresponding path program 1 times [2022-03-15 20:56:31,354 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 20:56:31,354 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2089236061] [2022-03-15 20:56:31,354 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 20:56:31,354 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 20:56:31,364 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 20:56:31,386 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2022-03-15 20:56:31,388 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 20:56:31,388 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2089236061] [2022-03-15 20:56:31,388 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2089236061] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-15 20:56:31,388 INFO L191 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-15 20:56:31,388 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2022-03-15 20:56:31,388 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [1567802901] [2022-03-15 20:56:31,388 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 20:56:31,391 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 20:56:31,436 INFO L252 McrAutomatonBuilder]: Finished intersection with 276 states and 886 transitions. [2022-03-15 20:56:31,437 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 20:56:32,389 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 0 new interpolants: [] [2022-03-15 20:56:32,391 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-03-15 20:56:32,391 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 20:56:32,391 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-03-15 20:56:32,391 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-03-15 20:56:32,391 INFO L87 Difference]: Start difference. First operand 324 states and 1772 transitions. Second operand has 3 states, 2 states have (on average 10.5) internal successors, (21), 2 states have internal predecessors, (21), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:56:32,432 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 20:56:32,432 INFO L93 Difference]: Finished difference Result 645 states and 3541 transitions. [2022-03-15 20:56:32,432 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-03-15 20:56:32,432 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 2 states have (on average 10.5) internal successors, (21), 2 states have internal predecessors, (21), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 21 [2022-03-15 20:56:32,433 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 20:56:32,437 INFO L225 Difference]: With dead ends: 645 [2022-03-15 20:56:32,438 INFO L226 Difference]: Without dead ends: 516 [2022-03-15 20:56:32,440 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 255 GetRequests, 254 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-15 20:56:32,445 INFO L933 BasicCegarLoop]: 7 mSDtfsCounter, 3 mSDsluCounter, 21 mSDsCounter, 0 mSdLazyCounter, 37 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3 SdHoareTripleChecker+Valid, 13 SdHoareTripleChecker+Invalid, 37 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 37 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-15 20:56:32,446 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [3 Valid, 13 Invalid, 37 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 37 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-15 20:56:32,448 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 516 states. [2022-03-15 20:56:32,472 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 516 to 516. [2022-03-15 20:56:32,474 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 516 states, 515 states have (on average 5.557281553398059) internal successors, (2862), 515 states have internal predecessors, (2862), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:56:32,477 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 516 states to 516 states and 2862 transitions. [2022-03-15 20:56:32,477 INFO L78 Accepts]: Start accepts. Automaton has 516 states and 2862 transitions. Word has length 21 [2022-03-15 20:56:32,477 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 20:56:32,477 INFO L470 AbstractCegarLoop]: Abstraction has 516 states and 2862 transitions. [2022-03-15 20:56:32,477 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 2 states have (on average 10.5) internal successors, (21), 2 states have internal predecessors, (21), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:56:32,477 INFO L276 IsEmpty]: Start isEmpty. Operand 516 states and 2862 transitions. [2022-03-15 20:56:32,479 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2022-03-15 20:56:32,480 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 20:56:32,480 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 20:56:32,480 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-03-15 20:56:32,480 INFO L402 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr2INUSE_VIOLATION (and 3 more)] === [2022-03-15 20:56:32,480 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 20:56:32,480 INFO L85 PathProgramCache]: Analyzing trace with hash 1689736276, now seen corresponding path program 1 times [2022-03-15 20:56:32,481 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 20:56:32,481 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1818934533] [2022-03-15 20:56:32,481 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 20:56:32,481 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 20:56:32,499 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 20:56:32,519 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2022-03-15 20:56:32,519 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 20:56:32,520 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1818934533] [2022-03-15 20:56:32,520 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1818934533] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-15 20:56:32,520 INFO L191 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-15 20:56:32,520 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2022-03-15 20:56:32,520 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [1572117361] [2022-03-15 20:56:32,520 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 20:56:32,522 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 20:56:32,607 INFO L252 McrAutomatonBuilder]: Finished intersection with 390 states and 1323 transitions. [2022-03-15 20:56:32,607 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 20:56:33,996 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 0 new interpolants: [] [2022-03-15 20:56:33,996 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-03-15 20:56:33,997 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 20:56:33,997 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-03-15 20:56:33,997 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-03-15 20:56:33,997 INFO L87 Difference]: Start difference. First operand 516 states and 2862 transitions. Second operand has 3 states, 2 states have (on average 11.0) internal successors, (22), 2 states have internal predecessors, (22), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:56:34,035 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 20:56:34,036 INFO L93 Difference]: Finished difference Result 941 states and 5335 transitions. [2022-03-15 20:56:34,036 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-03-15 20:56:34,036 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 2 states have (on average 11.0) internal successors, (22), 2 states have internal predecessors, (22), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 22 [2022-03-15 20:56:34,036 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 20:56:34,042 INFO L225 Difference]: With dead ends: 941 [2022-03-15 20:56:34,042 INFO L226 Difference]: Without dead ends: 858 [2022-03-15 20:56:34,043 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 368 GetRequests, 367 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-15 20:56:34,045 INFO L933 BasicCegarLoop]: 7 mSDtfsCounter, 2 mSDsluCounter, 17 mSDsCounter, 0 mSdLazyCounter, 33 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 13 SdHoareTripleChecker+Invalid, 33 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 33 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-15 20:56:34,046 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 13 Invalid, 33 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 33 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-15 20:56:34,048 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 858 states. [2022-03-15 20:56:34,065 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 858 to 858. [2022-03-15 20:56:34,067 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 858 states, 857 states have (on average 5.673278879813302) internal successors, (4862), 857 states have internal predecessors, (4862), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:56:34,072 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 858 states to 858 states and 4862 transitions. [2022-03-15 20:56:34,072 INFO L78 Accepts]: Start accepts. Automaton has 858 states and 4862 transitions. Word has length 22 [2022-03-15 20:56:34,072 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 20:56:34,073 INFO L470 AbstractCegarLoop]: Abstraction has 858 states and 4862 transitions. [2022-03-15 20:56:34,073 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 2 states have (on average 11.0) internal successors, (22), 2 states have internal predecessors, (22), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:56:34,073 INFO L276 IsEmpty]: Start isEmpty. Operand 858 states and 4862 transitions. [2022-03-15 20:56:34,076 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2022-03-15 20:56:34,076 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 20:56:34,076 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 20:56:34,077 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2022-03-15 20:56:34,077 INFO L402 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr2INUSE_VIOLATION (and 3 more)] === [2022-03-15 20:56:34,078 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 20:56:34,078 INFO L85 PathProgramCache]: Analyzing trace with hash -1604305123, now seen corresponding path program 1 times [2022-03-15 20:56:34,079 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 20:56:34,080 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [741155314] [2022-03-15 20:56:34,080 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 20:56:34,080 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 20:56:34,104 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 20:56:34,146 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2022-03-15 20:56:34,146 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 20:56:34,147 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [741155314] [2022-03-15 20:56:34,147 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [741155314] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-15 20:56:34,147 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [602729486] [2022-03-15 20:56:34,147 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 20:56:34,147 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 20:56:34,147 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 20:56:34,152 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-15 20:56:34,168 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-15 20:56:34,212 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 20:56:34,213 INFO L263 TraceCheckSpWp]: Trace formula consists of 116 conjuncts, 3 conjunts are in the unsatisfiable core [2022-03-15 20:56:34,217 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-15 20:56:34,286 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2022-03-15 20:56:34,287 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-15 20:56:34,328 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2022-03-15 20:56:34,329 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [602729486] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-15 20:56:34,329 INFO L191 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-03-15 20:56:34,329 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [2, 2, 2] total 4 [2022-03-15 20:56:34,329 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [978783047] [2022-03-15 20:56:34,329 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 20:56:34,332 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 20:56:34,380 INFO L252 McrAutomatonBuilder]: Finished intersection with 519 states and 1825 transitions. [2022-03-15 20:56:34,380 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 20:56:36,841 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 0 new interpolants: [] [2022-03-15 20:56:36,841 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2022-03-15 20:56:36,841 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 20:56:36,842 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2022-03-15 20:56:36,843 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-03-15 20:56:36,843 INFO L87 Difference]: Start difference. First operand 858 states and 4862 transitions. Second operand has 4 states, 3 states have (on average 11.666666666666666) internal successors, (35), 3 states have internal predecessors, (35), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:56:36,900 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 20:56:36,900 INFO L93 Difference]: Finished difference Result 1331 states and 7578 transitions. [2022-03-15 20:56:36,900 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2022-03-15 20:56:36,900 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 3 states have (on average 11.666666666666666) internal successors, (35), 3 states have internal predecessors, (35), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 23 [2022-03-15 20:56:36,901 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 20:56:36,907 INFO L225 Difference]: With dead ends: 1331 [2022-03-15 20:56:36,907 INFO L226 Difference]: Without dead ends: 956 [2022-03-15 20:56:36,907 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 541 GetRequests, 370 SyntacticMatches, 167 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-03-15 20:56:36,908 INFO L933 BasicCegarLoop]: 13 mSDtfsCounter, 6 mSDsluCounter, 47 mSDsCounter, 0 mSdLazyCounter, 77 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 31 SdHoareTripleChecker+Invalid, 77 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 77 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-15 20:56:36,909 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 31 Invalid, 77 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 77 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-15 20:56:36,911 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 956 states. [2022-03-15 20:56:36,924 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 956 to 732. [2022-03-15 20:56:36,926 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 732 states, 731 states have (on average 5.674418604651163) internal successors, (4148), 731 states have internal predecessors, (4148), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:56:36,929 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 732 states to 732 states and 4148 transitions. [2022-03-15 20:56:36,929 INFO L78 Accepts]: Start accepts. Automaton has 732 states and 4148 transitions. Word has length 23 [2022-03-15 20:56:36,930 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 20:56:36,930 INFO L470 AbstractCegarLoop]: Abstraction has 732 states and 4148 transitions. [2022-03-15 20:56:36,932 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 3 states have (on average 11.666666666666666) internal successors, (35), 3 states have internal predecessors, (35), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:56:36,932 INFO L276 IsEmpty]: Start isEmpty. Operand 732 states and 4148 transitions. [2022-03-15 20:56:36,934 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2022-03-15 20:56:36,934 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 20:56:36,934 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 20:56:36,953 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-15 20:56:37,147 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 20:56:37,148 INFO L402 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr2INUSE_VIOLATION (and 3 more)] === [2022-03-15 20:56:37,148 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 20:56:37,148 INFO L85 PathProgramCache]: Analyzing trace with hash -1662752717, now seen corresponding path program 1 times [2022-03-15 20:56:37,153 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 20:56:37,153 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1405146673] [2022-03-15 20:56:37,153 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 20:56:37,153 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 20:56:37,160 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 20:56:37,175 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2022-03-15 20:56:37,175 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 20:56:37,175 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1405146673] [2022-03-15 20:56:37,175 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1405146673] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-15 20:56:37,175 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [509028609] [2022-03-15 20:56:37,175 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 20:56:37,175 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 20:56:37,175 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 20:56:37,180 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-15 20:56:37,203 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-15 20:56:37,240 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 20:56:37,241 INFO L263 TraceCheckSpWp]: Trace formula consists of 116 conjuncts, 3 conjunts are in the unsatisfiable core [2022-03-15 20:56:37,241 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-15 20:56:37,276 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2022-03-15 20:56:37,276 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-15 20:56:37,331 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2022-03-15 20:56:37,331 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [509028609] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-15 20:56:37,331 INFO L191 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-03-15 20:56:37,331 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [2, 2, 2] total 4 [2022-03-15 20:56:37,331 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [2065280962] [2022-03-15 20:56:37,331 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 20:56:37,333 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 20:56:37,382 INFO L252 McrAutomatonBuilder]: Finished intersection with 519 states and 1825 transitions. [2022-03-15 20:56:37,382 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 20:56:40,521 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 1 new interpolants: [8872#(or (<= (+ x4 1) n) (<= n x3))] [2022-03-15 20:56:40,522 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-15 20:56:40,522 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 20:56:40,522 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-15 20:56:40,522 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2022-03-15 20:56:40,522 INFO L87 Difference]: Start difference. First operand 732 states and 4148 transitions. Second operand has 5 states, 4 states have (on average 11.5) internal successors, (46), 4 states have internal predecessors, (46), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:56:40,588 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 20:56:40,588 INFO L93 Difference]: Finished difference Result 1429 states and 8180 transitions. [2022-03-15 20:56:40,589 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-15 20:56:40,589 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 11.5) internal successors, (46), 4 states have internal predecessors, (46), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 23 [2022-03-15 20:56:40,589 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 20:56:40,597 INFO L225 Difference]: With dead ends: 1429 [2022-03-15 20:56:40,597 INFO L226 Difference]: Without dead ends: 1075 [2022-03-15 20:56:40,597 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 541 GetRequests, 457 SyntacticMatches, 79 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 78 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2022-03-15 20:56:40,598 INFO L933 BasicCegarLoop]: 12 mSDtfsCounter, 21 mSDsluCounter, 42 mSDsCounter, 0 mSdLazyCounter, 75 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 21 SdHoareTripleChecker+Valid, 29 SdHoareTripleChecker+Invalid, 78 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 75 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-15 20:56:40,599 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [21 Valid, 29 Invalid, 78 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 75 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-15 20:56:40,601 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1075 states. [2022-03-15 20:56:40,626 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1075 to 1075. [2022-03-15 20:56:40,629 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1075 states, 1074 states have (on average 5.726256983240224) internal successors, (6150), 1074 states have internal predecessors, (6150), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:56:40,635 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1075 states to 1075 states and 6150 transitions. [2022-03-15 20:56:40,635 INFO L78 Accepts]: Start accepts. Automaton has 1075 states and 6150 transitions. Word has length 23 [2022-03-15 20:56:40,636 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 20:56:40,636 INFO L470 AbstractCegarLoop]: Abstraction has 1075 states and 6150 transitions. [2022-03-15 20:56:40,636 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 11.5) internal successors, (46), 4 states have internal predecessors, (46), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:56:40,636 INFO L276 IsEmpty]: Start isEmpty. Operand 1075 states and 6150 transitions. [2022-03-15 20:56:40,641 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2022-03-15 20:56:40,641 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 20:56:40,641 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 20:56:40,675 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2022-03-15 20:56:40,859 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 20:56:40,860 INFO L402 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr2INUSE_VIOLATION (and 3 more)] === [2022-03-15 20:56:40,860 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 20:56:40,860 INFO L85 PathProgramCache]: Analyzing trace with hash 3477840, now seen corresponding path program 1 times [2022-03-15 20:56:40,861 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 20:56:40,861 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [4693471] [2022-03-15 20:56:40,861 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 20:56:40,861 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 20:56:40,867 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 20:56:40,893 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2022-03-15 20:56:40,893 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 20:56:40,893 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [4693471] [2022-03-15 20:56:40,894 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [4693471] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-15 20:56:40,894 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [603009320] [2022-03-15 20:56:40,894 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 20:56:40,894 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 20:56:40,894 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 20:56:40,895 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-15 20:56:40,896 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-15 20:56:40,928 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 20:56:40,929 INFO L263 TraceCheckSpWp]: Trace formula consists of 119 conjuncts, 3 conjunts are in the unsatisfiable core [2022-03-15 20:56:40,930 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-15 20:56:40,966 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2022-03-15 20:56:40,966 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-15 20:56:41,001 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2022-03-15 20:56:41,001 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [603009320] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-15 20:56:41,001 INFO L191 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-03-15 20:56:41,001 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [2, 2, 2] total 4 [2022-03-15 20:56:41,001 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [715605695] [2022-03-15 20:56:41,001 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 20:56:41,003 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 20:56:41,083 INFO L252 McrAutomatonBuilder]: Finished intersection with 759 states and 2813 transitions. [2022-03-15 20:56:41,083 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 20:56:45,883 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 1 new interpolants: [12596#(or (<= (+ x1 1) n) (<= n x2))] [2022-03-15 20:56:45,883 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-15 20:56:45,883 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 20:56:45,883 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-15 20:56:45,883 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2022-03-15 20:56:45,883 INFO L87 Difference]: Start difference. First operand 1075 states and 6150 transitions. Second operand has 5 states, 4 states have (on average 9.75) internal successors, (39), 4 states have internal predecessors, (39), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:56:45,957 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 20:56:45,957 INFO L93 Difference]: Finished difference Result 1744 states and 9949 transitions. [2022-03-15 20:56:45,957 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-15 20:56:45,957 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 9.75) internal successors, (39), 4 states have internal predecessors, (39), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 24 [2022-03-15 20:56:45,957 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 20:56:45,967 INFO L225 Difference]: With dead ends: 1744 [2022-03-15 20:56:45,967 INFO L226 Difference]: Without dead ends: 1123 [2022-03-15 20:56:45,967 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 782 GetRequests, 775 SyntacticMatches, 2 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2022-03-15 20:56:45,968 INFO L933 BasicCegarLoop]: 13 mSDtfsCounter, 27 mSDsluCounter, 51 mSDsCounter, 0 mSdLazyCounter, 86 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 31 SdHoareTripleChecker+Invalid, 89 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 86 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-15 20:56:45,968 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [27 Valid, 31 Invalid, 89 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 86 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-15 20:56:45,970 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1123 states. [2022-03-15 20:56:45,987 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1123 to 899. [2022-03-15 20:56:45,989 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 899 states, 898 states have (on average 5.697104677060134) internal successors, (5116), 898 states have internal predecessors, (5116), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:56:45,993 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 899 states to 899 states and 5116 transitions. [2022-03-15 20:56:45,993 INFO L78 Accepts]: Start accepts. Automaton has 899 states and 5116 transitions. Word has length 24 [2022-03-15 20:56:45,993 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 20:56:45,993 INFO L470 AbstractCegarLoop]: Abstraction has 899 states and 5116 transitions. [2022-03-15 20:56:45,993 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 9.75) internal successors, (39), 4 states have internal predecessors, (39), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:56:45,993 INFO L276 IsEmpty]: Start isEmpty. Operand 899 states and 5116 transitions. [2022-03-15 20:56:45,996 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2022-03-15 20:56:45,996 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 20:56:45,996 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 20:56:46,012 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2022-03-15 20:56:46,211 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 20:56:46,214 INFO L402 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr2INUSE_VIOLATION (and 3 more)] === [2022-03-15 20:56:46,214 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 20:56:46,214 INFO L85 PathProgramCache]: Analyzing trace with hash -946881784, now seen corresponding path program 1 times [2022-03-15 20:56:46,215 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 20:56:46,215 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [490313580] [2022-03-15 20:56:46,215 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 20:56:46,215 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 20:56:46,221 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 20:56:46,250 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2022-03-15 20:56:46,250 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 20:56:46,251 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [490313580] [2022-03-15 20:56:46,251 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [490313580] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-15 20:56:46,251 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [907261948] [2022-03-15 20:56:46,251 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 20:56:46,251 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 20:56:46,251 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 20:56:46,252 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-15 20:56:46,255 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-15 20:56:46,282 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 20:56:46,283 INFO L263 TraceCheckSpWp]: Trace formula consists of 119 conjuncts, 3 conjunts are in the unsatisfiable core [2022-03-15 20:56:46,284 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-15 20:56:46,330 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2022-03-15 20:56:46,331 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-15 20:56:46,365 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2022-03-15 20:56:46,365 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [907261948] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-15 20:56:46,365 INFO L191 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-03-15 20:56:46,366 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [2, 2, 2] total 4 [2022-03-15 20:56:46,366 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [1750600958] [2022-03-15 20:56:46,366 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 20:56:46,367 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 20:56:46,440 INFO L252 McrAutomatonBuilder]: Finished intersection with 706 states and 2572 transitions. [2022-03-15 20:56:46,440 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 20:56:50,198 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 1 new interpolants: [16283#(or (<= n x1) (<= (+ x2 1) n))] [2022-03-15 20:56:50,198 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-15 20:56:50,198 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 20:56:50,198 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-15 20:56:50,199 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2022-03-15 20:56:50,199 INFO L87 Difference]: Start difference. First operand 899 states and 5116 transitions. Second operand has 5 states, 4 states have (on average 9.5) internal successors, (38), 4 states have internal predecessors, (38), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:56:50,273 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 20:56:50,273 INFO L93 Difference]: Finished difference Result 1792 states and 10223 transitions. [2022-03-15 20:56:50,273 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-15 20:56:50,274 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 9.5) internal successors, (38), 4 states have internal predecessors, (38), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 24 [2022-03-15 20:56:50,274 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 20:56:50,282 INFO L225 Difference]: With dead ends: 1792 [2022-03-15 20:56:50,282 INFO L226 Difference]: Without dead ends: 1298 [2022-03-15 20:56:50,282 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 729 GetRequests, 723 SyntacticMatches, 1 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2022-03-15 20:56:50,283 INFO L933 BasicCegarLoop]: 12 mSDtfsCounter, 26 mSDsluCounter, 51 mSDsCounter, 0 mSdLazyCounter, 86 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 26 SdHoareTripleChecker+Valid, 30 SdHoareTripleChecker+Invalid, 89 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 86 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-15 20:56:50,283 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [26 Valid, 30 Invalid, 89 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 86 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-15 20:56:50,284 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1298 states. [2022-03-15 20:56:50,305 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1298 to 1298. [2022-03-15 20:56:50,308 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1298 states, 1297 states have (on average 5.748650732459522) internal successors, (7456), 1297 states have internal predecessors, (7456), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:56:50,313 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1298 states to 1298 states and 7456 transitions. [2022-03-15 20:56:50,313 INFO L78 Accepts]: Start accepts. Automaton has 1298 states and 7456 transitions. Word has length 24 [2022-03-15 20:56:50,313 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 20:56:50,313 INFO L470 AbstractCegarLoop]: Abstraction has 1298 states and 7456 transitions. [2022-03-15 20:56:50,313 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 9.5) internal successors, (38), 4 states have internal predecessors, (38), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:56:50,314 INFO L276 IsEmpty]: Start isEmpty. Operand 1298 states and 7456 transitions. [2022-03-15 20:56:50,317 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2022-03-15 20:56:50,317 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 20:56:50,317 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 20:56:50,337 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-15 20:56:50,535 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 20:56:50,535 INFO L402 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr2INUSE_VIOLATION (and 3 more)] === [2022-03-15 20:56:50,536 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 20:56:50,536 INFO L85 PathProgramCache]: Analyzing trace with hash -2135311353, now seen corresponding path program 1 times [2022-03-15 20:56:50,536 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 20:56:50,536 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1366989421] [2022-03-15 20:56:50,536 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 20:56:50,537 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 20:56:50,542 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 20:56:50,564 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-15 20:56:50,564 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 20:56:50,564 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1366989421] [2022-03-15 20:56:50,564 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1366989421] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-15 20:56:50,565 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2041205547] [2022-03-15 20:56:50,565 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 20:56:50,565 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 20:56:50,565 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 20:56:50,566 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-15 20:56:50,575 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-15 20:56:50,598 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 20:56:50,599 INFO L263 TraceCheckSpWp]: Trace formula consists of 122 conjuncts, 3 conjunts are in the unsatisfiable core [2022-03-15 20:56:50,599 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-15 20:56:50,634 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-15 20:56:50,634 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-15 20:56:50,665 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-15 20:56:50,665 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2041205547] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-15 20:56:50,665 INFO L191 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-03-15 20:56:50,665 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [2, 2, 2] total 3 [2022-03-15 20:56:50,666 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [26053043] [2022-03-15 20:56:50,666 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 20:56:50,668 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 20:56:50,799 INFO L252 McrAutomatonBuilder]: Finished intersection with 1015 states and 3879 transitions. [2022-03-15 20:56:50,799 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 20:56:58,842 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 1 new interpolants: [20821#(or (<= (+ x5 1) n) (<= n x6))] [2022-03-15 20:56:58,843 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-15 20:56:58,843 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 20:56:58,843 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-15 20:56:58,843 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2022-03-15 20:56:58,843 INFO L87 Difference]: Start difference. First operand 1298 states and 7456 transitions. Second operand has 5 states, 4 states have (on average 13.0) internal successors, (52), 4 states have internal predecessors, (52), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:56:58,915 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 20:56:58,915 INFO L93 Difference]: Finished difference Result 1785 states and 10293 transitions. [2022-03-15 20:56:58,915 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-15 20:56:58,915 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 13.0) internal successors, (52), 4 states have internal predecessors, (52), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 25 [2022-03-15 20:56:58,915 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 20:56:58,924 INFO L225 Difference]: With dead ends: 1785 [2022-03-15 20:56:58,924 INFO L226 Difference]: Without dead ends: 1337 [2022-03-15 20:56:58,924 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 1039 GetRequests, 972 SyntacticMatches, 63 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 124 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2022-03-15 20:56:58,924 INFO L933 BasicCegarLoop]: 13 mSDtfsCounter, 15 mSDsluCounter, 43 mSDsCounter, 0 mSdLazyCounter, 78 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 31 SdHoareTripleChecker+Invalid, 81 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 78 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-15 20:56:58,924 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [15 Valid, 31 Invalid, 81 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 78 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-15 20:56:58,926 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1337 states. [2022-03-15 20:56:58,944 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1337 to 1095. [2022-03-15 20:56:58,947 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1095 states, 1094 states have (on average 5.7221206581352835) internal successors, (6260), 1094 states have internal predecessors, (6260), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:56:58,951 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1095 states to 1095 states and 6260 transitions. [2022-03-15 20:56:58,951 INFO L78 Accepts]: Start accepts. Automaton has 1095 states and 6260 transitions. Word has length 25 [2022-03-15 20:56:58,951 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 20:56:58,951 INFO L470 AbstractCegarLoop]: Abstraction has 1095 states and 6260 transitions. [2022-03-15 20:56:58,951 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 13.0) internal successors, (52), 4 states have internal predecessors, (52), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:56:58,951 INFO L276 IsEmpty]: Start isEmpty. Operand 1095 states and 6260 transitions. [2022-03-15 20:56:58,955 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2022-03-15 20:56:58,955 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 20:56:58,955 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 20:56:58,976 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2022-03-15 20:56:59,175 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 20:56:59,176 INFO L402 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr2INUSE_VIOLATION (and 3 more)] === [2022-03-15 20:56:59,176 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 20:56:59,176 INFO L85 PathProgramCache]: Analyzing trace with hash -2130443431, now seen corresponding path program 1 times [2022-03-15 20:56:59,177 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 20:56:59,177 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [665715170] [2022-03-15 20:56:59,177 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 20:56:59,177 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 20:56:59,184 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 20:56:59,216 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-15 20:56:59,217 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 20:56:59,217 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [665715170] [2022-03-15 20:56:59,217 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [665715170] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-15 20:56:59,217 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1622853709] [2022-03-15 20:56:59,217 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 20:56:59,217 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 20:56:59,217 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 20:56:59,218 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-15 20:56:59,219 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-15 20:56:59,249 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 20:56:59,250 INFO L263 TraceCheckSpWp]: Trace formula consists of 122 conjuncts, 3 conjunts are in the unsatisfiable core [2022-03-15 20:56:59,252 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-15 20:56:59,323 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-15 20:56:59,323 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-15 20:56:59,363 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-15 20:56:59,363 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1622853709] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-15 20:56:59,363 INFO L191 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-03-15 20:56:59,363 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [2, 2, 2] total 3 [2022-03-15 20:56:59,363 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [207634874] [2022-03-15 20:56:59,364 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 20:56:59,365 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 20:56:59,482 INFO L252 McrAutomatonBuilder]: Finished intersection with 1095 states and 4255 transitions. [2022-03-15 20:56:59,482 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 20:57:07,293 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 1 new interpolants: [24946#(or (<= (+ x6 1) n) (<= n x5))] [2022-03-15 20:57:07,293 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-15 20:57:07,294 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 20:57:07,294 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-15 20:57:07,294 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2022-03-15 20:57:07,294 INFO L87 Difference]: Start difference. First operand 1095 states and 6260 transitions. Second operand has 5 states, 4 states have (on average 12.25) internal successors, (49), 4 states have internal predecessors, (49), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:57:07,368 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 20:57:07,368 INFO L93 Difference]: Finished difference Result 1824 states and 10513 transitions. [2022-03-15 20:57:07,368 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-15 20:57:07,369 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 12.25) internal successors, (49), 4 states have internal predecessors, (49), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 25 [2022-03-15 20:57:07,369 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 20:57:07,378 INFO L225 Difference]: With dead ends: 1824 [2022-03-15 20:57:07,378 INFO L226 Difference]: Without dead ends: 1459 [2022-03-15 20:57:07,379 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 1119 GetRequests, 1083 SyntacticMatches, 32 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 62 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2022-03-15 20:57:07,379 INFO L933 BasicCegarLoop]: 12 mSDtfsCounter, 17 mSDsluCounter, 43 mSDsCounter, 0 mSdLazyCounter, 80 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 30 SdHoareTripleChecker+Invalid, 83 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 80 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-15 20:57:07,379 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [17 Valid, 30 Invalid, 83 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 80 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-15 20:57:07,381 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1459 states. [2022-03-15 20:57:07,405 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1459 to 1459. [2022-03-15 20:57:07,408 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1459 states, 1458 states have (on average 5.751714677640604) internal successors, (8386), 1458 states have internal predecessors, (8386), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:57:07,414 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1459 states to 1459 states and 8386 transitions. [2022-03-15 20:57:07,414 INFO L78 Accepts]: Start accepts. Automaton has 1459 states and 8386 transitions. Word has length 25 [2022-03-15 20:57:07,414 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 20:57:07,414 INFO L470 AbstractCegarLoop]: Abstraction has 1459 states and 8386 transitions. [2022-03-15 20:57:07,414 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 12.25) internal successors, (49), 4 states have internal predecessors, (49), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:57:07,414 INFO L276 IsEmpty]: Start isEmpty. Operand 1459 states and 8386 transitions. [2022-03-15 20:57:07,419 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2022-03-15 20:57:07,419 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 20:57:07,419 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 20:57:07,441 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-15 20:57:07,641 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 20:57:07,642 INFO L402 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr2INUSE_VIOLATION (and 3 more)] === [2022-03-15 20:57:07,642 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 20:57:07,642 INFO L85 PathProgramCache]: Analyzing trace with hash -1906459408, now seen corresponding path program 1 times [2022-03-15 20:57:07,643 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 20:57:07,643 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [104557744] [2022-03-15 20:57:07,643 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 20:57:07,643 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 20:57:07,651 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 20:57:07,677 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-15 20:57:07,677 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 20:57:07,677 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [104557744] [2022-03-15 20:57:07,677 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [104557744] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-15 20:57:07,678 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [814596625] [2022-03-15 20:57:07,678 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 20:57:07,678 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 20:57:07,678 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 20:57:07,679 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-15 20:57:07,679 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-15 20:57:07,739 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 20:57:07,740 INFO L263 TraceCheckSpWp]: Trace formula consists of 125 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-15 20:57:07,740 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-15 20:57:07,819 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-15 20:57:07,820 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-15 20:57:07,855 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-15 20:57:07,855 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [814596625] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-15 20:57:07,855 INFO L191 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-03-15 20:57:07,855 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [2, 3, 2] total 5 [2022-03-15 20:57:07,855 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [1378889824] [2022-03-15 20:57:07,855 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 20:57:07,857 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 20:57:08,071 INFO L252 McrAutomatonBuilder]: Finished intersection with 1459 states and 5834 transitions. [2022-03-15 20:57:08,072 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 20:57:19,229 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 1 new interpolants: [29846#(= (* 2 x3) x4)] [2022-03-15 20:57:19,229 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-15 20:57:19,230 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 20:57:19,230 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-15 20:57:19,230 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2022-03-15 20:57:19,230 INFO L87 Difference]: Start difference. First operand 1459 states and 8386 transitions. Second operand has 5 states, 4 states have (on average 14.0) internal successors, (56), 4 states have internal predecessors, (56), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:57:19,338 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 20:57:19,339 INFO L93 Difference]: Finished difference Result 4029 states and 23214 transitions. [2022-03-15 20:57:19,339 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-15 20:57:19,339 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 14.0) internal successors, (56), 4 states have internal predecessors, (56), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 26 [2022-03-15 20:57:19,339 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 20:57:19,359 INFO L225 Difference]: With dead ends: 4029 [2022-03-15 20:57:19,359 INFO L226 Difference]: Without dead ends: 3854 [2022-03-15 20:57:19,359 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 1485 GetRequests, 713 SyntacticMatches, 766 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2022-03-15 20:57:19,359 INFO L933 BasicCegarLoop]: 19 mSDtfsCounter, 11 mSDsluCounter, 119 mSDsCounter, 0 mSdLazyCounter, 152 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 56 SdHoareTripleChecker+Invalid, 152 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 152 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-15 20:57:19,360 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 56 Invalid, 152 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 152 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-15 20:57:19,364 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3854 states. [2022-03-15 20:57:19,441 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3854 to 2872. [2022-03-15 20:57:19,464 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 2872 states, 2871 states have (on average 6.115290839428771) internal successors, (17557), 2871 states have internal predecessors, (17557), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:57:19,476 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2872 states to 2872 states and 17557 transitions. [2022-03-15 20:57:19,477 INFO L78 Accepts]: Start accepts. Automaton has 2872 states and 17557 transitions. Word has length 26 [2022-03-15 20:57:19,477 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 20:57:19,477 INFO L470 AbstractCegarLoop]: Abstraction has 2872 states and 17557 transitions. [2022-03-15 20:57:19,477 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 14.0) internal successors, (56), 4 states have internal predecessors, (56), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:57:19,478 INFO L276 IsEmpty]: Start isEmpty. Operand 2872 states and 17557 transitions. [2022-03-15 20:57:19,502 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2022-03-15 20:57:19,502 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 20:57:19,502 INFO L514 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 20:57:19,527 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-15 20:57:19,703 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 20:57:19,703 INFO L402 AbstractCegarLoop]: === Iteration 11 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr2INUSE_VIOLATION (and 3 more)] === [2022-03-15 20:57:19,703 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 20:57:19,703 INFO L85 PathProgramCache]: Analyzing trace with hash 1038505011, now seen corresponding path program 2 times [2022-03-15 20:57:19,704 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 20:57:19,705 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1807772939] [2022-03-15 20:57:19,705 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 20:57:19,705 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 20:57:19,710 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 20:57:19,744 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-15 20:57:19,744 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 20:57:19,744 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1807772939] [2022-03-15 20:57:19,744 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1807772939] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-15 20:57:19,744 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [455509734] [2022-03-15 20:57:19,745 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-15 20:57:19,745 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 20:57:19,745 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 20:57:19,746 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-15 20:57:19,747 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-15 20:57:19,779 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-15 20:57:19,780 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-15 20:57:19,780 INFO L263 TraceCheckSpWp]: Trace formula consists of 128 conjuncts, 5 conjunts are in the unsatisfiable core [2022-03-15 20:57:19,781 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-15 20:57:19,865 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-15 20:57:19,866 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-15 20:57:19,924 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-15 20:57:19,924 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [455509734] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-15 20:57:19,924 INFO L191 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-03-15 20:57:19,924 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4, 3] total 6 [2022-03-15 20:57:19,924 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [1116878710] [2022-03-15 20:57:19,924 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 20:57:19,926 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 20:57:20,253 INFO L252 McrAutomatonBuilder]: Finished intersection with 1927 states and 7889 transitions. [2022-03-15 20:57:20,253 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 20:57:35,723 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 2 new interpolants: [39784#(or (<= (+ (* 2 x3) 1) n) (not (< x3 n))), 39785#(or (<= (* 2 x3) x4) (not (< x3 n)))] [2022-03-15 20:57:35,724 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-03-15 20:57:35,724 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 20:57:35,724 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-03-15 20:57:35,724 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=70, Unknown=0, NotChecked=0, Total=90 [2022-03-15 20:57:35,724 INFO L87 Difference]: Start difference. First operand 2872 states and 17557 transitions. Second operand has 8 states, 7 states have (on average 13.857142857142858) internal successors, (97), 7 states have internal predecessors, (97), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:57:35,952 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 20:57:35,952 INFO L93 Difference]: Finished difference Result 5139 states and 29655 transitions. [2022-03-15 20:57:35,952 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-03-15 20:57:35,952 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 13.857142857142858) internal successors, (97), 7 states have internal predecessors, (97), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 27 [2022-03-15 20:57:35,952 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 20:57:35,970 INFO L225 Difference]: With dead ends: 5139 [2022-03-15 20:57:35,970 INFO L226 Difference]: Without dead ends: 3795 [2022-03-15 20:57:35,970 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 1959 GetRequests, 1750 SyntacticMatches, 197 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 292 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=38, Invalid=144, Unknown=0, NotChecked=0, Total=182 [2022-03-15 20:57:35,971 INFO L933 BasicCegarLoop]: 25 mSDtfsCounter, 24 mSDsluCounter, 286 mSDsCounter, 0 mSdLazyCounter, 342 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 135 SdHoareTripleChecker+Invalid, 348 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 342 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-03-15 20:57:35,971 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [24 Valid, 135 Invalid, 348 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 342 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-03-15 20:57:35,975 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3795 states. [2022-03-15 20:57:36,032 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3795 to 2548. [2022-03-15 20:57:36,037 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 2548 states, 2547 states have (on average 5.974479780133491) internal successors, (15217), 2547 states have internal predecessors, (15217), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:57:36,048 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2548 states to 2548 states and 15217 transitions. [2022-03-15 20:57:36,048 INFO L78 Accepts]: Start accepts. Automaton has 2548 states and 15217 transitions. Word has length 27 [2022-03-15 20:57:36,048 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 20:57:36,049 INFO L470 AbstractCegarLoop]: Abstraction has 2548 states and 15217 transitions. [2022-03-15 20:57:36,049 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 13.857142857142858) internal successors, (97), 7 states have internal predecessors, (97), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:57:36,049 INFO L276 IsEmpty]: Start isEmpty. Operand 2548 states and 15217 transitions. [2022-03-15 20:57:36,055 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2022-03-15 20:57:36,056 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 20:57:36,056 INFO L514 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 20:57:36,089 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-15 20:57:36,270 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2022-03-15 20:57:36,270 INFO L402 AbstractCegarLoop]: === Iteration 12 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr2INUSE_VIOLATION (and 3 more)] === [2022-03-15 20:57:36,271 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 20:57:36,271 INFO L85 PathProgramCache]: Analyzing trace with hash -773370403, now seen corresponding path program 3 times [2022-03-15 20:57:36,271 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 20:57:36,271 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [505779244] [2022-03-15 20:57:36,272 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 20:57:36,272 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 20:57:36,277 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 20:57:36,313 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-15 20:57:36,313 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 20:57:36,313 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [505779244] [2022-03-15 20:57:36,313 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [505779244] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-15 20:57:36,313 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [423038752] [2022-03-15 20:57:36,313 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-03-15 20:57:36,313 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 20:57:36,314 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 20:57:36,314 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-15 20:57:36,315 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-15 20:57:36,346 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2022-03-15 20:57:36,346 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-15 20:57:36,347 INFO L263 TraceCheckSpWp]: Trace formula consists of 128 conjuncts, 5 conjunts are in the unsatisfiable core [2022-03-15 20:57:36,347 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-15 20:57:36,407 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-15 20:57:36,407 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-15 20:57:36,449 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-15 20:57:36,450 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [423038752] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-15 20:57:36,450 INFO L191 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-03-15 20:57:36,450 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4, 4] total 6 [2022-03-15 20:57:36,450 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [1269981256] [2022-03-15 20:57:36,450 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 20:57:36,451 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 20:57:36,776 INFO L252 McrAutomatonBuilder]: Finished intersection with 1927 states and 7889 transitions. [2022-03-15 20:57:36,777 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 20:57:54,209 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 2 new interpolants: [50194#(or (<= (+ x4 1) n) (<= n (* 2 x3)) (not (< x3 n))), 50193#(or (<= (+ x4 1) n) (<= n x3))] [2022-03-15 20:57:54,209 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-03-15 20:57:54,209 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 20:57:54,210 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-03-15 20:57:54,210 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2022-03-15 20:57:54,210 INFO L87 Difference]: Start difference. First operand 2548 states and 15217 transitions. Second operand has 8 states, 7 states have (on average 13.857142857142858) internal successors, (97), 7 states have internal predecessors, (97), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:57:54,357 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 20:57:54,358 INFO L93 Difference]: Finished difference Result 4118 states and 24512 transitions. [2022-03-15 20:57:54,358 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-03-15 20:57:54,358 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 13.857142857142858) internal successors, (97), 7 states have internal predecessors, (97), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 27 [2022-03-15 20:57:54,358 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 20:57:54,377 INFO L225 Difference]: With dead ends: 4118 [2022-03-15 20:57:54,377 INFO L226 Difference]: Without dead ends: 3322 [2022-03-15 20:57:54,378 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 1957 GetRequests, 1785 SyntacticMatches, 162 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 485 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=40, Invalid=92, Unknown=0, NotChecked=0, Total=132 [2022-03-15 20:57:54,379 INFO L933 BasicCegarLoop]: 17 mSDtfsCounter, 27 mSDsluCounter, 125 mSDsCounter, 0 mSdLazyCounter, 176 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 70 SdHoareTripleChecker+Invalid, 186 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 176 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-15 20:57:54,379 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [27 Valid, 70 Invalid, 186 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 176 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-15 20:57:54,384 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3322 states. [2022-03-15 20:57:54,463 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3322 to 3322. [2022-03-15 20:57:54,471 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3322 states, 3321 states have (on average 5.947907256850346) internal successors, (19753), 3321 states have internal predecessors, (19753), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:57:54,489 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3322 states to 3322 states and 19753 transitions. [2022-03-15 20:57:54,489 INFO L78 Accepts]: Start accepts. Automaton has 3322 states and 19753 transitions. Word has length 27 [2022-03-15 20:57:54,489 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 20:57:54,489 INFO L470 AbstractCegarLoop]: Abstraction has 3322 states and 19753 transitions. [2022-03-15 20:57:54,490 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 13.857142857142858) internal successors, (97), 7 states have internal predecessors, (97), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:57:54,490 INFO L276 IsEmpty]: Start isEmpty. Operand 3322 states and 19753 transitions. [2022-03-15 20:57:54,500 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2022-03-15 20:57:54,501 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 20:57:54,501 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 20:57:54,541 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2022-03-15 20:57:54,715 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 20:57:54,715 INFO L402 AbstractCegarLoop]: === Iteration 13 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr2INUSE_VIOLATION (and 3 more)] === [2022-03-15 20:57:54,716 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 20:57:54,716 INFO L85 PathProgramCache]: Analyzing trace with hash 1804525798, now seen corresponding path program 4 times [2022-03-15 20:57:54,717 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 20:57:54,717 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [483983447] [2022-03-15 20:57:54,717 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 20:57:54,717 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 20:57:54,724 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 20:57:54,769 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-15 20:57:54,769 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 20:57:54,769 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [483983447] [2022-03-15 20:57:54,769 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [483983447] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-15 20:57:54,769 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [762525801] [2022-03-15 20:57:54,769 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-03-15 20:57:54,769 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 20:57:54,770 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 20:57:54,771 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-15 20:57:54,771 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-15 20:57:54,806 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-03-15 20:57:54,806 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-15 20:57:54,806 INFO L263 TraceCheckSpWp]: Trace formula consists of 131 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-15 20:57:54,807 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-15 20:57:54,895 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2022-03-15 20:57:54,896 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-15 20:57:54,944 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2022-03-15 20:57:54,944 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [762525801] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-15 20:57:54,944 INFO L191 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-03-15 20:57:54,944 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [3, 3, 2] total 6 [2022-03-15 20:57:54,944 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [294482858] [2022-03-15 20:57:54,944 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 20:57:54,946 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 20:57:55,382 INFO L252 McrAutomatonBuilder]: Finished intersection with 2548 states and 10670 transitions. [2022-03-15 20:57:55,382 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 20:58:16,850 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 2 new interpolants: [61131#(= (* 2 x3) x4), 61132#(= (* x3 4) x4)] [2022-03-15 20:58:16,850 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-03-15 20:58:16,850 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 20:58:16,851 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-03-15 20:58:16,851 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=72, Unknown=0, NotChecked=0, Total=90 [2022-03-15 20:58:16,851 INFO L87 Difference]: Start difference. First operand 3322 states and 19753 transitions. Second operand has 7 states, 6 states have (on average 14.666666666666666) internal successors, (88), 6 states have internal predecessors, (88), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:58:17,072 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 20:58:17,072 INFO L93 Difference]: Finished difference Result 8728 states and 50761 transitions. [2022-03-15 20:58:17,072 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-03-15 20:58:17,072 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 14.666666666666666) internal successors, (88), 6 states have internal predecessors, (88), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 28 [2022-03-15 20:58:17,072 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 20:58:17,108 INFO L225 Difference]: With dead ends: 8728 [2022-03-15 20:58:17,108 INFO L226 Difference]: Without dead ends: 8553 [2022-03-15 20:58:17,108 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 2578 GetRequests, 1595 SyntacticMatches, 975 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 31 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=18, Invalid=72, Unknown=0, NotChecked=0, Total=90 [2022-03-15 20:58:17,109 INFO L933 BasicCegarLoop]: 31 mSDtfsCounter, 22 mSDsluCounter, 385 mSDsCounter, 0 mSdLazyCounter, 407 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 152 SdHoareTripleChecker+Invalid, 407 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 407 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-03-15 20:58:17,110 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [22 Valid, 152 Invalid, 407 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 407 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-03-15 20:58:17,120 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 8553 states. [2022-03-15 20:58:17,308 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 8553 to 6283. [2022-03-15 20:58:17,324 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6283 states, 6282 states have (on average 6.1959567016873605) internal successors, (38923), 6282 states have internal predecessors, (38923), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:58:17,353 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6283 states to 6283 states and 38923 transitions. [2022-03-15 20:58:17,354 INFO L78 Accepts]: Start accepts. Automaton has 6283 states and 38923 transitions. Word has length 28 [2022-03-15 20:58:17,354 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 20:58:17,354 INFO L470 AbstractCegarLoop]: Abstraction has 6283 states and 38923 transitions. [2022-03-15 20:58:17,354 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 14.666666666666666) internal successors, (88), 6 states have internal predecessors, (88), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:58:17,354 INFO L276 IsEmpty]: Start isEmpty. Operand 6283 states and 38923 transitions. [2022-03-15 20:58:17,376 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2022-03-15 20:58:17,376 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 20:58:17,376 INFO L514 BasicCegarLoop]: trace histogram [3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 20:58:17,392 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-15 20:58:17,587 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2022-03-15 20:58:17,587 INFO L402 AbstractCegarLoop]: === Iteration 14 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr2INUSE_VIOLATION (and 3 more)] === [2022-03-15 20:58:17,588 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 20:58:17,588 INFO L85 PathProgramCache]: Analyzing trace with hash 114929405, now seen corresponding path program 5 times [2022-03-15 20:58:17,589 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 20:58:17,589 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [102806621] [2022-03-15 20:58:17,589 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 20:58:17,589 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 20:58:17,594 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 20:58:17,624 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-15 20:58:17,624 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 20:58:17,624 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [102806621] [2022-03-15 20:58:17,625 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [102806621] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-15 20:58:17,625 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [872384057] [2022-03-15 20:58:17,625 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2022-03-15 20:58:17,625 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 20:58:17,625 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 20:58:17,626 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-15 20:58:17,630 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2022-03-15 20:58:17,665 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 3 check-sat command(s) [2022-03-15 20:58:17,665 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-15 20:58:17,665 INFO L263 TraceCheckSpWp]: Trace formula consists of 134 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-15 20:58:17,666 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-15 20:58:17,757 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-15 20:58:17,757 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-15 20:58:17,819 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-15 20:58:17,819 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [872384057] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-15 20:58:17,819 INFO L191 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-03-15 20:58:17,819 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 6, 4] total 8 [2022-03-15 20:58:17,819 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [1691425041] [2022-03-15 20:58:17,819 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 20:58:17,821 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 20:58:18,570 INFO L252 McrAutomatonBuilder]: Finished intersection with 3169 states and 13451 transitions. [2022-03-15 20:58:18,571 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 20:58:51,395 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 6 new interpolants: [82606#(or (<= (* 2 x3) x4) (not (< x3 n))), 82607#(or (<= (* 2 x3) (* 2 x4)) (not (< x3 n))), 82608#(or (<= n (* 2 x3)) (<= (+ (* x3 4) 1) n)), 82609#(or (not (< (* 2 x3) n)) (<= (* x3 4) x4) (not (< x3 n))), 82610#(or (not (< (* 2 x3) n)) (<= (* x3 4) (* 2 x4)) (not (< x3 n))), 82605#(or (<= (+ (* 2 x3) 1) n) (not (< x3 n)))] [2022-03-15 20:58:51,396 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2022-03-15 20:58:51,396 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 20:58:51,396 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2022-03-15 20:58:51,396 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=37, Invalid=203, Unknown=0, NotChecked=0, Total=240 [2022-03-15 20:58:51,396 INFO L87 Difference]: Start difference. First operand 6283 states and 38923 transitions. Second operand has 13 states, 12 states have (on average 14.25) internal successors, (171), 12 states have internal predecessors, (171), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:58:51,885 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 20:58:51,885 INFO L93 Difference]: Finished difference Result 10480 states and 61213 transitions. [2022-03-15 20:58:51,885 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2022-03-15 20:58:51,885 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 12 states have (on average 14.25) internal successors, (171), 12 states have internal predecessors, (171), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 29 [2022-03-15 20:58:51,885 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 20:58:51,918 INFO L225 Difference]: With dead ends: 10480 [2022-03-15 20:58:51,918 INFO L226 Difference]: Without dead ends: 8300 [2022-03-15 20:58:51,918 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 3208 GetRequests, 2931 SyntacticMatches, 256 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 939 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=86, Invalid=420, Unknown=0, NotChecked=0, Total=506 [2022-03-15 20:58:51,918 INFO L933 BasicCegarLoop]: 37 mSDtfsCounter, 61 mSDsluCounter, 667 mSDsCounter, 0 mSdLazyCounter, 750 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 61 SdHoareTripleChecker+Valid, 298 SdHoareTripleChecker+Invalid, 763 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 750 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-03-15 20:58:51,919 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [61 Valid, 298 Invalid, 763 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 750 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-03-15 20:58:51,927 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 8300 states. [2022-03-15 20:58:52,039 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 8300 to 4573. [2022-03-15 20:58:52,049 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4573 states, 4572 states have (on average 6.021216097987751) internal successors, (27529), 4572 states have internal predecessors, (27529), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:58:52,068 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4573 states to 4573 states and 27529 transitions. [2022-03-15 20:58:52,068 INFO L78 Accepts]: Start accepts. Automaton has 4573 states and 27529 transitions. Word has length 29 [2022-03-15 20:58:52,068 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 20:58:52,068 INFO L470 AbstractCegarLoop]: Abstraction has 4573 states and 27529 transitions. [2022-03-15 20:58:52,069 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 12 states have (on average 14.25) internal successors, (171), 12 states have internal predecessors, (171), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:58:52,069 INFO L276 IsEmpty]: Start isEmpty. Operand 4573 states and 27529 transitions. [2022-03-15 20:58:52,082 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2022-03-15 20:58:52,082 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 20:58:52,082 INFO L514 BasicCegarLoop]: trace histogram [3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 20:58:52,101 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2022-03-15 20:58:52,291 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2022-03-15 20:58:52,292 INFO L402 AbstractCegarLoop]: === Iteration 15 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr2INUSE_VIOLATION (and 3 more)] === [2022-03-15 20:58:52,292 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 20:58:52,292 INFO L85 PathProgramCache]: Analyzing trace with hash -218633581, now seen corresponding path program 6 times [2022-03-15 20:58:52,293 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 20:58:52,293 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1068271446] [2022-03-15 20:58:52,293 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 20:58:52,293 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 20:58:52,298 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 20:58:52,330 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-15 20:58:52,331 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 20:58:52,331 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1068271446] [2022-03-15 20:58:52,331 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1068271446] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-15 20:58:52,331 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1631788078] [2022-03-15 20:58:52,331 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-03-15 20:58:52,331 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 20:58:52,331 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 20:58:52,332 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-15 20:58:52,367 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2022-03-15 20:58:52,404 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 3 check-sat command(s) [2022-03-15 20:58:52,404 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-15 20:58:52,405 INFO L263 TraceCheckSpWp]: Trace formula consists of 134 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-15 20:58:52,405 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-15 20:58:52,480 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-15 20:58:52,481 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-15 20:58:52,544 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-15 20:58:52,545 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1631788078] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-15 20:58:52,545 INFO L191 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-03-15 20:58:52,545 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 6] total 9 [2022-03-15 20:58:52,545 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [1992537900] [2022-03-15 20:58:52,545 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 20:58:52,547 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 20:58:53,187 INFO L252 McrAutomatonBuilder]: Finished intersection with 3169 states and 13451 transitions. [2022-03-15 20:58:53,188 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 20:59:32,120 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 6 new interpolants: [102434#(or (<= (+ x4 1) n) (<= n x3) (<= n (* x3 4))), 102432#(or (<= (+ x4 1) n) (<= n (* 2 x3)) (not (< x3 n))), 102433#(or (<= n (* 2 x3)) (<= (+ (* 2 x4) 1) n) (not (< x3 n))), 102435#(or (<= n (* x3 4)) (<= (+ (* 2 x4) 1) n) (not (< x3 n))), 102430#(or (<= (+ x4 1) n) (<= n x3)), 102431#(or (<= n x3) (<= (+ (* 2 x4) 1) n))] [2022-03-15 20:59:32,121 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2022-03-15 20:59:32,121 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 20:59:32,121 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-03-15 20:59:32,121 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=65, Invalid=207, Unknown=0, NotChecked=0, Total=272 [2022-03-15 20:59:32,121 INFO L87 Difference]: Start difference. First operand 4573 states and 27529 transitions. Second operand has 14 states, 13 states have (on average 14.076923076923077) internal successors, (183), 13 states have internal predecessors, (183), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:59:32,538 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 20:59:32,539 INFO L93 Difference]: Finished difference Result 11383 states and 67504 transitions. [2022-03-15 20:59:32,539 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2022-03-15 20:59:32,539 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 13 states have (on average 14.076923076923077) internal successors, (183), 13 states have internal predecessors, (183), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 29 [2022-03-15 20:59:32,539 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 20:59:32,571 INFO L225 Difference]: With dead ends: 11383 [2022-03-15 20:59:32,571 INFO L226 Difference]: Without dead ends: 7669 [2022-03-15 20:59:32,572 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 3209 GetRequests, 2965 SyntacticMatches, 221 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1349 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=164, Invalid=436, Unknown=0, NotChecked=0, Total=600 [2022-03-15 20:59:32,572 INFO L933 BasicCegarLoop]: 28 mSDtfsCounter, 76 mSDsluCounter, 391 mSDsCounter, 0 mSdLazyCounter, 459 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 76 SdHoareTripleChecker+Valid, 193 SdHoareTripleChecker+Invalid, 475 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 459 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-03-15 20:59:32,572 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [76 Valid, 193 Invalid, 475 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 459 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-03-15 20:59:32,580 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 7669 states. [2022-03-15 20:59:32,680 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 7669 to 5653. [2022-03-15 20:59:32,692 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5653 states, 5652 states have (on average 5.9916843595187546) internal successors, (33865), 5652 states have internal predecessors, (33865), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:59:32,716 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5653 states to 5653 states and 33865 transitions. [2022-03-15 20:59:32,716 INFO L78 Accepts]: Start accepts. Automaton has 5653 states and 33865 transitions. Word has length 29 [2022-03-15 20:59:32,716 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 20:59:32,716 INFO L470 AbstractCegarLoop]: Abstraction has 5653 states and 33865 transitions. [2022-03-15 20:59:32,716 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 13 states have (on average 14.076923076923077) internal successors, (183), 13 states have internal predecessors, (183), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:59:32,716 INFO L276 IsEmpty]: Start isEmpty. Operand 5653 states and 33865 transitions. [2022-03-15 20:59:32,731 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2022-03-15 20:59:32,731 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 20:59:32,731 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 20:59:32,749 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2022-03-15 20:59:32,944 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2022-03-15 20:59:32,944 INFO L402 AbstractCegarLoop]: === Iteration 16 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr2INUSE_VIOLATION (and 3 more)] === [2022-03-15 20:59:32,944 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 20:59:32,945 INFO L85 PathProgramCache]: Analyzing trace with hash 1821498096, now seen corresponding path program 7 times [2022-03-15 20:59:32,945 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 20:59:32,945 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1616538785] [2022-03-15 20:59:32,945 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 20:59:32,945 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 20:59:32,950 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 20:59:33,004 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-15 20:59:33,005 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 20:59:33,005 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1616538785] [2022-03-15 20:59:33,005 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1616538785] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-15 20:59:33,005 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1451489625] [2022-03-15 20:59:33,005 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2022-03-15 20:59:33,005 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 20:59:33,005 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 20:59:33,006 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-15 20:59:33,007 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2022-03-15 20:59:33,040 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 20:59:33,041 INFO L263 TraceCheckSpWp]: Trace formula consists of 137 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-15 20:59:33,042 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-15 20:59:33,129 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2022-03-15 20:59:33,129 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-15 20:59:33,173 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2022-03-15 20:59:33,173 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1451489625] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-15 20:59:33,173 INFO L191 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-03-15 20:59:33,174 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 3, 2] total 7 [2022-03-15 20:59:33,174 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [644597816] [2022-03-15 20:59:33,174 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 20:59:33,176 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 20:59:34,056 INFO L252 McrAutomatonBuilder]: Finished intersection with 3943 states and 16958 transitions. [2022-03-15 20:59:34,056 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 21:00:10,132 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 3 new interpolants: [125324#(= (* 2 x3) x4), 125326#(= (* x3 8) x4), 125325#(= (* x3 4) x4)] [2022-03-15 21:00:10,132 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-03-15 21:00:10,132 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 21:00:10,132 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-03-15 21:00:10,133 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=110, Unknown=0, NotChecked=0, Total=132 [2022-03-15 21:00:10,133 INFO L87 Difference]: Start difference. First operand 5653 states and 33865 transitions. Second operand has 9 states, 8 states have (on average 15.0) internal successors, (120), 8 states have internal predecessors, (120), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 21:00:10,620 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 21:00:10,620 INFO L93 Difference]: Finished difference Result 14363 states and 83942 transitions. [2022-03-15 21:00:10,621 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-03-15 21:00:10,621 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 15.0) internal successors, (120), 8 states have internal predecessors, (120), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 30 [2022-03-15 21:00:10,621 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 21:00:10,692 INFO L225 Difference]: With dead ends: 14363 [2022-03-15 21:00:10,692 INFO L226 Difference]: Without dead ends: 14188 [2022-03-15 21:00:10,692 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 3977 GetRequests, 2756 SyntacticMatches, 1211 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 60 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=22, Invalid=110, Unknown=0, NotChecked=0, Total=132 [2022-03-15 21:00:10,693 INFO L933 BasicCegarLoop]: 43 mSDtfsCounter, 33 mSDsluCounter, 799 mSDsCounter, 0 mSdLazyCounter, 786 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 33 SdHoareTripleChecker+Valid, 296 SdHoareTripleChecker+Invalid, 786 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 786 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-03-15 21:00:10,693 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [33 Valid, 296 Invalid, 786 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 786 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-03-15 21:00:10,711 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 14188 states. [2022-03-15 21:00:10,948 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 14188 to 10783. [2022-03-15 21:00:10,973 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 10783 states, 10782 states have (on average 6.183453904655908) internal successors, (66670), 10782 states have internal predecessors, (66670), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 21:00:11,029 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10783 states to 10783 states and 66670 transitions. [2022-03-15 21:00:11,030 INFO L78 Accepts]: Start accepts. Automaton has 10783 states and 66670 transitions. Word has length 30 [2022-03-15 21:00:11,030 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 21:00:11,030 INFO L470 AbstractCegarLoop]: Abstraction has 10783 states and 66670 transitions. [2022-03-15 21:00:11,030 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 15.0) internal successors, (120), 8 states have internal predecessors, (120), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 21:00:11,030 INFO L276 IsEmpty]: Start isEmpty. Operand 10783 states and 66670 transitions. [2022-03-15 21:00:11,065 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2022-03-15 21:00:11,066 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 21:00:11,066 INFO L514 BasicCegarLoop]: trace histogram [4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 21:00:11,083 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2022-03-15 21:00:11,279 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2022-03-15 21:00:11,280 INFO L402 AbstractCegarLoop]: === Iteration 17 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr2INUSE_VIOLATION (and 3 more)] === [2022-03-15 21:00:11,280 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 21:00:11,280 INFO L85 PathProgramCache]: Analyzing trace with hash 641070643, now seen corresponding path program 8 times [2022-03-15 21:00:11,281 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 21:00:11,281 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1470056848] [2022-03-15 21:00:11,281 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 21:00:11,281 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 21:00:11,285 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 21:00:11,326 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 0 proven. 16 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-15 21:00:11,326 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 21:00:11,326 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1470056848] [2022-03-15 21:00:11,326 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1470056848] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-15 21:00:11,326 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [22254734] [2022-03-15 21:00:11,326 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-15 21:00:11,327 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 21:00:11,327 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 21:00:11,344 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-15 21:00:11,376 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2022-03-15 21:00:11,392 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-15 21:00:11,392 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-15 21:00:11,393 INFO L263 TraceCheckSpWp]: Trace formula consists of 140 conjuncts, 9 conjunts are in the unsatisfiable core [2022-03-15 21:00:11,394 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-15 21:00:11,494 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 0 proven. 16 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-15 21:00:11,495 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-15 21:00:11,561 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 0 proven. 16 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-15 21:00:11,562 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [22254734] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-15 21:00:11,562 INFO L191 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-03-15 21:00:11,562 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 8, 5] total 10 [2022-03-15 21:00:11,562 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [1217829788] [2022-03-15 21:00:11,562 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 21:00:11,564 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 21:00:12,704 INFO L252 McrAutomatonBuilder]: Finished intersection with 4717 states and 20465 transitions. [2022-03-15 21:00:12,704 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 21:01:17,671 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 12 new interpolants: [161458#(or (<= n x3) (<= n (* x3 4)) (<= (* x3 8) (* 2 x4))), 161451#(or (not (< (* 2 x3) n)) (<= (* x3 4) x4) (not (< x3 n))), 161453#(or (<= (* 2 x3) (* x4 4)) (not (< x3 n))), 161449#(or (<= (* 2 x3) x4) (not (< x3 n))), 161450#(or (<= n (* 2 x3)) (<= (+ (* x3 4) 1) n)), 161452#(or (<= (* 2 x3) (* 2 x4)) (not (< x3 n))), 161457#(or (<= (* x3 8) x4) (<= n x3) (<= n (* x3 4))), 161448#(or (<= (+ (* 2 x3) 1) n) (not (< x3 n))), 161455#(or (<= n x3) (<= (* x3 4) (* x4 4)) (<= n (* 2 x3))), 161456#(or (<= n (* x3 4)) (<= (+ (* x3 8) 1) n)), 161459#(or (<= n x3) (<= (* x3 8) (* x4 4)) (<= n (* x3 4))), 161454#(or (not (< (* 2 x3) n)) (<= (* x3 4) (* 2 x4)) (not (< x3 n)))] [2022-03-15 21:01:17,672 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2022-03-15 21:01:17,672 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 21:01:17,672 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2022-03-15 21:01:17,672 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=63, Invalid=489, Unknown=0, NotChecked=0, Total=552 [2022-03-15 21:01:17,673 INFO L87 Difference]: Start difference. First operand 10783 states and 66670 transitions. Second operand has 20 states, 19 states have (on average 14.368421052631579) internal successors, (273), 19 states have internal predecessors, (273), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 21:01:18,578 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 21:01:18,578 INFO L93 Difference]: Finished difference Result 17216 states and 100952 transitions. [2022-03-15 21:01:18,578 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2022-03-15 21:01:18,578 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 19 states have (on average 14.368421052631579) internal successors, (273), 19 states have internal predecessors, (273), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 31 [2022-03-15 21:01:18,578 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 21:01:18,636 INFO L225 Difference]: With dead ends: 17216 [2022-03-15 21:01:18,636 INFO L226 Difference]: Without dead ends: 14200 [2022-03-15 21:01:18,637 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 4763 GetRequests, 4432 SyntacticMatches, 299 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1929 ImplicationChecksByTransitivity, 1.9s TimeCoverageRelationStatistics Valid=164, Invalid=958, Unknown=0, NotChecked=0, Total=1122 [2022-03-15 21:01:18,637 INFO L933 BasicCegarLoop]: 49 mSDtfsCounter, 88 mSDsluCounter, 1532 mSDsCounter, 0 mSdLazyCounter, 1632 mSolverCounterSat, 19 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 88 SdHoareTripleChecker+Valid, 654 SdHoareTripleChecker+Invalid, 1651 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 19 IncrementalHoareTripleChecker+Valid, 1632 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2022-03-15 21:01:18,637 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [88 Valid, 654 Invalid, 1651 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [19 Valid, 1632 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2022-03-15 21:01:18,652 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 14200 states. [2022-03-15 21:01:18,833 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 14200 to 7219. [2022-03-15 21:01:18,845 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 7219 states, 7218 states have (on average 6.023413688002217) internal successors, (43477), 7218 states have internal predecessors, (43477), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 21:01:18,960 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7219 states to 7219 states and 43477 transitions. [2022-03-15 21:01:18,960 INFO L78 Accepts]: Start accepts. Automaton has 7219 states and 43477 transitions. Word has length 31 [2022-03-15 21:01:18,960 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 21:01:18,960 INFO L470 AbstractCegarLoop]: Abstraction has 7219 states and 43477 transitions. [2022-03-15 21:01:18,960 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 19 states have (on average 14.368421052631579) internal successors, (273), 19 states have internal predecessors, (273), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 21:01:18,960 INFO L276 IsEmpty]: Start isEmpty. Operand 7219 states and 43477 transitions. [2022-03-15 21:01:18,982 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2022-03-15 21:01:18,983 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 21:01:18,983 INFO L514 BasicCegarLoop]: trace histogram [4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 21:01:19,007 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2022-03-15 21:01:19,198 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable16,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 21:01:19,199 INFO L402 AbstractCegarLoop]: === Iteration 18 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr2INUSE_VIOLATION (and 3 more)] === [2022-03-15 21:01:19,200 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 21:01:19,200 INFO L85 PathProgramCache]: Analyzing trace with hash -1109447331, now seen corresponding path program 9 times [2022-03-15 21:01:19,201 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 21:01:19,201 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1511587650] [2022-03-15 21:01:19,201 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 21:01:19,201 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 21:01:19,205 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 21:01:19,276 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 0 proven. 16 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-15 21:01:19,276 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 21:01:19,276 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1511587650] [2022-03-15 21:01:19,276 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1511587650] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-15 21:01:19,276 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1847564784] [2022-03-15 21:01:19,276 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-03-15 21:01:19,276 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 21:01:19,277 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 21:01:19,292 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-15 21:01:19,293 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2022-03-15 21:01:19,325 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2022-03-15 21:01:19,325 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-15 21:01:19,326 INFO L263 TraceCheckSpWp]: Trace formula consists of 131 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-15 21:01:19,327 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-15 21:01:19,460 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2022-03-15 21:01:19,460 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-15 21:01:19,509 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2022-03-15 21:01:19,510 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1847564784] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-15 21:01:19,510 INFO L191 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-03-15 21:01:19,510 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 3, 2] total 11 [2022-03-15 21:01:19,510 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [271834508] [2022-03-15 21:01:19,510 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 21:01:19,512 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 21:01:20,676 INFO L252 McrAutomatonBuilder]: Finished intersection with 4717 states and 20465 transitions. [2022-03-15 21:01:20,676 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 21:02:37,202 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 12 new interpolants: [193333#(or (<= n (* 2 x3)) (<= (+ (* x4 4) 1) n) (not (< x3 n))), 193338#(or (<= n x3) (<= n (* x3 8)) (<= (+ (* x4 4) 1) n)), 193327#(or (<= (+ x4 1) n) (<= n x3)), 193336#(or (<= (+ x4 1) n) (<= n x3) (<= n (* x3 8))), 193331#(or (<= n x3) (<= (+ (* x4 4) 1) n)), 193329#(or (<= (+ x4 1) n) (<= n x3) (<= n (* x3 4))), 193332#(or (<= n (* 2 x3)) (<= (+ (* 2 x4) 1) n) (not (< x3 n))), 193328#(or (<= (+ x4 1) n) (<= n (* 2 x3)) (not (< x3 n))), 193330#(or (<= n x3) (<= (+ (* 2 x4) 1) n)), 193335#(or (<= n (* x3 4)) (<= (+ (* x4 4) 1) n) (not (< x3 n))), 193334#(or (<= n (* x3 4)) (<= (+ (* 2 x4) 1) n) (not (< x3 n))), 193337#(or (<= n x3) (<= n (* x3 8)) (<= (+ (* 2 x4) 1) n))] [2022-03-15 21:02:37,202 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2022-03-15 21:02:37,202 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 21:02:37,203 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2022-03-15 21:02:37,203 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=98, Invalid=502, Unknown=0, NotChecked=0, Total=600 [2022-03-15 21:02:37,203 INFO L87 Difference]: Start difference. First operand 7219 states and 43477 transitions. Second operand has 22 states, 21 states have (on average 14.142857142857142) internal successors, (297), 21 states have internal predecessors, (297), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 21:02:37,982 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 21:02:37,982 INFO L93 Difference]: Finished difference Result 19877 states and 118211 transitions. [2022-03-15 21:02:37,982 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2022-03-15 21:02:37,983 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 21 states have (on average 14.142857142857142) internal successors, (297), 21 states have internal predecessors, (297), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 31 [2022-03-15 21:02:37,983 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 21:02:38,039 INFO L225 Difference]: With dead ends: 19877 [2022-03-15 21:02:38,039 INFO L226 Difference]: Without dead ends: 13258 [2022-03-15 21:02:38,040 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 4768 GetRequests, 4279 SyntacticMatches, 451 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4066 ImplicationChecksByTransitivity, 4.2s TimeCoverageRelationStatistics Valid=380, Invalid=1180, Unknown=0, NotChecked=0, Total=1560 [2022-03-15 21:02:38,040 INFO L933 BasicCegarLoop]: 36 mSDtfsCounter, 170 mSDsluCounter, 690 mSDsCounter, 0 mSdLazyCounter, 786 mSolverCounterSat, 28 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 170 SdHoareTripleChecker+Valid, 338 SdHoareTripleChecker+Invalid, 814 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 28 IncrementalHoareTripleChecker+Valid, 786 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-03-15 21:02:38,040 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [170 Valid, 338 Invalid, 814 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [28 Valid, 786 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-03-15 21:02:38,054 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 13258 states. [2022-03-15 21:02:38,259 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 13258 to 8605. [2022-03-15 21:02:38,273 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8605 states, 8604 states have (on average 5.998721524872153) internal successors, (51613), 8604 states have internal predecessors, (51613), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 21:02:38,308 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8605 states to 8605 states and 51613 transitions. [2022-03-15 21:02:38,308 INFO L78 Accepts]: Start accepts. Automaton has 8605 states and 51613 transitions. Word has length 31 [2022-03-15 21:02:38,308 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 21:02:38,308 INFO L470 AbstractCegarLoop]: Abstraction has 8605 states and 51613 transitions. [2022-03-15 21:02:38,308 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 21 states have (on average 14.142857142857142) internal successors, (297), 21 states have internal predecessors, (297), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 21:02:38,308 INFO L276 IsEmpty]: Start isEmpty. Operand 8605 states and 51613 transitions. [2022-03-15 21:02:38,329 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2022-03-15 21:02:38,329 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 21:02:38,329 INFO L514 BasicCegarLoop]: trace histogram [4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 21:02:38,345 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Ended with exit code 0 [2022-03-15 21:02:38,530 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2022-03-15 21:02:38,530 INFO L402 AbstractCegarLoop]: === Iteration 19 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr2INUSE_VIOLATION (and 3 more)] === [2022-03-15 21:02:38,532 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 21:02:38,532 INFO L85 PathProgramCache]: Analyzing trace with hash -23924378, now seen corresponding path program 10 times [2022-03-15 21:02:38,532 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 21:02:38,532 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [988936998] [2022-03-15 21:02:38,532 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 21:02:38,533 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 21:02:38,538 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 21:02:38,600 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 20 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-15 21:02:38,600 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 21:02:38,600 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [988936998] [2022-03-15 21:02:38,600 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [988936998] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-15 21:02:38,600 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1132438043] [2022-03-15 21:02:38,600 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-03-15 21:02:38,601 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 21:02:38,601 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 21:02:38,602 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-15 21:02:38,602 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2022-03-15 21:02:38,639 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-03-15 21:02:38,640 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-15 21:02:38,640 INFO L263 TraceCheckSpWp]: Trace formula consists of 143 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-15 21:02:38,641 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-15 21:02:38,738 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 22 trivial. 0 not checked. [2022-03-15 21:02:38,739 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-15 21:02:38,784 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 22 trivial. 0 not checked. [2022-03-15 21:02:38,784 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1132438043] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-15 21:02:38,784 INFO L191 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-03-15 21:02:38,785 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 3, 2] total 8 [2022-03-15 21:02:38,785 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [1491941425] [2022-03-15 21:02:38,785 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 21:02:38,787 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 21:02:40,241 INFO L252 McrAutomatonBuilder]: Finished intersection with 5644 states and 24698 transitions. [2022-03-15 21:02:40,242 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 21:03:36,146 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 4 new interpolants: [230654#(= (* x3 8) x4), 230652#(= (* 2 x3) x4), 230655#(= (* 16 x3) x4), 230653#(= (* x3 4) x4)] [2022-03-15 21:03:36,146 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2022-03-15 21:03:36,146 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 21:03:36,146 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2022-03-15 21:03:36,147 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=156, Unknown=0, NotChecked=0, Total=182 [2022-03-15 21:03:36,147 INFO L87 Difference]: Start difference. First operand 8605 states and 51613 transitions. Second operand has 11 states, 10 states have (on average 15.2) internal successors, (152), 10 states have internal predecessors, (152), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 21:03:36,718 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 21:03:36,718 INFO L93 Difference]: Finished difference Result 21240 states and 124395 transitions. [2022-03-15 21:03:36,719 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-03-15 21:03:36,719 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 15.2) internal successors, (152), 10 states have internal predecessors, (152), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 32 [2022-03-15 21:03:36,719 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 21:03:36,809 INFO L225 Difference]: With dead ends: 21240 [2022-03-15 21:03:36,809 INFO L226 Difference]: Without dead ends: 21065 [2022-03-15 21:03:36,810 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 5682 GetRequests, 4167 SyntacticMatches, 1503 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 117 ImplicationChecksByTransitivity, 2.4s TimeCoverageRelationStatistics Valid=26, Invalid=156, Unknown=0, NotChecked=0, Total=182 [2022-03-15 21:03:36,810 INFO L933 BasicCegarLoop]: 55 mSDtfsCounter, 44 mSDsluCounter, 1361 mSDsCounter, 0 mSdLazyCounter, 1289 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 44 SdHoareTripleChecker+Valid, 488 SdHoareTripleChecker+Invalid, 1289 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 1289 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2022-03-15 21:03:36,810 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [44 Valid, 488 Invalid, 1289 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 1289 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2022-03-15 21:03:36,836 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 21065 states. [2022-03-15 21:03:37,211 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 21065 to 16525. [2022-03-15 21:03:37,242 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 16525 states, 16524 states have (on average 6.154018397482449) internal successors, (101689), 16524 states have internal predecessors, (101689), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 21:03:37,326 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 16525 states to 16525 states and 101689 transitions. [2022-03-15 21:03:37,327 INFO L78 Accepts]: Start accepts. Automaton has 16525 states and 101689 transitions. Word has length 32 [2022-03-15 21:03:37,327 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 21:03:37,327 INFO L470 AbstractCegarLoop]: Abstraction has 16525 states and 101689 transitions. [2022-03-15 21:03:37,327 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 15.2) internal successors, (152), 10 states have internal predecessors, (152), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 21:03:37,327 INFO L276 IsEmpty]: Start isEmpty. Operand 16525 states and 101689 transitions. [2022-03-15 21:03:37,381 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2022-03-15 21:03:37,381 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 21:03:37,382 INFO L514 BasicCegarLoop]: trace histogram [5, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 21:03:37,398 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2022-03-15 21:03:37,582 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 21:03:37,582 INFO L402 AbstractCegarLoop]: === Iteration 20 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr2INUSE_VIOLATION (and 3 more)] === [2022-03-15 21:03:37,584 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 21:03:37,584 INFO L85 PathProgramCache]: Analyzing trace with hash -732451203, now seen corresponding path program 11 times [2022-03-15 21:03:37,584 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 21:03:37,584 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [46048413] [2022-03-15 21:03:37,585 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 21:03:37,585 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 21:03:37,589 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 21:03:37,643 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 0 proven. 25 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-15 21:03:37,643 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 21:03:37,643 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [46048413] [2022-03-15 21:03:37,643 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [46048413] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-15 21:03:37,643 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [541393546] [2022-03-15 21:03:37,643 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2022-03-15 21:03:37,644 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 21:03:37,644 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 21:03:37,645 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-15 21:03:37,645 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2022-03-15 21:03:37,680 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2022-03-15 21:03:37,680 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-15 21:03:37,681 INFO L263 TraceCheckSpWp]: Trace formula consists of 146 conjuncts, 11 conjunts are in the unsatisfiable core [2022-03-15 21:03:37,681 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-15 21:03:37,815 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 0 proven. 25 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-15 21:03:37,815 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-15 21:03:37,887 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 0 proven. 25 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-15 21:03:37,887 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [541393546] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-15 21:03:37,887 INFO L191 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-03-15 21:03:37,887 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 10, 6] total 12 [2022-03-15 21:03:37,887 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [1847182029] [2022-03-15 21:03:37,888 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 21:03:37,890 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 21:03:40,010 INFO L252 McrAutomatonBuilder]: Finished intersection with 6571 states and 28931 transitions. [2022-03-15 21:03:40,011 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 21:05:23,898 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 20 new interpolants: [285152#(or (<= (+ (* 2 x3) 1) n) (not (< x3 n))), 285160#(or (<= n x3) (<= (* x3 4) (* x4 4)) (<= n (* 2 x3))), 285155#(or (<= (* 2 x3) (* x4 4)) (not (< x3 n))), 285157#(or (<= n (* 2 x3)) (<= (+ (* x3 4) 1) n)), 285158#(or (not (< (* 2 x3) n)) (<= (* x3 4) x4) (not (< x3 n))), 285169#(or (<= (* 16 x3) (* 2 x4)) (<= n x3) (<= n (* x3 8))), 285156#(or (<= (* 2 x3) (* x4 8)) (not (< x3 n))), 285164#(or (<= n x3) (<= n (* x3 4)) (<= (* x3 8) (* 2 x4))), 285163#(or (<= (* x3 8) x4) (<= n x3) (<= n (* x3 4))), 285159#(or (not (< (* 2 x3) n)) (<= (* x3 4) (* 2 x4)) (not (< x3 n))), 285154#(or (<= (* 2 x3) (* 2 x4)) (not (< x3 n))), 285161#(or (not (< (* 2 x3) n)) (<= (* x3 4) (* x4 8)) (not (< x3 n))), 285153#(or (<= (* 2 x3) x4) (not (< x3 n))), 285162#(or (<= n (* x3 4)) (<= (+ (* x3 8) 1) n)), 285165#(or (<= n x3) (<= (* x3 8) (* x4 4)) (<= n (* x3 4))), 285170#(or (<= n x3) (<= n (* x3 8)) (<= (* 16 x3) (* x4 4))), 285167#(or (<= (+ (* 16 x3) 1) n) (<= n (* x3 8))), 285171#(or (<= (* 16 x3) (* x4 8)) (<= n x3) (<= n (* x3 8))), 285168#(or (<= n x3) (<= (* 16 x3) x4) (<= n (* x3 8))), 285166#(or (<= n x3) (<= n (* x3 4)) (<= (* x3 8) (* x4 8)))] [2022-03-15 21:05:23,899 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 29 states [2022-03-15 21:05:23,899 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 21:05:23,899 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2022-03-15 21:05:23,899 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=100, Invalid=1022, Unknown=0, NotChecked=0, Total=1122 [2022-03-15 21:05:23,900 INFO L87 Difference]: Start difference. First operand 16525 states and 101689 transitions. Second operand has 29 states, 28 states have (on average 14.392857142857142) internal successors, (403), 28 states have internal predecessors, (403), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 21:05:25,484 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 21:05:25,484 INFO L93 Difference]: Finished difference Result 25500 states and 149763 transitions. [2022-03-15 21:05:25,484 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2022-03-15 21:05:25,484 INFO L78 Accepts]: Start accepts. Automaton has has 29 states, 28 states have (on average 14.392857142857142) internal successors, (403), 28 states have internal predecessors, (403), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 33 [2022-03-15 21:05:25,484 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 21:05:25,576 INFO L225 Difference]: With dead ends: 25500 [2022-03-15 21:05:25,576 INFO L226 Difference]: Without dead ends: 21648 [2022-03-15 21:05:25,576 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 6624 GetRequests, 6136 SyntacticMatches, 443 SemanticMatches, 45 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5382 ImplicationChecksByTransitivity, 4.7s TimeCoverageRelationStatistics Valid=280, Invalid=1882, Unknown=0, NotChecked=0, Total=2162 [2022-03-15 21:05:25,578 INFO L933 BasicCegarLoop]: 61 mSDtfsCounter, 130 mSDsluCounter, 2719 mSDsCounter, 0 mSdLazyCounter, 2859 mSolverCounterSat, 30 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 130 SdHoareTripleChecker+Valid, 1150 SdHoareTripleChecker+Invalid, 2889 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 30 IncrementalHoareTripleChecker+Valid, 2859 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2022-03-15 21:05:25,578 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [130 Valid, 1150 Invalid, 2889 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [30 Valid, 2859 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2022-03-15 21:05:25,603 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 21648 states. [2022-03-15 21:05:25,852 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 21648 to 10486. [2022-03-15 21:05:25,870 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 10486 states, 10485 states have (on average 6.014401525989509) internal successors, (63061), 10485 states have internal predecessors, (63061), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 21:05:25,912 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10486 states to 10486 states and 63061 transitions. [2022-03-15 21:05:25,912 INFO L78 Accepts]: Start accepts. Automaton has 10486 states and 63061 transitions. Word has length 33 [2022-03-15 21:05:25,912 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 21:05:25,912 INFO L470 AbstractCegarLoop]: Abstraction has 10486 states and 63061 transitions. [2022-03-15 21:05:25,912 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 29 states, 28 states have (on average 14.392857142857142) internal successors, (403), 28 states have internal predecessors, (403), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 21:05:25,912 INFO L276 IsEmpty]: Start isEmpty. Operand 10486 states and 63061 transitions. [2022-03-15 21:05:25,936 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2022-03-15 21:05:25,936 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 21:05:25,936 INFO L514 BasicCegarLoop]: trace histogram [5, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 21:05:25,958 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Forceful destruction successful, exit code 0 [2022-03-15 21:05:26,138 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 21:05:26,139 INFO L402 AbstractCegarLoop]: === Iteration 21 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr2INUSE_VIOLATION (and 3 more)] === [2022-03-15 21:05:26,139 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 21:05:26,139 INFO L85 PathProgramCache]: Analyzing trace with hash 836066451, now seen corresponding path program 12 times [2022-03-15 21:05:26,140 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 21:05:26,140 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [192824992] [2022-03-15 21:05:26,140 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 21:05:26,140 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 21:05:26,144 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 21:05:26,214 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 0 proven. 25 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-15 21:05:26,214 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 21:05:26,214 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [192824992] [2022-03-15 21:05:26,214 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [192824992] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-15 21:05:26,214 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [116477130] [2022-03-15 21:05:26,214 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-03-15 21:05:26,214 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 21:05:26,214 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 21:05:26,215 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-15 21:05:26,216 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2022-03-15 21:05:26,247 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 3 check-sat command(s) [2022-03-15 21:05:26,248 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-15 21:05:26,248 INFO L263 TraceCheckSpWp]: Trace formula consists of 134 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-15 21:05:26,249 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-15 21:05:26,368 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 27 trivial. 0 not checked. [2022-03-15 21:05:26,368 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-15 21:05:26,420 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 27 trivial. 0 not checked. [2022-03-15 21:05:26,420 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [116477130] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-15 21:05:26,420 INFO L191 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-03-15 21:05:26,420 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 3, 2] total 13 [2022-03-15 21:05:26,420 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [948385943] [2022-03-15 21:05:26,420 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 21:05:26,422 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 21:05:28,002 INFO L252 McrAutomatonBuilder]: Finished intersection with 6571 states and 28931 transitions. [2022-03-15 21:05:28,002 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 21:07:22,639 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 20 new interpolants: [331894#(or (<= n x3) (<= (+ (* 2 x4) 1) n) (<= n (* 16 x3))), 331891#(or (<= n x3) (<= n (* x3 8)) (<= (+ (* x4 4) 1) n)), 331883#(or (<= n (* x3 4)) (<= (+ (* 2 x4) 1) n) (not (< x3 n))), 331895#(or (<= n x3) (<= (+ (* x4 4) 1) n) (<= n (* 16 x3))), 331885#(or (<= n x3) (<= (+ (* x4 4) 1) n)), 331878#(or (<= n x3) (<= (+ (* 2 x4) 1) n)), 331893#(or (<= (+ x4 1) n) (<= n x3) (<= n (* 16 x3))), 331881#(or (<= (+ x4 1) n) (<= n x3) (<= n (* x3 8))), 331887#(or (<= n x3) (<= (+ (* x4 8) 1) n)), 331877#(or (<= (+ x4 1) n) (<= n x3)), 331889#(or (<= n (* x3 4)) (<= (+ (* x4 4) 1) n) (not (< x3 n))), 331882#(or (<= n (* 2 x3)) (<= (+ (* 2 x4) 1) n) (not (< x3 n))), 331892#(or (<= n x3) (<= n (* x3 8)) (<= (+ (* x4 8) 1) n)), 331896#(or (<= (+ (* x4 8) 1) n) (not (< x3 n)) (<= n (* 16 x3))), 331884#(or (<= n x3) (<= n (* x3 8)) (<= (+ (* 2 x4) 1) n)), 331880#(or (<= (+ x4 1) n) (<= n x3) (<= n (* x3 4))), 331879#(or (<= (+ x4 1) n) (<= n (* 2 x3)) (not (< x3 n))), 331890#(or (<= n (* x3 4)) (<= (+ (* x4 8) 1) n) (not (< x3 n))), 331886#(or (<= n (* 2 x3)) (<= (+ (* x4 4) 1) n) (not (< x3 n))), 331888#(or (<= n (* 2 x3)) (<= (+ (* x4 8) 1) n) (not (< x3 n)))] [2022-03-15 21:07:22,639 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 32 states [2022-03-15 21:07:22,639 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 21:07:22,640 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2022-03-15 21:07:22,640 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=168, Invalid=1022, Unknown=0, NotChecked=0, Total=1190 [2022-03-15 21:07:22,640 INFO L87 Difference]: Start difference. First operand 10486 states and 63061 transitions. Second operand has 32 states, 31 states have (on average 14.161290322580646) internal successors, (439), 31 states have internal predecessors, (439), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 21:07:23,842 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 21:07:23,843 INFO L93 Difference]: Finished difference Result 30886 states and 183883 transitions. [2022-03-15 21:07:23,843 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2022-03-15 21:07:23,843 INFO L78 Accepts]: Start accepts. Automaton has has 32 states, 31 states have (on average 14.161290322580646) internal successors, (439), 31 states have internal predecessors, (439), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 33 [2022-03-15 21:07:23,843 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 21:07:23,931 INFO L225 Difference]: With dead ends: 30886 [2022-03-15 21:07:23,931 INFO L226 Difference]: Without dead ends: 20557 [2022-03-15 21:07:23,932 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 6635 GetRequests, 6087 SyntacticMatches, 491 SemanticMatches, 57 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7803 ImplicationChecksByTransitivity, 5.2s TimeCoverageRelationStatistics Valid=815, Invalid=2607, Unknown=0, NotChecked=0, Total=3422 [2022-03-15 21:07:23,933 INFO L933 BasicCegarLoop]: 44 mSDtfsCounter, 403 mSDsluCounter, 1048 mSDsCounter, 0 mSdLazyCounter, 1165 mSolverCounterSat, 41 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 403 SdHoareTripleChecker+Valid, 504 SdHoareTripleChecker+Invalid, 1206 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 41 IncrementalHoareTripleChecker+Valid, 1165 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2022-03-15 21:07:23,933 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [403 Valid, 504 Invalid, 1206 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [41 Valid, 1165 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2022-03-15 21:07:23,954 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 20557 states. [2022-03-15 21:07:24,205 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 20557 to 12178. [2022-03-15 21:07:24,225 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 12178 states, 12177 states have (on average 5.9946620678328) internal successors, (72997), 12177 states have internal predecessors, (72997), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 21:07:24,274 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 12178 states to 12178 states and 72997 transitions. [2022-03-15 21:07:24,275 INFO L78 Accepts]: Start accepts. Automaton has 12178 states and 72997 transitions. Word has length 33 [2022-03-15 21:07:24,275 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 21:07:24,275 INFO L470 AbstractCegarLoop]: Abstraction has 12178 states and 72997 transitions. [2022-03-15 21:07:24,275 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 32 states, 31 states have (on average 14.161290322580646) internal successors, (439), 31 states have internal predecessors, (439), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 21:07:24,275 INFO L276 IsEmpty]: Start isEmpty. Operand 12178 states and 72997 transitions. [2022-03-15 21:07:24,302 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2022-03-15 21:07:24,303 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 21:07:24,303 INFO L514 BasicCegarLoop]: trace histogram [5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 21:07:24,320 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Forceful destruction successful, exit code 0 [2022-03-15 21:07:24,503 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable20,19 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 21:07:24,503 INFO L402 AbstractCegarLoop]: === Iteration 22 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr2INUSE_VIOLATION (and 3 more)] === [2022-03-15 21:07:24,504 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 21:07:24,504 INFO L85 PathProgramCache]: Analyzing trace with hash 157460720, now seen corresponding path program 13 times [2022-03-15 21:07:24,504 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 21:07:24,504 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [125265864] [2022-03-15 21:07:24,505 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 21:07:24,505 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 21:07:24,510 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 21:07:24,597 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 0 proven. 30 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-15 21:07:24,597 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 21:07:24,597 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [125265864] [2022-03-15 21:07:24,597 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [125265864] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-15 21:07:24,597 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [15429638] [2022-03-15 21:07:24,597 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2022-03-15 21:07:24,597 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 21:07:24,597 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 21:07:24,598 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-15 21:07:24,599 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Waiting until timeout for monitored process [2022-03-15 21:07:24,635 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 21:07:24,636 INFO L263 TraceCheckSpWp]: Trace formula consists of 149 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-15 21:07:24,636 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-15 21:07:24,741 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 32 trivial. 0 not checked. [2022-03-15 21:07:24,742 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-15 21:07:24,789 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 32 trivial. 0 not checked. [2022-03-15 21:07:24,790 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [15429638] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-15 21:07:24,790 INFO L191 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-03-15 21:07:24,790 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 3, 2] total 9 [2022-03-15 21:07:24,790 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [1480051316] [2022-03-15 21:07:24,790 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 21:07:24,792 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 21:07:26,797 INFO L252 McrAutomatonBuilder]: Finished intersection with 7651 states and 33890 transitions. [2022-03-15 21:07:26,797 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider Received shutdown request... [2022-03-15 21:08:01,609 INFO L764 garLoopResultBuilder]: Registering result TIMEOUT for location ULTIMATE.startErr0ASSERT_VIOLATIONASSERT (6 of 7 remaining) [2022-03-15 21:08:01,615 WARN L340 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Timeout while monitored process is still running, waiting 1000 ms for graceful end [2022-03-15 21:08:01,615 WARN L340 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Timeout while monitored process is still running, waiting 1000 ms for graceful end [2022-03-15 21:08:01,624 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Forceful destruction successful, exit code 0 [2022-03-15 21:08:01,820 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable21,20 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 21:08:01,820 WARN L594 AbstractCegarLoop]: Verification canceled: while BasicCegarLoop was analyzing trace of length 35 with TraceHistMax 5,while PolyPacSimplificationTermWalker was simplifying a ATOM-1 term,while PolyPacSimplificationTermWalker was simplifying 3 xjuncts wrt. a ATOM-1 context. [2022-03-15 21:08:01,821 INFO L764 garLoopResultBuilder]: Registering result TIMEOUT for location ULTIMATE.startErr0INUSE_VIOLATION (5 of 7 remaining) [2022-03-15 21:08:01,821 INFO L764 garLoopResultBuilder]: Registering result TIMEOUT for location ULTIMATE.startErr1INUSE_VIOLATION (4 of 7 remaining) [2022-03-15 21:08:01,822 INFO L764 garLoopResultBuilder]: Registering result TIMEOUT for location ULTIMATE.startErr2INUSE_VIOLATION (3 of 7 remaining) [2022-03-15 21:08:01,822 INFO L764 garLoopResultBuilder]: Registering result TIMEOUT for location ULTIMATE.startErr3INUSE_VIOLATION (2 of 7 remaining) [2022-03-15 21:08:01,822 INFO L764 garLoopResultBuilder]: Registering result TIMEOUT for location ULTIMATE.startErr4INUSE_VIOLATION (1 of 7 remaining) [2022-03-15 21:08:01,822 INFO L764 garLoopResultBuilder]: Registering result TIMEOUT for location ULTIMATE.startErr5INUSE_VIOLATION (0 of 7 remaining) [2022-03-15 21:08:01,824 INFO L732 BasicCegarLoop]: Path program histogram: [13, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 21:08:01,825 INFO L230 ceAbstractionStarter]: Analysis of concurrent program completed with 1 thread instances [2022-03-15 21:08:01,825 INFO L180 ceAbstractionStarter]: Computing trace abstraction results [2022-03-15 21:08:01,827 INFO L202 PluginConnector]: Adding new model exp3x3-opt.wvr.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 15.03 09:08:01 BasicIcfg [2022-03-15 21:08:01,827 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2022-03-15 21:08:01,827 INFO L158 Benchmark]: Toolchain (without parser) took 692274.91ms. Allocated memory was 208.7MB in the beginning and 1.6GB in the end (delta: 1.4GB). Free memory was 172.6MB in the beginning and 1.1GB in the end (delta: -881.6MB). Peak memory consumption was 538.9MB. Max. memory is 8.0GB. [2022-03-15 21:08:01,827 INFO L158 Benchmark]: Boogie PL CUP Parser took 0.09ms. Allocated memory is still 208.7MB. Free memory is still 173.9MB. There was no memory consumed. Max. memory is 8.0GB. [2022-03-15 21:08:01,827 INFO L158 Benchmark]: Boogie Procedure Inliner took 28.13ms. Allocated memory is still 208.7MB. Free memory was 172.6MB in the beginning and 171.2MB in the end (delta: 1.5MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. [2022-03-15 21:08:01,827 INFO L158 Benchmark]: Boogie Preprocessor took 24.15ms. Allocated memory is still 208.7MB. Free memory was 171.0MB in the beginning and 170.1MB in the end (delta: 945.8kB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. [2022-03-15 21:08:01,827 INFO L158 Benchmark]: RCFGBuilder took 188.18ms. Allocated memory is still 208.7MB. Free memory was 170.1MB in the beginning and 159.5MB in the end (delta: 10.6MB). Peak memory consumption was 10.5MB. Max. memory is 8.0GB. [2022-03-15 21:08:01,828 INFO L158 Benchmark]: TraceAbstraction took 692027.81ms. Allocated memory was 208.7MB in the beginning and 1.6GB in the end (delta: 1.4GB). Free memory was 159.0MB in the beginning and 1.1GB in the end (delta: -895.2MB). Peak memory consumption was 525.2MB. Max. memory is 8.0GB. [2022-03-15 21:08:01,828 INFO L339 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * Boogie PL CUP Parser took 0.09ms. Allocated memory is still 208.7MB. Free memory is still 173.9MB. There was no memory consumed. Max. memory is 8.0GB. * Boogie Procedure Inliner took 28.13ms. Allocated memory is still 208.7MB. Free memory was 172.6MB in the beginning and 171.2MB in the end (delta: 1.5MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. * Boogie Preprocessor took 24.15ms. Allocated memory is still 208.7MB. Free memory was 171.0MB in the beginning and 170.1MB in the end (delta: 945.8kB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. * RCFGBuilder took 188.18ms. Allocated memory is still 208.7MB. Free memory was 170.1MB in the beginning and 159.5MB in the end (delta: 10.6MB). Peak memory consumption was 10.5MB. Max. memory is 8.0GB. * TraceAbstraction took 692027.81ms. Allocated memory was 208.7MB in the beginning and 1.6GB in the end (delta: 1.4GB). Free memory was 159.0MB in the beginning and 1.1GB in the end (delta: -895.2MB). Peak memory consumption was 525.2MB. Max. memory is 8.0GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: PetriNetLargeBlockEncoding benchmarks Lipton Reduction Statistics: ReductionTime: 0.2s, 48 PlacesBefore, 46 PlacesAfterwards, 35 TransitionsBefore, 33 TransitionsAfterwards, 240 CoEnabledTransitionPairs, 2 FixpointIterations, 3 TrivialSequentialCompositions, 0 ConcurrentSequentialCompositions, 0 TrivialYvCompositions, 0 ConcurrentYvCompositions, 0 ChoiceCompositions, 3 TotalNumberOfCompositions, 270 MoverChecksTotal, Independence Relation Statistics: CachedIndependenceRelation.Independence Queries: [ total: 270, positive: 270, positive conditional: 0, positive unconditional: 270, negative: 0, negative conditional: 0, negative unconditional: 0, unknown: 0, unknown conditional: 0, unknown unconditional: 0] , CachedIndependenceRelation.Statistics on underlying relation: SyntacticIndependenceRelation.Independence Queries: [ total: 75, positive: 75, positive conditional: 0, positive unconditional: 75, negative: 0, negative conditional: 0, negative unconditional: 0, unknown: 0, unknown conditional: 0, unknown unconditional: 0] , Cache Queries: [ total: 270, positive: 195, positive conditional: 0, positive unconditional: 195, negative: 0, negative conditional: 0, negative unconditional: 0, unknown: 75, unknown conditional: 0, unknown unconditional: 75] , Statistics on independence cache: Total cache size (in pairs): 75, Positive cache size: 75, Positive conditional cache size: 0, Positive unconditional cache size: 75, Negative cache size: 0, Negative conditional cache size: 0, Negative unconditional cache size: 0 - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - TimeoutResultAtElement [Line: 100]: Timeout (TraceAbstraction) Unable to prove that assertion always holds Cancelled while BasicCegarLoop was analyzing trace of length 35 with TraceHistMax 5,while PolyPacSimplificationTermWalker was simplifying a ATOM-1 term,while PolyPacSimplificationTermWalker was simplifying 3 xjuncts wrt. a ATOM-1 context. - TimeoutResultAtElement [Line: 89]: Timeout (TraceAbstraction) Unable to prove that petrification did provide enough thread instances (tool internal message, not intended for end users) Cancelled while BasicCegarLoop was analyzing trace of length 35 with TraceHistMax 5,while PolyPacSimplificationTermWalker was simplifying a ATOM-1 term,while PolyPacSimplificationTermWalker was simplifying 3 xjuncts wrt. a ATOM-1 context. - TimeoutResultAtElement [Line: 91]: Timeout (TraceAbstraction) Unable to prove that petrification did provide enough thread instances (tool internal message, not intended for end users) Cancelled while BasicCegarLoop was analyzing trace of length 35 with TraceHistMax 5,while PolyPacSimplificationTermWalker was simplifying a ATOM-1 term,while PolyPacSimplificationTermWalker was simplifying 3 xjuncts wrt. a ATOM-1 context. - TimeoutResultAtElement [Line: 87]: Timeout (TraceAbstraction) Unable to prove that petrification did provide enough thread instances (tool internal message, not intended for end users) Cancelled while BasicCegarLoop was analyzing trace of length 35 with TraceHistMax 5,while PolyPacSimplificationTermWalker was simplifying a ATOM-1 term,while PolyPacSimplificationTermWalker was simplifying 3 xjuncts wrt. a ATOM-1 context. - TimeoutResultAtElement [Line: 88]: Timeout (TraceAbstraction) Unable to prove that petrification did provide enough thread instances (tool internal message, not intended for end users) Cancelled while BasicCegarLoop was analyzing trace of length 35 with TraceHistMax 5,while PolyPacSimplificationTermWalker was simplifying a ATOM-1 term,while PolyPacSimplificationTermWalker was simplifying 3 xjuncts wrt. a ATOM-1 context. - TimeoutResultAtElement [Line: 90]: Timeout (TraceAbstraction) Unable to prove that petrification did provide enough thread instances (tool internal message, not intended for end users) Cancelled while BasicCegarLoop was analyzing trace of length 35 with TraceHistMax 5,while PolyPacSimplificationTermWalker was simplifying a ATOM-1 term,while PolyPacSimplificationTermWalker was simplifying 3 xjuncts wrt. a ATOM-1 context. - TimeoutResultAtElement [Line: 87]: Timeout (TraceAbstraction) Unable to prove that petrification did provide enough thread instances (tool internal message, not intended for end users) Cancelled while BasicCegarLoop was analyzing trace of length 35 with TraceHistMax 5,while PolyPacSimplificationTermWalker was simplifying a ATOM-1 term,while PolyPacSimplificationTermWalker was simplifying 3 xjuncts wrt. a ATOM-1 context. - StatisticsResult: Ultimate Automizer benchmark data with 1 thread instances CFG has 13 procedures, 48 locations, 7 error locations. Started 1 CEGAR loops. OverallTime: 692.0s, OverallIterations: 22, TraceHistogramMax: 5, PathProgramHistogramMax: 13, EmptinessCheckTime: 0.3s, AutomataDifference: 8.4s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.2s, PartialOrderReductionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 1210 SdHoareTripleChecker+Valid, 4.4s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 1210 mSDsluCounter, 4555 SdHoareTripleChecker+Invalid, 3.5s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 10456 mSDsCounter, 178 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 11390 IncrementalHoareTripleChecker+Invalid, 11568 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 178 mSolverCounterUnsat, 541 mSDtfsCounter, 11390 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 52391 GetRequests, 44768 SyntacticMatches, 7319 SemanticMatches, 304 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 22720 ImplicationChecksByTransitivity, 25.1s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=16525occurred in iteration=19, InterpolantAutomatonStates: 213, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 3.2s AutomataMinimizationTime, 21 MinimizatonAttempts, 50052 StatesRemovedByMinimization, 14 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.3s SatisfiabilityAnalysisTime, 3.2s InterpolantComputationTime, 1063 NumberOfCodeBlocks, 1056 NumberOfCodeBlocksAsserted, 52 NumberOfCheckSat, 1506 ConstructedInterpolants, 0 QuantifiedInterpolants, 8167 SizeOfPredicates, 12 NumberOfNonLiveVariables, 2325 ConjunctsInSsa, 104 ConjunctsInUnsatCore, 57 InterpolantComputations, 3 PerfectInterpolantSequences, 339/663 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Completed graceful shutdown [2022-03-15 21:08:01,838 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Ended with exit code 0