/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/parallel/misc-1.wvr.bpl -------------------------------------------------------------------------------- This is Ultimate 0.2.2-wip.dk.mcr-reduction-c7b2d19 [2022-03-15 21:15:34,907 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-03-15 21:15:34,909 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-03-15 21:15:34,954 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-03-15 21:15:34,971 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-03-15 21:15:34,972 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-03-15 21:15:34,973 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-03-15 21:15:34,974 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-03-15 21:15:34,975 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-03-15 21:15:34,975 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-03-15 21:15:34,976 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-03-15 21:15:34,977 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-03-15 21:15:34,977 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-03-15 21:15:34,977 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-03-15 21:15:34,978 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-03-15 21:15:34,979 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-03-15 21:15:34,979 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-03-15 21:15:34,980 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-03-15 21:15:34,981 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-03-15 21:15:34,982 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-03-15 21:15:34,982 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-03-15 21:15:34,983 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-03-15 21:15:34,984 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-03-15 21:15:34,984 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-03-15 21:15:34,986 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-03-15 21:15:34,986 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-03-15 21:15:34,986 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-03-15 21:15:34,987 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-03-15 21:15:34,987 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-03-15 21:15:34,988 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-03-15 21:15:34,988 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-03-15 21:15:34,988 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-03-15 21:15:34,989 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-03-15 21:15:34,989 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-03-15 21:15:34,990 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-03-15 21:15:34,990 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-03-15 21:15:34,991 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-03-15 21:15:34,991 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-03-15 21:15:34,991 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-03-15 21:15:34,991 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-03-15 21:15:34,992 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-03-15 21:15:34,995 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 21:15:35,018 INFO L113 SettingsManager]: Loading preferences was successful [2022-03-15 21:15:35,018 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-03-15 21:15:35,019 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-03-15 21:15:35,019 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-03-15 21:15:35,019 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-03-15 21:15:35,020 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-03-15 21:15:35,020 INFO L138 SettingsManager]: * Use SBE=true [2022-03-15 21:15:35,020 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-03-15 21:15:35,020 INFO L138 SettingsManager]: * sizeof long=4 [2022-03-15 21:15:35,020 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-03-15 21:15:35,020 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-03-15 21:15:35,021 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-03-15 21:15:35,021 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-03-15 21:15:35,021 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-03-15 21:15:35,021 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-03-15 21:15:35,021 INFO L138 SettingsManager]: * sizeof long double=12 [2022-03-15 21:15:35,021 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-03-15 21:15:35,021 INFO L138 SettingsManager]: * Use constant arrays=true [2022-03-15 21:15:35,021 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-03-15 21:15:35,021 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-03-15 21:15:35,021 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-03-15 21:15:35,021 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-03-15 21:15:35,022 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-03-15 21:15:35,022 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-15 21:15:35,022 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-03-15 21:15:35,022 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_NestedInterpolation [2022-03-15 21:15:35,022 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-03-15 21:15:35,022 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-03-15 21:15:35,022 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2022-03-15 21:15:35,022 INFO L138 SettingsManager]: * Override the interpolant automaton setting of the refinement strategy=true [2022-03-15 21:15:35,027 INFO L138 SettingsManager]: * Large block encoding in concurrent analysis=VARIABLE_BASED_MOVER_CHECK [2022-03-15 21:15:35,027 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-03-15 21:15:35,027 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 21:15:35,206 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-03-15 21:15:35,225 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-03-15 21:15:35,226 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-03-15 21:15:35,227 INFO L271 PluginConnector]: Initializing Boogie PL CUP Parser... [2022-03-15 21:15:35,228 INFO L275 PluginConnector]: Boogie PL CUP Parser initialized [2022-03-15 21:15:35,228 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/concurrent/bpl/weaver-benchmarks/generated/parallel/misc-1.wvr.bpl [2022-03-15 21:15:35,228 INFO L110 BoogieParser]: Parsing: '/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/concurrent/bpl/weaver-benchmarks/generated/parallel/misc-1.wvr.bpl' [2022-03-15 21:15:35,250 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-03-15 21:15:35,251 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-03-15 21:15:35,252 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2022-03-15 21:15:35,252 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2022-03-15 21:15:35,252 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2022-03-15 21:15:35,260 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "misc-1.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.03 09:15:35" (1/1) ... [2022-03-15 21:15:35,264 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "misc-1.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.03 09:15:35" (1/1) ... [2022-03-15 21:15:35,268 INFO L137 Inliner]: procedures = 3, calls = 2, calls flagged for inlining = 0, calls inlined = 0, statements flattened = 0 [2022-03-15 21:15:35,269 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2022-03-15 21:15:35,272 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-03-15 21:15:35,272 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-03-15 21:15:35,272 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-03-15 21:15:35,277 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "misc-1.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.03 09:15:35" (1/1) ... [2022-03-15 21:15:35,277 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "misc-1.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.03 09:15:35" (1/1) ... [2022-03-15 21:15:35,278 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "misc-1.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.03 09:15:35" (1/1) ... [2022-03-15 21:15:35,278 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "misc-1.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.03 09:15:35" (1/1) ... [2022-03-15 21:15:35,281 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "misc-1.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.03 09:15:35" (1/1) ... [2022-03-15 21:15:35,284 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "misc-1.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.03 09:15:35" (1/1) ... [2022-03-15 21:15:35,284 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "misc-1.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.03 09:15:35" (1/1) ... [2022-03-15 21:15:35,287 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-03-15 21:15:35,289 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-03-15 21:15:35,290 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-03-15 21:15:35,290 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-03-15 21:15:35,291 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "misc-1.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.03 09:15:35" (1/1) ... [2022-03-15 21:15:35,296 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-15 21:15:35,305 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 21:15:35,314 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 21:15:35,322 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 21:15:35,347 INFO L124 BoogieDeclarations]: Specification and implementation of procedure thread1 given in one single declaration [2022-03-15 21:15:35,348 INFO L130 BoogieDeclarations]: Found specification of procedure thread1 [2022-03-15 21:15:35,348 INFO L138 BoogieDeclarations]: Found implementation of procedure thread1 [2022-03-15 21:15:35,348 INFO L124 BoogieDeclarations]: Specification and implementation of procedure thread2 given in one single declaration [2022-03-15 21:15:35,348 INFO L130 BoogieDeclarations]: Found specification of procedure thread2 [2022-03-15 21:15:35,348 INFO L138 BoogieDeclarations]: Found implementation of procedure thread2 [2022-03-15 21:15:35,348 INFO L124 BoogieDeclarations]: Specification and implementation of procedure ULTIMATE.start given in one single declaration [2022-03-15 21:15:35,348 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-03-15 21:15:35,348 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-03-15 21:15:35,349 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 21:15:35,380 INFO L234 CfgBuilder]: Building ICFG [2022-03-15 21:15:35,381 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-03-15 21:15:35,462 INFO L275 CfgBuilder]: Performing block encoding [2022-03-15 21:15:35,466 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-03-15 21:15:35,466 INFO L299 CfgBuilder]: Removed 0 assume(true) statements. [2022-03-15 21:15:35,468 INFO L202 PluginConnector]: Adding new model misc-1.wvr.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 15.03 09:15:35 BoogieIcfgContainer [2022-03-15 21:15:35,468 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-03-15 21:15:35,469 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-03-15 21:15:35,469 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-03-15 21:15:35,486 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-03-15 21:15:35,487 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "misc-1.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.03 09:15:35" (1/2) ... [2022-03-15 21:15:35,487 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@78a5736d and model type misc-1.wvr.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 15.03 09:15:35, skipping insertion in model container [2022-03-15 21:15:35,487 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "misc-1.wvr.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 15.03 09:15:35" (2/2) ... [2022-03-15 21:15:35,488 INFO L111 eAbstractionObserver]: Analyzing ICFG misc-1.wvr.bpl [2022-03-15 21:15:35,491 WARN L150 ceAbstractionStarter]: Switching off computation of Hoare annotation because input is a concurrent program [2022-03-15 21:15:35,491 INFO L205 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:Craig_NestedInterpolation Determinization: PREDICATE_ABSTRACTION [2022-03-15 21:15:35,491 INFO L164 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-03-15 21:15:35,492 INFO L534 ceAbstractionStarter]: Constructing petrified ICFG for 1 thread instances. [2022-03-15 21:15:35,540 INFO L148 ThreadInstanceAdder]: Constructed 2 joinOtherThreadTransitions. [2022-03-15 21:15:35,584 INFO L338 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-03-15 21:15:35,590 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 21:15:35,590 INFO L340 AbstractCegarLoop]: Starting to check reachability of 3 error locations. [2022-03-15 21:15:35,601 INFO L126 etLargeBlockEncoding]: Petri net LBE is using variable-based independence relation. [2022-03-15 21:15:35,609 INFO L133 etLargeBlockEncoding]: Starting large block encoding on Petri net that has 34 places, 31 transitions, 78 flow [2022-03-15 21:15:35,618 INFO L110 LiptonReduction]: Starting Lipton reduction on Petri net that has 34 places, 31 transitions, 78 flow [2022-03-15 21:15:35,620 INFO L74 FinitePrefix]: Start finitePrefix. Operand has 34 places, 31 transitions, 78 flow [2022-03-15 21:15:35,650 INFO L129 PetriNetUnfolder]: 4/29 cut-off events. [2022-03-15 21:15:35,650 INFO L130 PetriNetUnfolder]: For 2/2 co-relation queries the response was YES. [2022-03-15 21:15:35,658 INFO L84 FinitePrefix]: Finished finitePrefix Result has 38 conditions, 29 events. 4/29 cut-off events. For 2/2 co-relation queries the response was YES. Maximal size of possible extension queue 6. Compared 64 event pairs, 0 based on Foata normal form. 0/24 useless extension candidates. Maximal degree in co-relation 23. Up to 2 conditions per place. [2022-03-15 21:15:35,659 INFO L116 LiptonReduction]: Number of co-enabled transitions 240 [2022-03-15 21:15:36,151 INFO L131 LiptonReduction]: Checked pairs total: 190 [2022-03-15 21:15:36,151 INFO L133 LiptonReduction]: Total number of compositions: 22 [2022-03-15 21:15:36,165 INFO L111 iNet2FiniteAutomaton]: Start petriNet2FiniteAutomaton. Operand has 18 places, 13 transitions, 42 flow [2022-03-15 21:15:36,173 INFO L133 iNet2FiniteAutomaton]: Finished petriNet2FiniteAutomaton. Result has 12 states, 11 states have (on average 1.8181818181818181) internal successors, (20), 11 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 21:15:36,174 INFO L276 IsEmpty]: Start isEmpty. Operand has 12 states, 11 states have (on average 1.8181818181818181) internal successors, (20), 11 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 21:15:36,178 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2022-03-15 21:15:36,178 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 21:15:36,178 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 21:15:36,178 INFO L402 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION] === [2022-03-15 21:15:36,181 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 21:15:36,181 INFO L85 PathProgramCache]: Analyzing trace with hash -1287215609, now seen corresponding path program 1 times [2022-03-15 21:15:36,193 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 21:15:36,195 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [951885699] [2022-03-15 21:15:36,195 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 21:15:36,195 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 21:15:36,254 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 21:15:36,411 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 21:15:36,412 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 21:15:36,412 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [951885699] [2022-03-15 21:15:36,412 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [951885699] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-15 21:15:36,412 INFO L191 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-15 21:15:36,413 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-03-15 21:15:36,414 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [1510827589] [2022-03-15 21:15:36,415 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 21:15:36,420 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 21:15:36,432 INFO L252 McrAutomatonBuilder]: Finished intersection with 12 states and 14 transitions. [2022-03-15 21:15:36,433 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 21:15:36,582 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 2 new interpolants: [67#(and (<= (+ bag1 sum1) (* 2 bag2)) (= bag2 sum2) (< (+ bag2 sum2) (+ bag1 sum1 1))), 66#(and (<= (+ bag1 sum1) sum2) (< sum2 (+ bag1 sum1 1)))] [2022-03-15 21:15:36,583 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-03-15 21:15:36,583 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 21:15:36,600 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-03-15 21:15:36,600 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2022-03-15 21:15:36,601 INFO L87 Difference]: Start difference. First operand has 12 states, 11 states have (on average 1.8181818181818181) internal successors, (20), 11 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) Second operand has 7 states, 6 states have (on average 2.1666666666666665) internal successors, (13), 6 states have internal predecessors, (13), 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:15:36,707 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 21:15:36,708 INFO L93 Difference]: Finished difference Result 28 states and 59 transitions. [2022-03-15 21:15:36,709 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-03-15 21:15:36,709 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 2.1666666666666665) internal successors, (13), 6 states have internal predecessors, (13), 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 8 [2022-03-15 21:15:36,710 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 21:15:36,716 INFO L225 Difference]: With dead ends: 28 [2022-03-15 21:15:36,716 INFO L226 Difference]: Without dead ends: 25 [2022-03-15 21:15:36,717 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 9 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=30, Invalid=60, Unknown=0, NotChecked=0, Total=90 [2022-03-15 21:15:36,719 INFO L933 BasicCegarLoop]: 1 mSDtfsCounter, 16 mSDsluCounter, 12 mSDsCounter, 0 mSdLazyCounter, 47 mSolverCounterSat, 18 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 1 SdHoareTripleChecker+Invalid, 65 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 18 IncrementalHoareTripleChecker+Valid, 47 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-15 21:15:36,721 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [16 Valid, 1 Invalid, 65 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [18 Valid, 47 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-15 21:15:36,732 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states. [2022-03-15 21:15:36,751 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 18. [2022-03-15 21:15:36,752 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 18 states, 17 states have (on average 1.8823529411764706) internal successors, (32), 17 states have internal predecessors, (32), 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:15:36,752 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 18 states to 18 states and 32 transitions. [2022-03-15 21:15:36,753 INFO L78 Accepts]: Start accepts. Automaton has 18 states and 32 transitions. Word has length 8 [2022-03-15 21:15:36,753 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 21:15:36,754 INFO L470 AbstractCegarLoop]: Abstraction has 18 states and 32 transitions. [2022-03-15 21:15:36,754 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 2.1666666666666665) internal successors, (13), 6 states have internal predecessors, (13), 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:15:36,754 INFO L276 IsEmpty]: Start isEmpty. Operand 18 states and 32 transitions. [2022-03-15 21:15:36,754 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2022-03-15 21:15:36,754 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 21:15:36,754 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 21:15:36,755 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-03-15 21:15:36,755 INFO L402 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION] === [2022-03-15 21:15:36,755 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 21:15:36,755 INFO L85 PathProgramCache]: Analyzing trace with hash -1248872468, now seen corresponding path program 1 times [2022-03-15 21:15:36,757 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 21:15:36,757 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1039468423] [2022-03-15 21:15:36,757 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 21:15:36,757 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 21:15:36,765 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 21:15:36,790 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 21:15:36,790 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 21:15:36,793 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1039468423] [2022-03-15 21:15:36,793 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1039468423] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-15 21:15:36,793 INFO L191 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-15 21:15:36,793 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-03-15 21:15:36,793 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [304121085] [2022-03-15 21:15:36,793 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 21:15:36,794 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 21:15:36,798 INFO L252 McrAutomatonBuilder]: Finished intersection with 15 states and 19 transitions. [2022-03-15 21:15:36,798 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 21:15:36,871 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 2 new interpolants: [143#(or (<= N j) (< i N)), 142#(< i N)] [2022-03-15 21:15:36,872 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-03-15 21:15:36,872 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 21:15:36,873 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-03-15 21:15:36,873 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2022-03-15 21:15:36,873 INFO L87 Difference]: Start difference. First operand 18 states and 32 transitions. Second operand has 6 states, 6 states have (on average 2.5) internal successors, (15), 5 states have internal predecessors, (15), 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:15:36,948 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 21:15:36,949 INFO L93 Difference]: Finished difference Result 20 states and 33 transitions. [2022-03-15 21:15:36,949 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-03-15 21:15:36,949 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.5) internal successors, (15), 5 states have internal predecessors, (15), 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 9 [2022-03-15 21:15:36,949 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 21:15:36,950 INFO L225 Difference]: With dead ends: 20 [2022-03-15 21:15:36,950 INFO L226 Difference]: Without dead ends: 16 [2022-03-15 21:15:36,950 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 4 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=22, Invalid=34, Unknown=0, NotChecked=0, Total=56 [2022-03-15 21:15:36,951 INFO L933 BasicCegarLoop]: 1 mSDtfsCounter, 11 mSDsluCounter, 16 mSDsCounter, 0 mSdLazyCounter, 58 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 1 SdHoareTripleChecker+Invalid, 63 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 58 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-15 21:15:36,951 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 1 Invalid, 63 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 58 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-15 21:15:36,953 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 16 states. [2022-03-15 21:15:36,954 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 16 to 16. [2022-03-15 21:15:36,954 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 16 states, 15 states have (on average 1.8666666666666667) internal successors, (28), 15 states have internal predecessors, (28), 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:15:36,955 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 16 states to 16 states and 28 transitions. [2022-03-15 21:15:36,955 INFO L78 Accepts]: Start accepts. Automaton has 16 states and 28 transitions. Word has length 9 [2022-03-15 21:15:36,955 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 21:15:36,955 INFO L470 AbstractCegarLoop]: Abstraction has 16 states and 28 transitions. [2022-03-15 21:15:36,955 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.5) internal successors, (15), 5 states have internal predecessors, (15), 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:15:36,955 INFO L276 IsEmpty]: Start isEmpty. Operand 16 states and 28 transitions. [2022-03-15 21:15:36,955 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2022-03-15 21:15:36,955 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 21:15:36,956 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 21:15:36,956 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-03-15 21:15:36,956 INFO L402 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION] === [2022-03-15 21:15:36,956 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 21:15:36,956 INFO L85 PathProgramCache]: Analyzing trace with hash 294957908, now seen corresponding path program 1 times [2022-03-15 21:15:36,957 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 21:15:36,957 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1995701274] [2022-03-15 21:15:36,957 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 21:15:36,957 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 21:15:36,964 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 21:15:37,012 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 21:15:37,013 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 21:15:37,013 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1995701274] [2022-03-15 21:15:37,013 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1995701274] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-15 21:15:37,013 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [704301750] [2022-03-15 21:15:37,013 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 21:15:37,013 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 21:15:37,014 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 21:15:37,015 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 21:15:37,016 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 21:15:37,040 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 21:15:37,041 INFO L263 TraceCheckSpWp]: Trace formula consists of 34 conjuncts, 4 conjunts are in the unsatisfiable core [2022-03-15 21:15:37,043 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-15 21:15:37,121 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 54 treesize of output 46 [2022-03-15 21:15:37,174 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 21:15:37,174 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-15 21:15:37,217 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 19 [2022-03-15 21:15:37,230 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 21:15:37,231 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [704301750] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-15 21:15:37,231 INFO L191 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-03-15 21:15:37,231 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [3, 3, 3] total 6 [2022-03-15 21:15:37,231 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [1611809402] [2022-03-15 21:15:37,231 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 21:15:37,232 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 21:15:37,233 INFO L252 McrAutomatonBuilder]: Finished intersection with 15 states and 19 transitions. [2022-03-15 21:15:37,233 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 21:15:37,459 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 4 new interpolants: [255#(< i N), 257#(or (<= N i) (< (+ i 1) N)), 256#(and (or (= (+ bag2 (* (- 1) j)) 0) (< i N)) (or (< j N) (< i N))), 258#(and (or (<= N i) (< (+ i 1) N) (< j N)) (or (<= N i) (< (+ i 1) N) (= (+ bag2 (* (- 1) j)) 0)))] [2022-03-15 21:15:37,459 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-03-15 21:15:37,459 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 21:15:37,460 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-03-15 21:15:37,460 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=82, Unknown=0, NotChecked=0, Total=110 [2022-03-15 21:15:37,460 INFO L87 Difference]: Start difference. First operand 16 states and 28 transitions. Second operand has 8 states, 8 states have (on average 2.25) internal successors, (18), 7 states have internal predecessors, (18), 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:15:37,521 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 21:15:37,521 INFO L93 Difference]: Finished difference Result 19 states and 34 transitions. [2022-03-15 21:15:37,521 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-03-15 21:15:37,521 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 2.25) internal successors, (18), 7 states have internal predecessors, (18), 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 9 [2022-03-15 21:15:37,521 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 21:15:37,522 INFO L225 Difference]: With dead ends: 19 [2022-03-15 21:15:37,522 INFO L226 Difference]: Without dead ends: 19 [2022-03-15 21:15:37,522 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 25 GetRequests, 15 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=35, Invalid=97, Unknown=0, NotChecked=0, Total=132 [2022-03-15 21:15:37,524 INFO L933 BasicCegarLoop]: 1 mSDtfsCounter, 15 mSDsluCounter, 25 mSDsCounter, 0 mSdLazyCounter, 90 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 1 SdHoareTripleChecker+Invalid, 96 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 90 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-15 21:15:37,525 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [15 Valid, 1 Invalid, 96 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 90 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-15 21:15:37,527 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 19 states. [2022-03-15 21:15:37,529 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 19 to 19. [2022-03-15 21:15:37,529 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 19 states, 18 states have (on average 1.8888888888888888) internal successors, (34), 18 states have internal predecessors, (34), 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:15:37,530 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 19 states to 19 states and 34 transitions. [2022-03-15 21:15:37,530 INFO L78 Accepts]: Start accepts. Automaton has 19 states and 34 transitions. Word has length 9 [2022-03-15 21:15:37,530 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 21:15:37,531 INFO L470 AbstractCegarLoop]: Abstraction has 19 states and 34 transitions. [2022-03-15 21:15:37,531 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 2.25) internal successors, (18), 7 states have internal predecessors, (18), 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:15:37,531 INFO L276 IsEmpty]: Start isEmpty. Operand 19 states and 34 transitions. [2022-03-15 21:15:37,531 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2022-03-15 21:15:37,531 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 21:15:37,532 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 21:15:37,548 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2022-03-15 21:15:37,748 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 21:15:37,748 INFO L402 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION] === [2022-03-15 21:15:37,748 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 21:15:37,748 INFO L85 PathProgramCache]: Analyzing trace with hash 553866303, now seen corresponding path program 1 times [2022-03-15 21:15:37,751 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 21:15:37,751 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [520000107] [2022-03-15 21:15:37,751 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 21:15:37,751 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 21:15:37,773 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 21:15:37,925 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 21:15:37,925 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 21:15:37,927 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [520000107] [2022-03-15 21:15:37,927 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [520000107] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-15 21:15:37,928 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1328940981] [2022-03-15 21:15:37,928 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 21:15:37,928 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 21:15:37,928 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 21:15:37,929 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 21:15:37,930 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 21:15:37,953 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 21:15:37,954 WARN L261 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 19 conjunts are in the unsatisfiable core [2022-03-15 21:15:37,955 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-15 21:15:38,067 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 35 treesize of output 25 [2022-03-15 21:15:38,093 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 21:15:38,093 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-15 21:15:38,217 INFO L353 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2022-03-15 21:15:38,217 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 84 treesize of output 80 [2022-03-15 21:15:38,328 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 21:15:38,328 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1328940981] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-15 21:15:38,328 INFO L191 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-03-15 21:15:38,328 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5, 5] total 11 [2022-03-15 21:15:38,329 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [251906441] [2022-03-15 21:15:38,329 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 21:15:38,330 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 21:15:38,331 INFO L252 McrAutomatonBuilder]: Finished intersection with 19 states and 26 transitions. [2022-03-15 21:15:38,331 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 21:15:38,726 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 5 new interpolants: [385#(and (<= (+ bag1 sum1) sum2) (< sum2 (+ bag1 sum1 1))), 387#(and (<= (+ bag1 sum1) (+ bag2 sum2)) (<= (+ bag2 sum2) (+ bag1 sum1))), 386#(and (< sum2 (+ (select A i) bag1 sum1 1)) (<= (+ (select A i) bag1 sum1) sum2)), 389#(and (<= (+ (* 2 bag2) (select A j)) (+ (select A i) bag1 sum1)) (= bag2 sum2) (<= 0 bag2) (<= bag2 0) (<= (+ (select A i) bag1 sum1) (+ (* 2 bag2) (select A j)))), 388#(and (<= (+ bag2 sum2) (+ (select A i) bag1 sum1)) (<= (+ (select A i) bag1 sum1) (+ bag2 sum2)))] [2022-03-15 21:15:38,727 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-03-15 21:15:38,727 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 21:15:38,727 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-03-15 21:15:38,728 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=51, Invalid=255, Unknown=0, NotChecked=0, Total=306 [2022-03-15 21:15:38,728 INFO L87 Difference]: Start difference. First operand 19 states and 34 transitions. Second operand has 12 states, 11 states have (on average 2.090909090909091) internal successors, (23), 11 states have internal predecessors, (23), 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:15:38,891 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 21:15:38,891 INFO L93 Difference]: Finished difference Result 33 states and 61 transitions. [2022-03-15 21:15:38,891 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-03-15 21:15:38,891 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 2.090909090909091) internal successors, (23), 11 states have internal predecessors, (23), 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 10 [2022-03-15 21:15:38,891 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 21:15:38,892 INFO L225 Difference]: With dead ends: 33 [2022-03-15 21:15:38,892 INFO L226 Difference]: Without dead ends: 30 [2022-03-15 21:15:38,892 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 10 SyntacticMatches, 5 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 100 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=69, Invalid=351, Unknown=0, NotChecked=0, Total=420 [2022-03-15 21:15:38,893 INFO L933 BasicCegarLoop]: 1 mSDtfsCounter, 12 mSDsluCounter, 55 mSDsCounter, 0 mSdLazyCounter, 208 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 1 SdHoareTripleChecker+Invalid, 219 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 208 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-15 21:15:38,893 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [12 Valid, 1 Invalid, 219 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 208 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-15 21:15:38,893 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 30 states. [2022-03-15 21:15:38,895 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 30 to 27. [2022-03-15 21:15:38,895 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 27 states, 26 states have (on average 2.0) internal successors, (52), 26 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 21:15:38,895 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 52 transitions. [2022-03-15 21:15:38,895 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 52 transitions. Word has length 10 [2022-03-15 21:15:38,895 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 21:15:38,895 INFO L470 AbstractCegarLoop]: Abstraction has 27 states and 52 transitions. [2022-03-15 21:15:38,896 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 2.090909090909091) internal successors, (23), 11 states have internal predecessors, (23), 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:15:38,896 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 52 transitions. [2022-03-15 21:15:38,896 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2022-03-15 21:15:38,896 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 21:15:38,896 INFO L514 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 21:15:38,913 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2022-03-15 21:15:39,103 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable3 [2022-03-15 21:15:39,104 INFO L402 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION] === [2022-03-15 21:15:39,104 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 21:15:39,104 INFO L85 PathProgramCache]: Analyzing trace with hash -9908044, now seen corresponding path program 2 times [2022-03-15 21:15:39,106 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 21:15:39,107 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1870028375] [2022-03-15 21:15:39,107 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 21:15:39,107 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 21:15:39,114 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 21:15:39,143 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 3 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 21:15:39,143 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 21:15:39,144 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1870028375] [2022-03-15 21:15:39,144 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1870028375] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-15 21:15:39,144 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1077630474] [2022-03-15 21:15:39,144 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-15 21:15:39,144 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 21:15:39,144 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 21:15:39,145 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 21:15:39,146 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 21:15:39,167 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-15 21:15:39,168 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-15 21:15:39,168 INFO L263 TraceCheckSpWp]: Trace formula consists of 40 conjuncts, 6 conjunts are in the unsatisfiable core [2022-03-15 21:15:39,169 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-15 21:15:39,232 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 3 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 21:15:39,232 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-15 21:15:39,284 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 62 treesize of output 54 [2022-03-15 21:15:39,307 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 3 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 21:15:39,307 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1077630474] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-15 21:15:39,307 INFO L191 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-03-15 21:15:39,307 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5, 5] total 9 [2022-03-15 21:15:39,307 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [1270023745] [2022-03-15 21:15:39,307 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 21:15:39,308 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 21:15:39,310 INFO L252 McrAutomatonBuilder]: Finished intersection with 23 states and 33 transitions. [2022-03-15 21:15:39,310 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 21:15:39,535 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 6 new interpolants: [553#(< i N), 555#(or (<= N j) (< i N)), 557#(or (<= N i) (< (+ i 1) N) (<= N (+ j 1))), 554#(or (<= N i) (< (+ i 1) N)), 556#(or (<= N j) (<= N i) (< (+ i 1) N)), 545#(or (<= N (+ j 1)) (< i N))] [2022-03-15 21:15:39,535 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-03-15 21:15:39,535 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 21:15:39,535 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-03-15 21:15:39,535 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=58, Invalid=152, Unknown=0, NotChecked=0, Total=210 [2022-03-15 21:15:39,536 INFO L87 Difference]: Start difference. First operand 27 states and 52 transitions. Second operand has 12 states, 12 states have (on average 2.25) internal successors, (27), 11 states have internal predecessors, (27), 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:15:39,737 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 21:15:39,738 INFO L93 Difference]: Finished difference Result 50 states and 92 transitions. [2022-03-15 21:15:39,738 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2022-03-15 21:15:39,738 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 2.25) internal successors, (27), 11 states have internal predecessors, (27), 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 11 [2022-03-15 21:15:39,738 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 21:15:39,739 INFO L225 Difference]: With dead ends: 50 [2022-03-15 21:15:39,739 INFO L226 Difference]: Without dead ends: 43 [2022-03-15 21:15:39,739 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 46 GetRequests, 23 SyntacticMatches, 0 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 104 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=177, Invalid=423, Unknown=0, NotChecked=0, Total=600 [2022-03-15 21:15:39,739 INFO L933 BasicCegarLoop]: 1 mSDtfsCounter, 34 mSDsluCounter, 38 mSDsCounter, 0 mSdLazyCounter, 146 mSolverCounterSat, 25 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 1 SdHoareTripleChecker+Invalid, 171 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 25 IncrementalHoareTripleChecker+Valid, 146 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-15 21:15:39,740 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [34 Valid, 1 Invalid, 171 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [25 Valid, 146 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-15 21:15:39,740 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2022-03-15 21:15:39,742 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 31. [2022-03-15 21:15:39,742 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 31 states, 30 states have (on average 2.1333333333333333) internal successors, (64), 30 states have internal predecessors, (64), 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:15:39,742 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 64 transitions. [2022-03-15 21:15:39,742 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 64 transitions. Word has length 11 [2022-03-15 21:15:39,742 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 21:15:39,742 INFO L470 AbstractCegarLoop]: Abstraction has 31 states and 64 transitions. [2022-03-15 21:15:39,743 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 2.25) internal successors, (27), 11 states have internal predecessors, (27), 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:15:39,743 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 64 transitions. [2022-03-15 21:15:39,743 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2022-03-15 21:15:39,743 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 21:15:39,743 INFO L514 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 21:15:39,761 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2022-03-15 21:15:39,944 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 21:15:39,945 INFO L402 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION] === [2022-03-15 21:15:39,945 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 21:15:39,945 INFO L85 PathProgramCache]: Analyzing trace with hash 604193356, now seen corresponding path program 3 times [2022-03-15 21:15:39,946 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 21:15:39,947 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [528944068] [2022-03-15 21:15:39,947 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 21:15:39,947 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 21:15:39,961 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 21:15:39,994 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 21:15:39,994 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 21:15:39,994 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [528944068] [2022-03-15 21:15:39,994 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [528944068] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-15 21:15:39,994 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [670868952] [2022-03-15 21:15:39,994 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-03-15 21:15:39,994 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 21:15:39,994 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 21:15:39,995 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 21:15:39,996 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 21:15:40,016 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2022-03-15 21:15:40,016 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-15 21:15:40,017 INFO L263 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 6 conjunts are in the unsatisfiable core [2022-03-15 21:15:40,017 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-15 21:15:40,131 INFO L353 Elim1Store]: treesize reduction 9, result has 10.0 percent of original size [2022-03-15 21:15:40,131 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 114 treesize of output 90 [2022-03-15 21:15:40,154 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 21:15:40,154 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-15 21:15:40,218 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 62 treesize of output 54 [2022-03-15 21:15:40,233 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 1 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 21:15:40,234 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [670868952] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-15 21:15:40,234 INFO L191 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-03-15 21:15:40,234 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5, 5] total 9 [2022-03-15 21:15:40,234 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [2034615878] [2022-03-15 21:15:40,234 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 21:15:40,235 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 21:15:40,236 INFO L252 McrAutomatonBuilder]: Finished intersection with 23 states and 33 transitions. [2022-03-15 21:15:40,236 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 21:15:40,545 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 9 new interpolants: [766#(or (<= (+ 2 j) N) (< i N)), 767#(or (<= N i) (< (+ i 1) N) (<= (+ 2 j) N)), 765#(or (<= N (+ i 1)) (< (+ 2 i) N) (< j N)), 760#(< i N), 761#(or (<= N i) (< (+ i 1) N)), 763#(or (<= N i) (< (+ i 1) N) (< j N)), 764#(or (<= N (+ i 1)) (< (+ 2 i) N)), 762#(or (<= (+ j 1) N) (< i N)), 768#(or (<= N (+ i 1)) (< (+ 2 i) N) (<= (+ 2 j) N))] [2022-03-15 21:15:40,545 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2022-03-15 21:15:40,545 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 21:15:40,545 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2022-03-15 21:15:40,545 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=86, Invalid=256, Unknown=0, NotChecked=0, Total=342 [2022-03-15 21:15:40,546 INFO L87 Difference]: Start difference. First operand 31 states and 64 transitions. Second operand has 15 states, 15 states have (on average 2.066666666666667) internal successors, (31), 14 states have internal predecessors, (31), 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:15:40,825 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 21:15:40,825 INFO L93 Difference]: Finished difference Result 57 states and 119 transitions. [2022-03-15 21:15:40,826 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2022-03-15 21:15:40,826 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.066666666666667) internal successors, (31), 14 states have internal predecessors, (31), 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 11 [2022-03-15 21:15:40,826 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 21:15:40,826 INFO L225 Difference]: With dead ends: 57 [2022-03-15 21:15:40,826 INFO L226 Difference]: Without dead ends: 57 [2022-03-15 21:15:40,827 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 50 GetRequests, 16 SyntacticMatches, 3 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 179 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=261, Invalid=795, Unknown=0, NotChecked=0, Total=1056 [2022-03-15 21:15:40,827 INFO L933 BasicCegarLoop]: 1 mSDtfsCounter, 55 mSDsluCounter, 37 mSDsCounter, 0 mSdLazyCounter, 195 mSolverCounterSat, 53 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 55 SdHoareTripleChecker+Valid, 1 SdHoareTripleChecker+Invalid, 248 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 53 IncrementalHoareTripleChecker+Valid, 195 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-15 21:15:40,828 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [55 Valid, 1 Invalid, 248 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [53 Valid, 195 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-15 21:15:40,828 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 57 states. [2022-03-15 21:15:40,831 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 57 to 47. [2022-03-15 21:15:40,831 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 47 states, 46 states have (on average 2.282608695652174) internal successors, (105), 46 states have internal predecessors, (105), 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:15:40,831 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 105 transitions. [2022-03-15 21:15:40,831 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 105 transitions. Word has length 11 [2022-03-15 21:15:40,831 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 21:15:40,831 INFO L470 AbstractCegarLoop]: Abstraction has 47 states and 105 transitions. [2022-03-15 21:15:40,831 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.066666666666667) internal successors, (31), 14 states have internal predecessors, (31), 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:15:40,832 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 105 transitions. [2022-03-15 21:15:40,832 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2022-03-15 21:15:40,832 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 21:15:40,832 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 21:15:40,850 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 21:15:41,032 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 21:15:41,033 INFO L402 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION] === [2022-03-15 21:15:41,033 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 21:15:41,033 INFO L85 PathProgramCache]: Analyzing trace with hash 1550230599, now seen corresponding path program 4 times [2022-03-15 21:15:41,034 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 21:15:41,034 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [51694541] [2022-03-15 21:15:41,034 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 21:15:41,034 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 21:15:41,060 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 21:15:41,343 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 21:15:41,344 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 21:15:41,344 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [51694541] [2022-03-15 21:15:41,344 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [51694541] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-15 21:15:41,344 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1469667902] [2022-03-15 21:15:41,344 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-03-15 21:15:41,344 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 21:15:41,344 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 21:15:41,345 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 21:15:41,348 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 21:15:41,368 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-03-15 21:15:41,368 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-15 21:15:41,369 WARN L261 TraceCheckSpWp]: Trace formula consists of 41 conjuncts, 26 conjunts are in the unsatisfiable core [2022-03-15 21:15:41,370 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-15 21:15:41,585 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 58 treesize of output 38 [2022-03-15 21:15:41,624 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 21:15:41,625 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-15 21:15:41,901 INFO L173 IndexEqualityManager]: detected equality via solver [2022-03-15 21:15:41,901 INFO L173 IndexEqualityManager]: detected equality via solver [2022-03-15 21:15:41,902 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-03-15 21:15:41,907 INFO L353 Elim1Store]: treesize reduction 15, result has 21.1 percent of original size [2022-03-15 21:15:41,908 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 4 select indices, 4 select index equivalence classes, 1 disjoint index pairs (out of 6 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 101 treesize of output 77 [2022-03-15 21:15:41,990 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 21:15:41,990 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1469667902] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-15 21:15:41,990 INFO L191 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-03-15 21:15:41,990 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 18 [2022-03-15 21:15:41,990 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [938877260] [2022-03-15 21:15:41,990 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 21:15:41,992 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 21:15:41,994 INFO L252 McrAutomatonBuilder]: Finished intersection with 28 states and 42 transitions. [2022-03-15 21:15:41,994 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 21:15:42,806 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 11 new interpolants: [1034#(and (<= (+ bag1 sum1) sum2) (< sum2 (+ bag1 sum1 1))), 1044#(and (= sum2 0) (= bag2 0) (= j 0) (<= (+ (select A j) (select A 1)) (+ (select A i) bag1 sum1 (select A (+ i 1)))) (<= (+ (select A i) bag1 sum1 (select A (+ i 1))) (+ (select A j) (select A (+ j 1)) bag2 sum2))), 1041#(and (= sum2 0) (<= (+ (select A j) bag2 sum2) (+ (select A i) bag1 sum1)) (<= (+ (select A i) bag1 sum1) (+ (select A j) bag2 sum2))), 1035#(and (< sum2 (+ (select A i) bag1 sum1 1)) (<= (+ (select A i) bag1 sum1) sum2)), 1038#(and (< sum2 (+ (select A i) bag1 sum1 (select A (+ i 1)) 1)) (<= (+ (select A i) bag1 sum1 (select A (+ i 1))) sum2)), 1042#(and (= bag2 0) (<= (+ (select A j) (select A (+ j 1)) bag2 sum2) (+ (select A i) bag1 sum1)) (= j 0) (<= (+ (select A i) bag1 sum1) (+ (select A j) (select A (+ j 1)) bag2 sum2)) (<= (+ (select A j) (select A 1)) (+ (select A i) bag1 sum1)) (<= (+ (select A i) bag1 sum1) (+ (select A j) (select A 1)))), 1036#(and (<= (+ bag1 sum1) (+ bag2 sum2)) (<= (+ bag2 sum2) (+ bag1 sum1))), 1039#(and (<= (+ bag2 sum2) (+ (select A i) bag1 sum1 (select A (+ i 1)))) (<= (+ (select A i) bag1 sum1 (select A (+ i 1))) (+ bag2 sum2))), 1037#(and (<= (+ bag2 sum2) (+ (select A i) bag1 sum1)) (<= (+ (select A i) bag1 sum1) (+ bag2 sum2))), 1040#(and (= sum2 0) (<= (+ bag1 sum1) (+ (select A j) bag2 sum2)) (<= (+ (select A j) bag2 sum2) (+ bag1 sum1))), 1043#(and (= sum2 0) (<= (+ (select A i) bag1 sum1 (select A (+ i 1))) (+ (select A j) bag2 sum2)) (<= (+ (select A j) bag2 sum2) (+ (select A i) bag1 sum1 (select A (+ i 1)))))] [2022-03-15 21:15:42,807 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2022-03-15 21:15:42,807 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 21:15:42,807 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2022-03-15 21:15:42,807 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=113, Invalid=817, Unknown=0, NotChecked=0, Total=930 [2022-03-15 21:15:42,808 INFO L87 Difference]: Start difference. First operand 47 states and 105 transitions. Second operand has 20 states, 19 states have (on average 2.0) internal successors, (38), 19 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 21:15:43,137 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 21:15:43,137 INFO L93 Difference]: Finished difference Result 72 states and 156 transitions. [2022-03-15 21:15:43,137 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2022-03-15 21:15:43,137 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 19 states have (on average 2.0) internal successors, (38), 19 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 12 [2022-03-15 21:15:43,138 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 21:15:43,139 INFO L225 Difference]: With dead ends: 72 [2022-03-15 21:15:43,139 INFO L226 Difference]: Without dead ends: 65 [2022-03-15 21:15:43,140 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 46 GetRequests, 11 SyntacticMatches, 4 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 301 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=126, Invalid=930, Unknown=0, NotChecked=0, Total=1056 [2022-03-15 21:15:43,140 INFO L933 BasicCegarLoop]: 1 mSDtfsCounter, 13 mSDsluCounter, 147 mSDsCounter, 0 mSdLazyCounter, 587 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 1 SdHoareTripleChecker+Invalid, 599 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 587 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-03-15 21:15:43,140 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [13 Valid, 1 Invalid, 599 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 587 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-03-15 21:15:43,141 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 65 states. [2022-03-15 21:15:43,143 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 65 to 48. [2022-03-15 21:15:43,143 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 48 states, 47 states have (on average 2.297872340425532) internal successors, (108), 47 states have internal predecessors, (108), 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:15:43,144 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 108 transitions. [2022-03-15 21:15:43,144 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 108 transitions. Word has length 12 [2022-03-15 21:15:43,144 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 21:15:43,144 INFO L470 AbstractCegarLoop]: Abstraction has 48 states and 108 transitions. [2022-03-15 21:15:43,144 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 19 states have (on average 2.0) internal successors, (38), 19 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 21:15:43,144 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 108 transitions. [2022-03-15 21:15:43,144 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2022-03-15 21:15:43,144 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 21:15:43,144 INFO L514 BasicCegarLoop]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 21:15:43,162 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 21:15:43,360 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 21:15:43,361 INFO L402 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION] === [2022-03-15 21:15:43,361 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 21:15:43,361 INFO L85 PathProgramCache]: Analyzing trace with hash -775194991, now seen corresponding path program 5 times [2022-03-15 21:15:43,362 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 21:15:43,362 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1162386278] [2022-03-15 21:15:43,362 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 21:15:43,362 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 21:15:43,368 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 21:15:43,406 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 5 proven. 1 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2022-03-15 21:15:43,407 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 21:15:43,407 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1162386278] [2022-03-15 21:15:43,407 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1162386278] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-15 21:15:43,407 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [592692493] [2022-03-15 21:15:43,407 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2022-03-15 21:15:43,407 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 21:15:43,407 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 21:15:43,409 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 21:15:43,410 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 21:15:43,435 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 3 check-sat command(s) [2022-03-15 21:15:43,435 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-15 21:15:43,435 INFO L263 TraceCheckSpWp]: Trace formula consists of 39 conjuncts, 6 conjunts are in the unsatisfiable core [2022-03-15 21:15:43,436 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-15 21:15:43,568 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 4 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2022-03-15 21:15:43,568 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-15 21:15:43,592 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 62 treesize of output 54 [2022-03-15 21:15:43,613 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 5 proven. 1 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2022-03-15 21:15:43,613 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [592692493] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-15 21:15:43,613 INFO L191 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-03-15 21:15:43,613 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5, 5] total 10 [2022-03-15 21:15:43,614 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [214846902] [2022-03-15 21:15:43,614 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 21:15:43,614 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 21:15:43,616 INFO L252 McrAutomatonBuilder]: Finished intersection with 27 states and 40 transitions. [2022-03-15 21:15:43,616 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 21:15:43,779 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 4 new interpolants: [1294#(< j N), 1295#(or (<= N j) (< (+ j 1) N)), 1297#(or (<= N j) (<= N i) (< (+ j 1) N)), 1296#(or (<= N i) (< j N))] [2022-03-15 21:15:43,779 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-03-15 21:15:43,779 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 21:15:43,780 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-03-15 21:15:43,780 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=47, Invalid=163, Unknown=0, NotChecked=0, Total=210 [2022-03-15 21:15:43,780 INFO L87 Difference]: Start difference. First operand 48 states and 108 transitions. Second operand has 10 states, 10 states have (on average 2.8) internal successors, (28), 9 states have internal predecessors, (28), 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:15:43,948 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 21:15:43,948 INFO L93 Difference]: Finished difference Result 70 states and 142 transitions. [2022-03-15 21:15:43,948 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2022-03-15 21:15:43,948 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.8) internal successors, (28), 9 states have internal predecessors, (28), 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 12 [2022-03-15 21:15:43,948 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 21:15:43,950 INFO L225 Difference]: With dead ends: 70 [2022-03-15 21:15:43,950 INFO L226 Difference]: Without dead ends: 67 [2022-03-15 21:15:43,950 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 51 GetRequests, 28 SyntacticMatches, 0 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 109 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=143, Invalid=457, Unknown=0, NotChecked=0, Total=600 [2022-03-15 21:15:43,951 INFO L933 BasicCegarLoop]: 1 mSDtfsCounter, 29 mSDsluCounter, 30 mSDsCounter, 0 mSdLazyCounter, 121 mSolverCounterSat, 24 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 29 SdHoareTripleChecker+Valid, 1 SdHoareTripleChecker+Invalid, 145 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 24 IncrementalHoareTripleChecker+Valid, 121 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-15 21:15:43,952 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [29 Valid, 1 Invalid, 145 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [24 Valid, 121 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-15 21:15:43,952 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 67 states. [2022-03-15 21:15:43,962 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 67 to 47. [2022-03-15 21:15:43,963 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 47 states, 46 states have (on average 2.217391304347826) internal successors, (102), 46 states have internal predecessors, (102), 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:15:43,963 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 102 transitions. [2022-03-15 21:15:43,963 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 102 transitions. Word has length 12 [2022-03-15 21:15:43,963 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 21:15:43,963 INFO L470 AbstractCegarLoop]: Abstraction has 47 states and 102 transitions. [2022-03-15 21:15:43,963 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.8) internal successors, (28), 9 states have internal predecessors, (28), 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:15:43,964 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 102 transitions. [2022-03-15 21:15:43,968 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2022-03-15 21:15:43,968 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 21:15:43,968 INFO L514 BasicCegarLoop]: trace histogram [3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 21:15:43,984 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 21:15:44,183 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 21:15:44,185 INFO L402 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION] === [2022-03-15 21:15:44,186 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 21:15:44,186 INFO L85 PathProgramCache]: Analyzing trace with hash 812614060, now seen corresponding path program 6 times [2022-03-15 21:15:44,186 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 21:15:44,186 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1363351672] [2022-03-15 21:15:44,186 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 21:15:44,186 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 21:15:44,192 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 21:15:44,221 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 6 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 21:15:44,221 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 21:15:44,221 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1363351672] [2022-03-15 21:15:44,221 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1363351672] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-15 21:15:44,221 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [213565498] [2022-03-15 21:15:44,222 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-03-15 21:15:44,222 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 21:15:44,222 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 21:15:44,223 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 21:15:44,224 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 21:15:44,244 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 3 check-sat command(s) [2022-03-15 21:15:44,244 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-15 21:15:44,245 INFO L263 TraceCheckSpWp]: Trace formula consists of 44 conjuncts, 8 conjunts are in the unsatisfiable core [2022-03-15 21:15:44,245 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-15 21:15:44,394 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 6 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 21:15:44,394 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-15 21:15:44,471 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 62 treesize of output 54 [2022-03-15 21:15:44,487 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 6 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 21:15:44,488 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [213565498] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-15 21:15:44,488 INFO L191 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-03-15 21:15:44,488 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 13 [2022-03-15 21:15:44,488 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [1025480966] [2022-03-15 21:15:44,488 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 21:15:44,489 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 21:15:44,492 INFO L252 McrAutomatonBuilder]: Finished intersection with 33 states and 51 transitions. [2022-03-15 21:15:44,492 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 21:15:44,953 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 12 new interpolants: [1556#(or (<= N (+ 2 j)) (< i N)), 1576#(or (<= N (+ i 1)) (< (+ 2 i) N) (<= N (+ j 1))), 1560#(or (<= N (+ 2 j)) (<= N i) (< (+ i 1) N)), 1569#(or (<= N j) (< i N)), 1575#(or (<= N (+ i 1)) (<= N j) (< (+ 2 i) N)), 1570#(or (<= N (+ j 1)) (< i N)), 1572#(or (<= N j) (<= N i) (< (+ i 1) N)), 1577#(or (<= N (+ i 1)) (<= N (+ 2 j)) (< (+ 2 i) N)), 1574#(or (<= N (+ i 1)) (< (+ 2 i) N)), 1571#(or (<= N i) (< (+ i 1) N)), 1568#(< i N), 1573#(or (<= N i) (< (+ i 1) N) (<= N (+ j 1)))] [2022-03-15 21:15:44,953 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2022-03-15 21:15:44,953 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 21:15:44,953 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2022-03-15 21:15:44,953 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=124, Invalid=428, Unknown=0, NotChecked=0, Total=552 [2022-03-15 21:15:44,954 INFO L87 Difference]: Start difference. First operand 47 states and 102 transitions. Second operand has 20 states, 20 states have (on average 2.15) internal successors, (43), 19 states have internal predecessors, (43), 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:15:45,704 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 21:15:45,705 INFO L93 Difference]: Finished difference Result 164 states and 374 transitions. [2022-03-15 21:15:45,705 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 48 states. [2022-03-15 21:15:45,705 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 20 states have (on average 2.15) internal successors, (43), 19 states have internal predecessors, (43), 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 13 [2022-03-15 21:15:45,705 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 21:15:45,706 INFO L225 Difference]: With dead ends: 164 [2022-03-15 21:15:45,706 INFO L226 Difference]: Without dead ends: 151 [2022-03-15 21:15:45,707 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 88 GetRequests, 28 SyntacticMatches, 0 SemanticMatches, 60 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1114 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=1013, Invalid=2769, Unknown=0, NotChecked=0, Total=3782 [2022-03-15 21:15:45,707 INFO L933 BasicCegarLoop]: 1 mSDtfsCounter, 105 mSDsluCounter, 50 mSDsCounter, 0 mSdLazyCounter, 244 mSolverCounterSat, 88 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 105 SdHoareTripleChecker+Valid, 1 SdHoareTripleChecker+Invalid, 332 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 88 IncrementalHoareTripleChecker+Valid, 244 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-03-15 21:15:45,708 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [105 Valid, 1 Invalid, 332 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [88 Valid, 244 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-03-15 21:15:45,708 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 151 states. [2022-03-15 21:15:45,711 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 151 to 96. [2022-03-15 21:15:45,711 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 96 states, 95 states have (on average 2.6526315789473682) internal successors, (252), 95 states have internal predecessors, (252), 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:15:45,712 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 252 transitions. [2022-03-15 21:15:45,712 INFO L78 Accepts]: Start accepts. Automaton has 96 states and 252 transitions. Word has length 13 [2022-03-15 21:15:45,712 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 21:15:45,712 INFO L470 AbstractCegarLoop]: Abstraction has 96 states and 252 transitions. [2022-03-15 21:15:45,712 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 20 states have (on average 2.15) internal successors, (43), 19 states have internal predecessors, (43), 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:15:45,712 INFO L276 IsEmpty]: Start isEmpty. Operand 96 states and 252 transitions. [2022-03-15 21:15:45,713 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2022-03-15 21:15:45,713 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 21:15:45,713 INFO L514 BasicCegarLoop]: trace histogram [3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 21:15:45,728 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 21:15:45,920 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 21:15:45,920 INFO L402 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION] === [2022-03-15 21:15:45,920 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 21:15:45,920 INFO L85 PathProgramCache]: Analyzing trace with hash -1625079020, now seen corresponding path program 7 times [2022-03-15 21:15:45,921 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 21:15:45,921 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2132533228] [2022-03-15 21:15:45,921 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 21:15:45,921 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 21:15:45,927 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 21:15:45,961 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 1 proven. 8 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 21:15:45,961 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 21:15:45,961 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2132533228] [2022-03-15 21:15:45,961 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2132533228] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-15 21:15:45,961 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1266809149] [2022-03-15 21:15:45,961 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2022-03-15 21:15:45,961 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 21:15:45,961 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 21:15:45,962 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 21:15:45,963 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 21:15:45,983 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 21:15:45,983 INFO L263 TraceCheckSpWp]: Trace formula consists of 42 conjuncts, 8 conjunts are in the unsatisfiable core [2022-03-15 21:15:45,984 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-15 21:15:46,214 INFO L353 Elim1Store]: treesize reduction 32, result has 3.0 percent of original size [2022-03-15 21:15:46,214 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 218 treesize of output 146 [2022-03-15 21:15:46,258 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 21:15:46,258 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-15 21:15:46,359 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 62 treesize of output 54 [2022-03-15 21:15:46,378 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 21:15:46,378 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1266809149] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-15 21:15:46,378 INFO L191 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-03-15 21:15:46,379 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 13 [2022-03-15 21:15:46,379 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [1510734150] [2022-03-15 21:15:46,379 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 21:15:46,380 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 21:15:46,383 INFO L252 McrAutomatonBuilder]: Finished intersection with 33 states and 51 transitions. [2022-03-15 21:15:46,383 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 21:15:47,146 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 16 new interpolants: [2110#(or (<= N (+ i 1)) (< (+ 2 i) N) (<= (+ 3 j) N)), 2102#(or (<= N (+ i 1)) (< (+ 2 i) N) (< j N)), 2105#(or (<= N i) (< (+ i 1) N) (<= (+ 2 j) N)), 2108#(or (<= (+ 3 j) N) (< i N)), 2100#(or (<= (+ j 1) N) (< i N)), 2096#(< i N), 2106#(or (<= N (+ i 1)) (< (+ 2 i) N) (<= (+ 2 j) N)), 2104#(or (<= (+ 2 j) N) (< i N)), 2109#(or (<= N i) (< (+ i 1) N) (<= (+ 3 j) N)), 2099#(or (<= N (+ 2 i)) (< (+ 3 i) N)), 2111#(or (<= N (+ 2 i)) (< (+ 3 i) N) (<= (+ 3 j) N)), 2098#(or (<= N (+ i 1)) (< (+ 2 i) N)), 2097#(or (<= N i) (< (+ i 1) N)), 2101#(or (<= N i) (< (+ i 1) N) (< j N)), 2107#(or (<= N (+ 2 i)) (<= (+ 2 j) N) (< (+ 3 i) N)), 2103#(or (<= N (+ 2 i)) (< (+ 3 i) N) (< j N))] [2022-03-15 21:15:47,146 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2022-03-15 21:15:47,147 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 21:15:47,147 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2022-03-15 21:15:47,147 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=201, Invalid=669, Unknown=0, NotChecked=0, Total=870 [2022-03-15 21:15:47,147 INFO L87 Difference]: Start difference. First operand 96 states and 252 transitions. Second operand has 24 states, 24 states have (on average 2.0) internal successors, (48), 23 states have internal predecessors, (48), 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:15:47,769 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 21:15:47,770 INFO L93 Difference]: Finished difference Result 189 states and 486 transitions. [2022-03-15 21:15:47,770 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 41 states. [2022-03-15 21:15:47,770 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 24 states have (on average 2.0) internal successors, (48), 23 states have internal predecessors, (48), 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 13 [2022-03-15 21:15:47,770 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 21:15:47,771 INFO L225 Difference]: With dead ends: 189 [2022-03-15 21:15:47,771 INFO L226 Difference]: Without dead ends: 189 [2022-03-15 21:15:47,772 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 77 GetRequests, 19 SyntacticMatches, 3 SemanticMatches, 55 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 741 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=741, Invalid=2451, Unknown=0, NotChecked=0, Total=3192 [2022-03-15 21:15:47,772 INFO L933 BasicCegarLoop]: 1 mSDtfsCounter, 82 mSDsluCounter, 69 mSDsCounter, 0 mSdLazyCounter, 469 mSolverCounterSat, 94 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 82 SdHoareTripleChecker+Valid, 1 SdHoareTripleChecker+Invalid, 563 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 94 IncrementalHoareTripleChecker+Valid, 469 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-03-15 21:15:47,773 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [82 Valid, 1 Invalid, 563 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [94 Valid, 469 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-03-15 21:15:47,774 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 189 states. [2022-03-15 21:15:47,781 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 189 to 137. [2022-03-15 21:15:47,781 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 137 states, 136 states have (on average 2.7794117647058822) internal successors, (378), 136 states have internal predecessors, (378), 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:15:47,781 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 137 states to 137 states and 378 transitions. [2022-03-15 21:15:47,781 INFO L78 Accepts]: Start accepts. Automaton has 137 states and 378 transitions. Word has length 13 [2022-03-15 21:15:47,781 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 21:15:47,781 INFO L470 AbstractCegarLoop]: Abstraction has 137 states and 378 transitions. [2022-03-15 21:15:47,782 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 24 states have (on average 2.0) internal successors, (48), 23 states have internal predecessors, (48), 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:15:47,782 INFO L276 IsEmpty]: Start isEmpty. Operand 137 states and 378 transitions. [2022-03-15 21:15:47,782 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2022-03-15 21:15:47,782 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 21:15:47,782 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 21:15:47,798 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 21:15:47,997 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,SelfDestructingSolverStorable9 [2022-03-15 21:15:47,997 INFO L402 AbstractCegarLoop]: === Iteration 11 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION] === [2022-03-15 21:15:47,997 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 21:15:47,998 INFO L85 PathProgramCache]: Analyzing trace with hash 1162263679, now seen corresponding path program 8 times [2022-03-15 21:15:47,999 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 21:15:47,999 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [190256448] [2022-03-15 21:15:47,999 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 21:15:47,999 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 21:15:48,067 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 21:15:51,309 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 21:15:51,309 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 21:15:51,309 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [190256448] [2022-03-15 21:15:51,309 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [190256448] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-15 21:15:51,310 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1328464964] [2022-03-15 21:15:51,310 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-15 21:15:51,310 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 21:15:51,310 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 21:15:51,311 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 21:15:51,311 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 21:15:51,339 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-15 21:15:51,339 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-15 21:15:51,339 WARN L261 TraceCheckSpWp]: Trace formula consists of 45 conjuncts, 28 conjunts are in the unsatisfiable core [2022-03-15 21:15:51,340 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-15 21:15:51,744 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 3 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 94 treesize of output 64 [2022-03-15 21:15:51,778 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 21:15:51,778 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-15 21:15:52,166 INFO L173 IndexEqualityManager]: detected equality via solver [2022-03-15 21:15:52,168 INFO L173 IndexEqualityManager]: detected equality via solver [2022-03-15 21:15:52,168 INFO L173 IndexEqualityManager]: detected equality via solver [2022-03-15 21:15:52,168 INFO L173 IndexEqualityManager]: detected equality via solver [2022-03-15 21:15:52,169 INFO L173 IndexEqualityManager]: detected equality via solver [2022-03-15 21:15:52,169 INFO L173 IndexEqualityManager]: detected equality via solver [2022-03-15 21:15:52,170 INFO L173 IndexEqualityManager]: detected equality via solver [2022-03-15 21:15:52,213 INFO L353 Elim1Store]: treesize reduction 20, result has 74.7 percent of original size [2022-03-15 21:15:52,213 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 6 select indices, 6 select index equivalence classes, 7 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 8 case distinctions, treesize of input 120 treesize of output 138 [2022-03-15 21:15:52,418 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 21:15:52,419 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1328464964] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-15 21:15:52,419 INFO L191 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-03-15 21:15:52,419 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9] total 22 [2022-03-15 21:15:52,419 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [1903165558] [2022-03-15 21:15:52,419 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 21:15:52,420 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 21:15:52,423 INFO L252 McrAutomatonBuilder]: Finished intersection with 39 states and 62 transitions. [2022-03-15 21:15:52,423 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 21:15:54,047 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 19 new interpolants: [2740#(and (= sum2 0) (<= (+ bag1 sum1) (+ (select A j) (select A (+ j 1)) bag2)) (<= (+ (select A j) (select A (+ j 1)) bag2) (+ bag1 sum1))), 2744#(and (<= (+ (select A i) (select A (+ 2 i)) bag1 sum1 (select A (+ i 1))) (+ bag2 sum2)) (<= (+ bag2 sum2) (+ (select A i) (select A (+ 2 i)) bag1 sum1 (select A (+ i 1))))), 2749#(and (<= (+ (select A i) (select A (+ 2 i)) bag1 sum1 (select A (+ i 1))) (+ (select A j) (select A (+ 2 j)) (select A (+ j 1)))) (<= (+ (select A i) (select A (+ 2 i)) bag1 sum1 (select A (+ i 1))) (+ (select A j) (select A (+ 2 j)) (select A (+ j 1)) bag2 sum2)) (<= (+ (select A j) (select A (+ 2 j)) (select A (+ j 1)) bag2 sum2) (+ (select A i) (select A (+ 2 i)) bag1 sum1 (select A (+ i 1)))) (= j 0) (<= 0 bag2) (<= (+ (select A j) bag2 (select A 1) (select A 2)) (+ (select A i) (select A (+ 2 i)) bag1 sum1 (select A (+ i 1))))), 2747#(and (= sum2 0) (<= (+ (select A i) (select A (+ 2 i)) bag1 sum1 (select A (+ i 1))) (+ (select A j) (select A (+ j 1)) bag2 sum2)) (<= (+ (select A j) (select A (+ j 1)) bag2 sum2) (+ (select A i) (select A (+ 2 i)) bag1 sum1 (select A (+ i 1))))), 2741#(and (= sum2 0) (<= (+ (select A j) (select A (+ j 1)) bag2 sum2) (+ (select A i) bag1 sum1)) (<= (+ (select A i) bag1 sum1) (+ (select A j) (select A (+ j 1)) bag2))), 2731#(and (<= (+ bag1 sum1) sum2) (< sum2 (+ bag1 sum1 1))), 2735#(and (< sum2 (+ (select A i) bag1 sum1 (select A (+ i 1)) 1)) (<= (+ (select A i) bag1 sum1 (select A (+ i 1))) sum2)), 2742#(and (= sum2 0) (= j 0) (<= 0 bag2) (<= (+ (select A j) bag2 (select A 1) (select A 2)) (+ (select A i) bag1 sum1)) (<= (+ (select A i) bag1 sum1) (+ (select A j) (select A (+ 2 j)) (select A (+ j 1))))), 2748#(and (<= (+ (select A i) bag1 sum1 (select A (+ i 1))) (+ (select A j) (select A (+ 2 j)) (select A (+ j 1)))) (<= (+ (select A j) bag2 (select A 1) (select A 2)) (+ (select A i) bag1 sum1 (select A (+ i 1)))) (<= (+ (select A i) bag1 sum1 (select A (+ i 1))) (+ (select A j) (select A (+ 2 j)) (select A (+ j 1)) bag2 sum2)) (= j 0) (<= 0 bag2) (<= (+ (select A j) (select A (+ 2 j)) (select A (+ j 1)) bag2 sum2) (+ (select A i) bag1 sum1 (select A (+ i 1))))), 2733#(and (< sum2 (+ (select A i) bag1 sum1 1)) (<= (+ (select A i) bag1 sum1) sum2)), 2739#(and (<= (+ (select A j) bag2 sum2) (+ (select A i) bag1 sum1)) (<= (+ (select A i) bag1 sum1) (+ (select A j) bag2 sum2))), 2737#(and (< sum2 (+ (select A i) (select A (+ 2 i)) bag1 sum1 (select A (+ i 1)) 1)) (<= (+ (select A i) (select A (+ 2 i)) bag1 sum1 (select A (+ i 1))) sum2)), 2746#(and (<= (+ (select A i) (select A (+ 2 i)) bag1 sum1 (select A (+ i 1))) (+ (select A j) bag2 sum2)) (<= (+ (select A j) bag2 sum2) (+ (select A i) (select A (+ 2 i)) bag1 sum1 (select A (+ i 1))))), 2738#(and (<= (+ bag1 sum1) (+ (select A j) bag2 sum2)) (<= (+ (select A j) bag2 sum2) (+ bag1 sum1))), 2734#(and (<= (+ bag2 sum2) (+ (select A i) bag1 sum1)) (<= (+ (select A i) bag1 sum1) (+ bag2 sum2))), 2736#(and (<= (+ bag2 sum2) (+ (select A i) bag1 sum1 (select A (+ i 1)))) (<= (+ (select A i) bag1 sum1 (select A (+ i 1))) (+ bag2 sum2))), 2743#(and (<= (+ (select A i) bag1 sum1 (select A (+ i 1))) (+ (select A j) bag2 sum2)) (<= (+ (select A j) bag2 sum2) (+ (select A i) bag1 sum1 (select A (+ i 1))))), 2745#(and (= sum2 0) (<= (+ (select A j) (select A (+ j 1)) bag2 sum2) (+ (select A i) bag1 sum1 (select A (+ i 1)))) (<= (+ (select A i) bag1 sum1 (select A (+ i 1))) (+ (select A j) (select A (+ j 1)) bag2 sum2))), 2732#(and (<= (+ bag1 sum1) (+ bag2 sum2)) (<= (+ bag2 sum2) (+ bag1 sum1)))] [2022-03-15 21:15:54,048 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 30 states [2022-03-15 21:15:54,048 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 21:15:54,048 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2022-03-15 21:15:54,048 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=146, Invalid=1660, Unknown=0, NotChecked=0, Total=1806 [2022-03-15 21:15:54,049 INFO L87 Difference]: Start difference. First operand 137 states and 378 transitions. Second operand has 30 states, 29 states have (on average 1.9655172413793103) internal successors, (57), 29 states have internal predecessors, (57), 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:15:54,765 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 21:15:54,765 INFO L93 Difference]: Finished difference Result 207 states and 547 transitions. [2022-03-15 21:15:54,765 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2022-03-15 21:15:54,766 INFO L78 Accepts]: Start accepts. Automaton has has 30 states, 29 states have (on average 1.9655172413793103) internal successors, (57), 29 states have internal predecessors, (57), 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 14 [2022-03-15 21:15:54,766 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 21:15:54,767 INFO L225 Difference]: With dead ends: 207 [2022-03-15 21:15:54,767 INFO L226 Difference]: Without dead ends: 198 [2022-03-15 21:15:54,767 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 65 GetRequests, 11 SyntacticMatches, 7 SemanticMatches, 47 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 623 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=181, Invalid=2171, Unknown=0, NotChecked=0, Total=2352 [2022-03-15 21:15:54,768 INFO L933 BasicCegarLoop]: 1 mSDtfsCounter, 13 mSDsluCounter, 283 mSDsCounter, 0 mSdLazyCounter, 1161 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 1 SdHoareTripleChecker+Invalid, 1174 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 1161 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2022-03-15 21:15:54,768 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [13 Valid, 1 Invalid, 1174 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 1161 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2022-03-15 21:15:54,768 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 198 states. [2022-03-15 21:15:54,772 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 198 to 153. [2022-03-15 21:15:54,772 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 153 states, 152 states have (on average 2.776315789473684) internal successors, (422), 152 states have internal predecessors, (422), 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:15:54,772 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 153 states to 153 states and 422 transitions. [2022-03-15 21:15:54,773 INFO L78 Accepts]: Start accepts. Automaton has 153 states and 422 transitions. Word has length 14 [2022-03-15 21:15:54,773 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 21:15:54,773 INFO L470 AbstractCegarLoop]: Abstraction has 153 states and 422 transitions. [2022-03-15 21:15:54,773 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 30 states, 29 states have (on average 1.9655172413793103) internal successors, (57), 29 states have internal predecessors, (57), 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:15:54,773 INFO L276 IsEmpty]: Start isEmpty. Operand 153 states and 422 transitions. [2022-03-15 21:15:54,773 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2022-03-15 21:15:54,773 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 21:15:54,773 INFO L514 BasicCegarLoop]: trace histogram [4, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 21:15:54,793 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 21:15:54,991 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 21:15:54,991 INFO L402 AbstractCegarLoop]: === Iteration 12 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION] === [2022-03-15 21:15:54,992 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 21:15:54,992 INFO L85 PathProgramCache]: Analyzing trace with hash -1881754167, now seen corresponding path program 9 times [2022-03-15 21:15:54,992 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 21:15:54,992 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1821639378] [2022-03-15 21:15:54,992 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 21:15:54,993 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 21:15:54,998 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 21:15:55,107 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 10 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 21:15:55,107 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 21:15:55,107 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1821639378] [2022-03-15 21:15:55,107 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1821639378] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-15 21:15:55,107 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1552108680] [2022-03-15 21:15:55,107 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-03-15 21:15:55,108 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 21:15:55,108 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 21:15:55,108 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 21:15:55,109 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 21:15:55,131 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2022-03-15 21:15:55,131 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-15 21:15:55,131 INFO L263 TraceCheckSpWp]: Trace formula consists of 43 conjuncts, 8 conjunts are in the unsatisfiable core [2022-03-15 21:15:55,132 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-15 21:15:55,378 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 6 proven. 6 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2022-03-15 21:15:55,378 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-15 21:15:55,438 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 62 treesize of output 54 [2022-03-15 21:15:55,458 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 9 proven. 3 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2022-03-15 21:15:55,458 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1552108680] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-15 21:15:55,458 INFO L191 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-03-15 21:15:55,458 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 7, 7] total 15 [2022-03-15 21:15:55,458 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [1203613271] [2022-03-15 21:15:55,458 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 21:15:55,459 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 21:15:55,463 INFO L252 McrAutomatonBuilder]: Finished intersection with 38 states and 60 transitions. [2022-03-15 21:15:55,463 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 21:15:55,971 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 12 new interpolants: [3376#(or (< (+ 2 j) N) (<= (+ N 1) i) (<= N (+ j 1))), 3371#(or (<= N i) (< j N)), 3374#(or (<= N j) (<= (+ N 1) i) (< (+ j 1) N)), 3372#(or (<= N (+ i 1)) (< j N)), 3378#(or (< (+ 2 j) N) (<= N i) (<= N (+ j 1))), 3379#(or (<= N (+ i 1)) (<= N j) (< (+ j 1) N)), 3370#(or (<= (+ N 1) i) (< j N)), 3369#(< j N), 3377#(or (<= N j) (<= N i) (< (+ j 1) N)), 3380#(or (<= N (+ i 1)) (< (+ 2 j) N) (<= N (+ j 1))), 3373#(or (<= N j) (< (+ j 1) N)), 3375#(or (< (+ 2 j) N) (<= N (+ j 1)))] [2022-03-15 21:15:55,971 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2022-03-15 21:15:55,971 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 21:15:55,972 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2022-03-15 21:15:55,972 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=136, Invalid=620, Unknown=0, NotChecked=0, Total=756 [2022-03-15 21:15:55,972 INFO L87 Difference]: Start difference. First operand 153 states and 422 transitions. Second operand has 21 states, 21 states have (on average 2.2857142857142856) internal successors, (48), 20 states have internal predecessors, (48), 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:15:56,531 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 21:15:56,531 INFO L93 Difference]: Finished difference Result 294 states and 719 transitions. [2022-03-15 21:15:56,532 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 37 states. [2022-03-15 21:15:56,532 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 21 states have (on average 2.2857142857142856) internal successors, (48), 20 states have internal predecessors, (48), 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 14 [2022-03-15 21:15:56,532 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 21:15:56,533 INFO L225 Difference]: With dead ends: 294 [2022-03-15 21:15:56,533 INFO L226 Difference]: Without dead ends: 280 [2022-03-15 21:15:56,534 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 85 GetRequests, 30 SyntacticMatches, 1 SemanticMatches, 54 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 814 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=670, Invalid=2410, Unknown=0, NotChecked=0, Total=3080 [2022-03-15 21:15:56,534 INFO L933 BasicCegarLoop]: 1 mSDtfsCounter, 106 mSDsluCounter, 51 mSDsCounter, 0 mSdLazyCounter, 250 mSolverCounterSat, 68 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 106 SdHoareTripleChecker+Valid, 1 SdHoareTripleChecker+Invalid, 318 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 68 IncrementalHoareTripleChecker+Valid, 250 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-03-15 21:15:56,535 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [106 Valid, 1 Invalid, 318 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [68 Valid, 250 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-03-15 21:15:56,535 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 280 states. [2022-03-15 21:15:56,539 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 280 to 190. [2022-03-15 21:15:56,539 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 190 states, 189 states have (on average 2.746031746031746) internal successors, (519), 189 states have internal predecessors, (519), 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:15:56,540 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 190 states to 190 states and 519 transitions. [2022-03-15 21:15:56,540 INFO L78 Accepts]: Start accepts. Automaton has 190 states and 519 transitions. Word has length 14 [2022-03-15 21:15:56,540 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 21:15:56,540 INFO L470 AbstractCegarLoop]: Abstraction has 190 states and 519 transitions. [2022-03-15 21:15:56,540 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 21 states have (on average 2.2857142857142856) internal successors, (48), 20 states have internal predecessors, (48), 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:15:56,540 INFO L276 IsEmpty]: Start isEmpty. Operand 190 states and 519 transitions. [2022-03-15 21:15:56,541 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2022-03-15 21:15:56,541 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 21:15:56,541 INFO L514 BasicCegarLoop]: trace histogram [4, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 21:15:56,556 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 21:15:56,756 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,SelfDestructingSolverStorable11 [2022-03-15 21:15:56,756 INFO L402 AbstractCegarLoop]: === Iteration 13 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION] === [2022-03-15 21:15:56,757 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 21:15:56,757 INFO L85 PathProgramCache]: Analyzing trace with hash 1670541428, now seen corresponding path program 10 times [2022-03-15 21:15:56,757 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 21:15:56,758 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [397028270] [2022-03-15 21:15:56,758 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 21:15:56,758 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 21:15:56,763 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 21:15:56,812 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 10 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 21:15:56,813 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 21:15:56,813 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [397028270] [2022-03-15 21:15:56,813 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [397028270] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-15 21:15:56,813 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1933133857] [2022-03-15 21:15:56,813 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-03-15 21:15:56,813 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 21:15:56,813 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 21:15:56,814 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 21:15:56,815 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 21:15:56,836 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-03-15 21:15:56,836 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-15 21:15:56,836 INFO L263 TraceCheckSpWp]: Trace formula consists of 48 conjuncts, 10 conjunts are in the unsatisfiable core [2022-03-15 21:15:56,837 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-15 21:15:57,129 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 10 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 21:15:57,129 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-15 21:15:57,254 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 62 treesize of output 54 [2022-03-15 21:15:57,274 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 10 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 21:15:57,274 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1933133857] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-15 21:15:57,274 INFO L191 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-03-15 21:15:57,274 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9] total 17 [2022-03-15 21:15:57,274 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [1405256158] [2022-03-15 21:15:57,274 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 21:15:57,275 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 21:15:57,279 INFO L252 McrAutomatonBuilder]: Finished intersection with 45 states and 73 transitions. [2022-03-15 21:15:57,279 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 21:15:58,154 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 20 new interpolants: [4224#(or (<= N (+ i 1)) (< (+ 2 i) N) (<= N (+ j 1))), 4205#(or (<= N (+ i 1)) (< (+ 2 i) N) (<= N (+ 3 j))), 4225#(or (<= N (+ i 1)) (<= N (+ 2 j)) (< (+ 2 i) N)), 4229#(or (<= N (+ 2 i)) (< (+ 3 i) N) (<= N (+ 3 j))), 4218#(or (<= N (+ j 1)) (< i N)), 4213#(< i N), 4223#(or (<= N (+ i 1)) (<= N j) (< (+ 2 i) N)), 4197#(or (< i N) (<= N (+ 3 j))), 4214#(or (<= N i) (< (+ i 1) N)), 4221#(or (<= N (+ 2 j)) (< i N)), 4227#(or (<= N (+ 2 i)) (< (+ 3 i) N) (<= N (+ j 1))), 4220#(or (<= N i) (< (+ i 1) N) (<= N (+ j 1))), 4217#(or (<= N j) (< i N)), 4201#(or (<= N i) (< (+ i 1) N) (<= N (+ 3 j))), 4216#(or (<= N (+ 2 i)) (< (+ 3 i) N)), 4228#(or (<= N (+ 2 j)) (<= N (+ 2 i)) (< (+ 3 i) N)), 4222#(or (<= N (+ 2 j)) (<= N i) (< (+ i 1) N)), 4226#(or (<= N j) (<= N (+ 2 i)) (< (+ 3 i) N)), 4219#(or (<= N j) (<= N i) (< (+ i 1) N)), 4215#(or (<= N (+ i 1)) (< (+ 2 i) N))] [2022-03-15 21:15:58,154 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 30 states [2022-03-15 21:15:58,154 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 21:15:58,154 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2022-03-15 21:15:58,154 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=226, Invalid=964, Unknown=0, NotChecked=0, Total=1190 [2022-03-15 21:15:58,155 INFO L87 Difference]: Start difference. First operand 190 states and 519 transitions. Second operand has 30 states, 30 states have (on average 2.1) internal successors, (63), 29 states have internal predecessors, (63), 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:16:00,324 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 21:16:00,325 INFO L93 Difference]: Finished difference Result 572 states and 1483 transitions. [2022-03-15 21:16:00,325 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 103 states. [2022-03-15 21:16:00,325 INFO L78 Accepts]: Start accepts. Automaton has has 30 states, 30 states have (on average 2.1) internal successors, (63), 29 states have internal predecessors, (63), 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 15 [2022-03-15 21:16:00,325 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 21:16:00,327 INFO L225 Difference]: With dead ends: 572 [2022-03-15 21:16:00,327 INFO L226 Difference]: Without dead ends: 547 [2022-03-15 21:16:00,329 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 157 GetRequests, 33 SyntacticMatches, 0 SemanticMatches, 124 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5725 ImplicationChecksByTransitivity, 2.1s TimeCoverageRelationStatistics Valid=4318, Invalid=11432, Unknown=0, NotChecked=0, Total=15750 [2022-03-15 21:16:00,330 INFO L933 BasicCegarLoop]: 1 mSDtfsCounter, 123 mSDsluCounter, 72 mSDsCounter, 0 mSdLazyCounter, 442 mSolverCounterSat, 96 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 123 SdHoareTripleChecker+Valid, 1 SdHoareTripleChecker+Invalid, 538 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 96 IncrementalHoareTripleChecker+Valid, 442 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-03-15 21:16:00,330 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [123 Valid, 1 Invalid, 538 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [96 Valid, 442 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-03-15 21:16:00,330 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 547 states. [2022-03-15 21:16:00,337 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 547 to 292. [2022-03-15 21:16:00,338 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 292 states, 291 states have (on average 2.9553264604811) internal successors, (860), 291 states have internal predecessors, (860), 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:16:00,339 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 292 states to 292 states and 860 transitions. [2022-03-15 21:16:00,339 INFO L78 Accepts]: Start accepts. Automaton has 292 states and 860 transitions. Word has length 15 [2022-03-15 21:16:00,339 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 21:16:00,339 INFO L470 AbstractCegarLoop]: Abstraction has 292 states and 860 transitions. [2022-03-15 21:16:00,339 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 30 states, 30 states have (on average 2.1) internal successors, (63), 29 states have internal predecessors, (63), 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:16:00,339 INFO L276 IsEmpty]: Start isEmpty. Operand 292 states and 860 transitions. [2022-03-15 21:16:00,340 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2022-03-15 21:16:00,340 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 21:16:00,340 INFO L514 BasicCegarLoop]: trace histogram [4, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 21:16:00,356 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2022-03-15 21:16:00,555 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,SelfDestructingSolverStorable12 [2022-03-15 21:16:00,558 INFO L402 AbstractCegarLoop]: === Iteration 14 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION] === [2022-03-15 21:16:00,558 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 21:16:00,558 INFO L85 PathProgramCache]: Analyzing trace with hash -883500020, now seen corresponding path program 11 times [2022-03-15 21:16:00,559 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 21:16:00,559 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1721645818] [2022-03-15 21:16:00,559 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 21:16:00,559 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 21:16:00,564 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 21:16:00,624 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 3 proven. 13 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 21:16:00,624 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 21:16:00,624 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1721645818] [2022-03-15 21:16:00,624 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1721645818] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-15 21:16:00,624 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [205518245] [2022-03-15 21:16:00,624 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2022-03-15 21:16:00,624 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 21:16:00,624 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 21:16:00,626 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 21:16:00,627 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 21:16:00,648 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 3 check-sat command(s) [2022-03-15 21:16:00,648 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-15 21:16:00,649 INFO L263 TraceCheckSpWp]: Trace formula consists of 46 conjuncts, 10 conjunts are in the unsatisfiable core [2022-03-15 21:16:00,650 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-15 21:16:01,138 INFO L353 Elim1Store]: treesize reduction 66, result has 1.5 percent of original size [2022-03-15 21:16:01,138 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 468 treesize of output 272 [2022-03-15 21:16:01,180 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 0 proven. 16 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 21:16:01,180 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-15 21:16:01,295 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 62 treesize of output 54 [2022-03-15 21:16:01,310 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 6 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 21:16:01,310 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [205518245] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-15 21:16:01,310 INFO L191 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-03-15 21:16:01,310 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9] total 17 [2022-03-15 21:16:01,311 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [1906481156] [2022-03-15 21:16:01,311 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 21:16:01,311 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 21:16:01,315 INFO L252 McrAutomatonBuilder]: Finished intersection with 45 states and 73 transitions. [2022-03-15 21:16:01,315 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 21:16:02,557 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 25 new interpolants: [5686#(or (<= N (+ 2 i)) (< (+ 3 i) N) (< j N)), 5693#(or (< (+ i 4) N) (<= N (+ 3 i)) (<= (+ 3 j) N)), 5672#(or (<= (+ 2 j) N) (< i N)), 5683#(or (<= N i) (< (+ i 1) N) (<= (+ j 4) N)), 5685#(or (<= N (+ 2 i)) (< (+ 3 i) N)), 5682#(or (<= (+ j 4) N) (< i N)), 5681#(or (<= N (+ i 1)) (< (+ 2 i) N) (<= (+ 3 j) N)), 5677#(or (<= N i) (< (+ i 1) N) (<= (+ 3 j) N)), 5688#(or (<= N (+ 2 i)) (< (+ 3 i) N) (<= (+ 3 j) N)), 5689#(or (<= N (+ 2 i)) (<= (+ j 4) N) (< (+ 3 i) N)), 5678#(or (<= N (+ i 1)) (< (+ 2 i) N)), 5690#(or (< (+ i 4) N) (<= N (+ 3 i))), 5694#(or (< (+ i 4) N) (<= (+ j 4) N) (<= N (+ 3 i))), 5676#(or (<= N i) (< (+ i 1) N) (<= (+ 2 j) N)), 5674#(or (<= N i) (< (+ i 1) N)), 5684#(or (<= N (+ i 1)) (< (+ 2 i) N) (<= (+ j 4) N)), 5670#(< i N), 5675#(or (<= N i) (< (+ i 1) N) (< j N)), 5691#(or (< (+ i 4) N) (<= N (+ 3 i)) (< j N)), 5680#(or (<= N (+ i 1)) (< (+ 2 i) N) (<= (+ 2 j) N)), 5687#(or (<= N (+ 2 i)) (<= (+ 2 j) N) (< (+ 3 i) N)), 5673#(or (<= (+ 3 j) N) (< i N)), 5671#(or (<= (+ j 1) N) (< i N)), 5679#(or (<= N (+ i 1)) (< (+ 2 i) N) (< j N)), 5692#(or (< (+ i 4) N) (<= N (+ 3 i)) (<= (+ 2 j) N))] [2022-03-15 21:16:02,558 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 35 states [2022-03-15 21:16:02,558 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 21:16:02,558 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 35 interpolants. [2022-03-15 21:16:02,558 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=391, Invalid=1415, Unknown=0, NotChecked=0, Total=1806 [2022-03-15 21:16:02,559 INFO L87 Difference]: Start difference. First operand 292 states and 860 transitions. Second operand has 35 states, 35 states have (on average 1.9714285714285715) internal successors, (69), 34 states have internal predecessors, (69), 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:16:03,591 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 21:16:03,591 INFO L93 Difference]: Finished difference Result 544 states and 1509 transitions. [2022-03-15 21:16:03,592 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 60 states. [2022-03-15 21:16:03,592 INFO L78 Accepts]: Start accepts. Automaton has has 35 states, 35 states have (on average 1.9714285714285715) internal successors, (69), 34 states have internal predecessors, (69), 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 15 [2022-03-15 21:16:03,592 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 21:16:03,594 INFO L225 Difference]: With dead ends: 544 [2022-03-15 21:16:03,594 INFO L226 Difference]: Without dead ends: 539 [2022-03-15 21:16:03,596 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 109 GetRequests, 22 SyntacticMatches, 3 SemanticMatches, 84 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2100 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=1626, Invalid=5684, Unknown=0, NotChecked=0, Total=7310 [2022-03-15 21:16:03,596 INFO L933 BasicCegarLoop]: 1 mSDtfsCounter, 130 mSDsluCounter, 82 mSDsCounter, 0 mSdLazyCounter, 548 mSolverCounterSat, 150 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 130 SdHoareTripleChecker+Valid, 1 SdHoareTripleChecker+Invalid, 698 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 150 IncrementalHoareTripleChecker+Valid, 548 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-03-15 21:16:03,596 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [130 Valid, 1 Invalid, 698 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [150 Valid, 548 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-03-15 21:16:03,597 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 539 states. [2022-03-15 21:16:03,604 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 539 to 356. [2022-03-15 21:16:03,605 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 356 states, 355 states have (on average 2.9126760563380283) internal successors, (1034), 355 states have internal predecessors, (1034), 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:16:03,606 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 356 states to 356 states and 1034 transitions. [2022-03-15 21:16:03,606 INFO L78 Accepts]: Start accepts. Automaton has 356 states and 1034 transitions. Word has length 15 [2022-03-15 21:16:03,606 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 21:16:03,606 INFO L470 AbstractCegarLoop]: Abstraction has 356 states and 1034 transitions. [2022-03-15 21:16:03,607 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 35 states, 35 states have (on average 1.9714285714285715) internal successors, (69), 34 states have internal predecessors, (69), 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:16:03,607 INFO L276 IsEmpty]: Start isEmpty. Operand 356 states and 1034 transitions. [2022-03-15 21:16:03,607 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2022-03-15 21:16:03,607 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 21:16:03,607 INFO L514 BasicCegarLoop]: trace histogram [4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 21:16:03,626 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 21:16:03,811 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,SelfDestructingSolverStorable13 [2022-03-15 21:16:03,811 INFO L402 AbstractCegarLoop]: === Iteration 15 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION] === [2022-03-15 21:16:03,812 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 21:16:03,812 INFO L85 PathProgramCache]: Analyzing trace with hash -1618591097, now seen corresponding path program 12 times [2022-03-15 21:16:03,812 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 21:16:03,812 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [775688070] [2022-03-15 21:16:03,812 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 21:16:03,812 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 21:16:03,923 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 21:27:53,955 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 0 proven. 20 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 21:27:53,956 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 21:27:53,956 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [775688070] [2022-03-15 21:27:53,956 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [775688070] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-15 21:27:53,956 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1145469238] [2022-03-15 21:27:53,956 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-03-15 21:27:53,956 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 21:27:53,956 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 21:27:53,957 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 21:27:53,958 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 21:27:54,016 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 3 check-sat command(s) [2022-03-15 21:27:54,017 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-15 21:27:54,017 WARN L261 TraceCheckSpWp]: Trace formula consists of 49 conjuncts, 34 conjunts are in the unsatisfiable core [2022-03-15 21:27:54,018 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-15 21:27:54,930 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 4 select indices, 4 select index equivalence classes, 6 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 187 treesize of output 127 [2022-03-15 21:27:55,020 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 0 proven. 20 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 21:27:55,020 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-15 21:27:55,657 INFO L173 IndexEqualityManager]: detected equality via solver [2022-03-15 21:27:55,657 INFO L173 IndexEqualityManager]: detected equality via solver [2022-03-15 21:27:55,657 INFO L173 IndexEqualityManager]: detected equality via solver [2022-03-15 21:27:55,658 INFO L173 IndexEqualityManager]: detected equality via solver [2022-03-15 21:27:55,658 INFO L173 IndexEqualityManager]: detected equality via solver [2022-03-15 21:27:55,658 INFO L173 IndexEqualityManager]: detected equality via solver [2022-03-15 21:27:55,659 INFO L173 IndexEqualityManager]: detected equality via solver [2022-03-15 21:27:55,659 INFO L173 IndexEqualityManager]: detected equality via solver [2022-03-15 21:27:55,659 INFO L173 IndexEqualityManager]: detected equality via solver [2022-03-15 21:27:55,660 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-03-15 21:27:55,660 INFO L173 IndexEqualityManager]: detected equality via solver [2022-03-15 21:27:55,661 INFO L173 IndexEqualityManager]: detected equality via solver [2022-03-15 21:27:55,661 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-03-15 21:27:55,662 INFO L173 IndexEqualityManager]: detected equality via solver [2022-03-15 21:27:55,663 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-03-15 21:27:55,671 INFO L353 Elim1Store]: treesize reduction 33, result has 10.8 percent of original size [2022-03-15 21:27:55,671 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 8 select indices, 8 select index equivalence classes, 6 disjoint index pairs (out of 28 index pairs), introduced 5 new quantified variables, introduced 7 case distinctions, treesize of input 141 treesize of output 77 [2022-03-15 21:27:55,761 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 0 proven. 20 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 21:27:55,761 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1145469238] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-15 21:27:55,761 INFO L191 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-03-15 21:27:55,761 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11, 11] total 30 [2022-03-15 21:27:55,762 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [417113937] [2022-03-15 21:27:55,762 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 21:27:55,763 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 21:27:55,768 INFO L252 McrAutomatonBuilder]: Finished intersection with 52 states and 86 transitions. [2022-03-15 21:27:55,768 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 21:27:58,297 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 29 new interpolants: [7180#(and (<= (+ bag2 sum2) (+ (select A i) (select A (+ 2 i)) bag1 sum1 (select A (+ 3 i)) (select A (+ i 1)))) (<= (+ (select A i) (select A (+ 2 i)) bag1 sum1 (select A (+ 3 i)) (select A (+ i 1))) (+ bag2 sum2))), 7159#(and (<= (+ bag1 sum1) sum2) (< sum2 (+ bag1 sum1 1))), 7176#(and (< sum2 (+ (select A i) (select A (+ 2 i)) bag1 sum1 (select A (+ i 1)) 1)) (<= (+ (select A i) (select A (+ 2 i)) bag1 sum1 (select A (+ i 1))) sum2)), 7164#(and (<= (+ bag2 sum2) (+ (select A i) bag1 sum1 (select A (+ i 1)))) (<= (+ (select A i) bag1 sum1 (select A (+ i 1))) (+ bag2 sum2))), 7168#(and (<= (+ bag1 sum1) (+ (select A j) (select A (+ j 1)) bag2 sum2)) (<= (+ (select A j) (select A (+ j 1)) bag2 sum2) (+ bag1 sum1))), 7162#(and (<= (+ bag2 sum2) (+ (select A i) bag1 sum1)) (<= (+ (select A i) bag1 sum1) (+ bag2 sum2))), 7187#(and (<= (+ (select A j) (select A (+ 3 j)) (select A (+ 2 j)) (select A (+ j 1)) bag2 sum2) (+ (select A i) (select A (+ 2 i)) bag1 sum1 (select A (+ 3 i)) (select A (+ i 1)))) (= bag2 0) (<= (+ (select A i) (select A (+ 2 i)) bag1 sum1 (select A (+ 3 i)) (select A (+ i 1))) (+ (* 2 bag2) (select A j) (select A 3) (select A 1) (select A 2))) (= j 0) (<= (+ (select A i) (select A (+ 2 i)) bag1 sum1 (select A (+ 3 i)) (select A (+ i 1))) (+ (select A j) (select A (+ 3 j)) (select A (+ 2 j)) (select A (+ j 1)) bag2 sum2)) (<= (+ (* 2 bag2) (select A j) (select A 3) (select A 1) (select A 2)) (+ (select A i) (select A (+ 2 i)) bag1 sum1 (select A (+ 3 i)) (select A (+ i 1))))), 7167#(and (<= (+ (select A i) bag1 sum1 (select A (+ i 1))) (+ (select A j) bag2 sum2)) (<= (+ (select A j) bag2 sum2) (+ (select A i) bag1 sum1 (select A (+ i 1))))), 7175#(and (<= (+ (select A i) bag1 sum1 (select A (+ i 1))) (+ (* 2 bag2) (select A j) (select A 3) (select A 1) (select A 2))) (= bag2 0) (<= (+ (* 2 bag2) (select A j) (select A 3) (select A 1) (select A 2)) (+ (select A i) bag1 sum1 (select A (+ i 1)))) (<= (+ (select A j) (select A (+ 3 j)) (select A (+ 2 j)) (select A (+ j 1)) bag2 sum2) (+ (select A i) bag1 sum1 (select A (+ i 1)))) (= j 0) (<= (+ (select A i) bag1 sum1 (select A (+ i 1))) (+ (select A j) (select A (+ 3 j)) (select A (+ 2 j)) (select A (+ j 1)) bag2 sum2))), 7160#(and (<= (+ bag1 sum1) (+ bag2 sum2)) (<= (+ bag2 sum2) (+ bag1 sum1))), 7185#(and (<= (+ (select A j) (select A (+ 2 j)) (select A (+ j 1)) bag2 sum2) (+ (select A i) (select A (+ 2 i)) bag1 sum1 (select A (+ 3 i)) (select A (+ i 1)))) (<= (+ (select A i) (select A (+ 2 i)) bag1 sum1 (select A (+ 3 i)) (select A (+ i 1))) (+ (select A j) (select A (+ 2 j)) (select A (+ j 1)) bag2 sum2))), 7183#(and (<= (+ (select A j) (select A (+ j 1)) bag2 sum2) (+ (select A i) (select A (+ 2 i)) bag1 sum1 (select A (+ 3 i)) (select A (+ i 1)))) (<= (+ (select A i) (select A (+ 2 i)) bag1 sum1 (select A (+ 3 i)) (select A (+ i 1))) (+ (select A j) (select A (+ j 1)) bag2 sum2))), 7171#(and (<= (+ (select A i) bag1 sum1) (+ (select A j) (select A (+ 2 j)) (select A (+ j 1)) bag2 sum2)) (<= (+ (select A j) (select A (+ 2 j)) (select A (+ j 1)) bag2 sum2) (+ (select A i) bag1 sum1))), 7172#(and (<= (+ (select A j) (select A (+ j 1)) bag2 sum2) (+ (select A i) bag1 sum1 (select A (+ i 1)))) (<= (+ (select A i) bag1 sum1 (select A (+ i 1))) (+ (select A j) (select A (+ j 1)) bag2 sum2))), 7177#(and (<= (+ (select A i) (select A (+ 2 i)) bag1 sum1 (select A (+ i 1))) (+ bag2 sum2)) (<= (+ bag2 sum2) (+ (select A i) (select A (+ 2 i)) bag1 sum1 (select A (+ i 1))))), 7166#(and (<= (+ (select A j) bag2 sum2) (+ (select A i) bag1 sum1)) (<= (+ (select A i) bag1 sum1) (+ (select A j) bag2 sum2))), 7161#(and (< sum2 (+ (select A i) bag1 sum1 1)) (<= (+ (select A i) bag1 sum1) sum2)), 7179#(and (< sum2 (+ (select A i) (select A (+ 2 i)) bag1 sum1 (select A (+ 3 i)) (select A (+ i 1)) 1)) (<= (+ (select A i) (select A (+ 2 i)) bag1 sum1 (select A (+ 3 i)) (select A (+ i 1))) sum2)), 7178#(and (<= (+ (select A i) (select A (+ 2 i)) bag1 sum1 (select A (+ i 1))) (+ (select A j) bag2 sum2)) (<= (+ (select A j) bag2 sum2) (+ (select A i) (select A (+ 2 i)) bag1 sum1 (select A (+ i 1))))), 7182#(and (<= (+ (select A i) (select A (+ 2 i)) bag1 sum1 (select A (+ i 1))) (+ (select A j) (select A (+ j 1)) bag2 sum2)) (<= (+ (select A j) (select A (+ j 1)) bag2 sum2) (+ (select A i) (select A (+ 2 i)) bag1 sum1 (select A (+ i 1))))), 7165#(and (<= (+ bag1 sum1) (+ (select A j) bag2 sum2)) (<= (+ (select A j) bag2 sum2) (+ bag1 sum1))), 7169#(and (<= (+ bag1 sum1) (+ (select A j) (select A (+ 2 j)) (select A (+ j 1)) bag2 sum2)) (<= (+ (select A j) (select A (+ 2 j)) (select A (+ j 1)) bag2 sum2) (+ bag1 sum1))), 7174#(and (= bag2 0) (<= (+ (select A j) (select A (+ 3 j)) (select A (+ 2 j)) (select A (+ j 1)) bag2 sum2) (+ (select A i) bag1 sum1)) (<= (+ (* 2 bag2) (select A j) (select A 3) (select A 1) (select A 2)) (+ (select A i) bag1 sum1)) (<= (+ (select A i) bag1 sum1) (+ (* 2 bag2) (select A j) (select A 3) (select A 1) (select A 2))) (= j 0) (<= (+ (select A i) bag1 sum1) (+ (select A j) (select A (+ 3 j)) (select A (+ 2 j)) (select A (+ j 1)) bag2 sum2))), 7163#(and (< sum2 (+ (select A i) bag1 sum1 (select A (+ i 1)) 1)) (<= (+ (select A i) bag1 sum1 (select A (+ i 1))) sum2)), 7181#(and (<= (+ (select A j) bag2 sum2) (+ (select A i) (select A (+ 2 i)) bag1 sum1 (select A (+ 3 i)) (select A (+ i 1)))) (<= (+ (select A i) (select A (+ 2 i)) bag1 sum1 (select A (+ 3 i)) (select A (+ i 1))) (+ (select A j) bag2 sum2))), 7173#(and (<= (+ (select A i) bag1 sum1 (select A (+ i 1))) (+ (select A j) (select A (+ 2 j)) (select A (+ j 1)) bag2 sum2)) (<= (+ (select A j) (select A (+ 2 j)) (select A (+ j 1)) bag2 sum2) (+ (select A i) bag1 sum1 (select A (+ i 1))))), 7186#(and (<= (+ (select A i) (select A (+ 2 i)) bag1 sum1 (select A (+ i 1))) (+ (select A j) (select A (+ 3 j)) (select A (+ 2 j)) (select A (+ j 1)) bag2 sum2)) (= bag2 0) (<= (+ (* 2 bag2) (select A j) (select A 3) (select A 1) (select A 2)) (+ (select A i) (select A (+ 2 i)) bag1 sum1 (select A (+ i 1)))) (<= (+ (select A j) (select A (+ 3 j)) (select A (+ 2 j)) (select A (+ j 1)) bag2 sum2) (+ (select A i) (select A (+ 2 i)) bag1 sum1 (select A (+ i 1)))) (= j 0) (<= (+ (select A i) (select A (+ 2 i)) bag1 sum1 (select A (+ i 1))) (+ (* 2 bag2) (select A j) (select A 3) (select A 1) (select A 2)))), 7184#(and (<= (+ (select A i) (select A (+ 2 i)) bag1 sum1 (select A (+ i 1))) (+ (select A j) (select A (+ 2 j)) (select A (+ j 1)) bag2 sum2)) (<= (+ (select A j) (select A (+ 2 j)) (select A (+ j 1)) bag2 sum2) (+ (select A i) (select A (+ 2 i)) bag1 sum1 (select A (+ i 1))))), 7170#(and (<= (+ (select A j) (select A (+ j 1)) bag2 sum2) (+ (select A i) bag1 sum1)) (<= (+ (select A i) bag1 sum1) (+ (select A j) (select A (+ j 1)) bag2 sum2)))] [2022-03-15 21:27:58,297 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 42 states [2022-03-15 21:27:58,297 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 21:27:58,298 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 42 interpolants. [2022-03-15 21:27:58,299 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=263, Invalid=3397, Unknown=0, NotChecked=0, Total=3660 [2022-03-15 21:27:58,299 INFO L87 Difference]: Start difference. First operand 356 states and 1034 transitions. Second operand has 42 states, 41 states have (on average 1.951219512195122) internal successors, (80), 41 states have internal predecessors, (80), 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:27:59,614 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 21:27:59,614 INFO L93 Difference]: Finished difference Result 511 states and 1446 transitions. [2022-03-15 21:27:59,615 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 38 states. [2022-03-15 21:27:59,615 INFO L78 Accepts]: Start accepts. Automaton has has 42 states, 41 states have (on average 1.951219512195122) internal successors, (80), 41 states have internal predecessors, (80), 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 16 [2022-03-15 21:27:59,615 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 21:27:59,617 INFO L225 Difference]: With dead ends: 511 [2022-03-15 21:27:59,617 INFO L226 Difference]: Without dead ends: 497 [2022-03-15 21:27:59,618 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 88 GetRequests, 13 SyntacticMatches, 4 SemanticMatches, 71 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1579 ImplicationChecksByTransitivity, 2.3s TimeCoverageRelationStatistics Valid=345, Invalid=4911, Unknown=0, NotChecked=0, Total=5256 [2022-03-15 21:27:59,619 INFO L933 BasicCegarLoop]: 1 mSDtfsCounter, 24 mSDsluCounter, 469 mSDsCounter, 0 mSdLazyCounter, 1966 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 1 SdHoareTripleChecker+Invalid, 1980 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 1966 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2022-03-15 21:27:59,619 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [24 Valid, 1 Invalid, 1980 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 1966 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2022-03-15 21:27:59,619 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 497 states. [2022-03-15 21:27:59,625 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 497 to 384. [2022-03-15 21:27:59,626 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 384 states, 383 states have (on average 2.9007832898172325) internal successors, (1111), 383 states have internal predecessors, (1111), 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:27:59,627 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 384 states to 384 states and 1111 transitions. [2022-03-15 21:27:59,627 INFO L78 Accepts]: Start accepts. Automaton has 384 states and 1111 transitions. Word has length 16 [2022-03-15 21:27:59,627 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 21:27:59,629 INFO L470 AbstractCegarLoop]: Abstraction has 384 states and 1111 transitions. [2022-03-15 21:27:59,629 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 42 states, 41 states have (on average 1.951219512195122) internal successors, (80), 41 states have internal predecessors, (80), 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:27:59,629 INFO L276 IsEmpty]: Start isEmpty. Operand 384 states and 1111 transitions. [2022-03-15 21:27:59,630 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2022-03-15 21:27:59,630 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 21:27:59,630 INFO L514 BasicCegarLoop]: trace histogram [5, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 21:27:59,648 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2022-03-15 21:27:59,846 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,SelfDestructingSolverStorable14 [2022-03-15 21:27:59,846 INFO L402 AbstractCegarLoop]: === Iteration 16 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION] === [2022-03-15 21:27:59,846 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 21:27:59,846 INFO L85 PathProgramCache]: Analyzing trace with hash -104349359, now seen corresponding path program 13 times [2022-03-15 21:27:59,847 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 21:27:59,847 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [978036361] [2022-03-15 21:27:59,847 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 21:27:59,847 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 21:27:59,852 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 21:27:59,909 INFO L134 CoverageAnalysis]: Checked inductivity of 21 backedges. 15 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 21:27:59,909 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 21:27:59,909 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [978036361] [2022-03-15 21:27:59,909 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [978036361] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-15 21:27:59,909 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [531372047] [2022-03-15 21:27:59,909 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2022-03-15 21:27:59,909 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 21:27:59,909 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 21:27:59,910 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:27:59,937 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 21:27:59,937 INFO L263 TraceCheckSpWp]: Trace formula consists of 47 conjuncts, 11 conjunts are in the unsatisfiable core [2022-03-15 21:27:59,939 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:27:59,939 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-15 21:28:00,467 INFO L134 CoverageAnalysis]: Checked inductivity of 21 backedges. 8 proven. 12 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2022-03-15 21:28:00,468 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-15 21:28:00,570 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 62 treesize of output 54 [2022-03-15 21:28:00,598 INFO L134 CoverageAnalysis]: Checked inductivity of 21 backedges. 15 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 21:28:00,598 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [531372047] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-15 21:28:00,598 INFO L191 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-03-15 21:28:00,598 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 9, 10] total 20 [2022-03-15 21:28:00,598 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [15522780] [2022-03-15 21:28:00,599 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 21:28:00,600 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 21:28:00,605 INFO L252 McrAutomatonBuilder]: Finished intersection with 51 states and 84 transitions. [2022-03-15 21:28:00,605 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 21:28:01,570 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 20 new interpolants: [8613#(or (<= N (+ 2 j)) (<= N i) (< (+ 3 j) N)), 8612#(or (< (+ 2 j) N) (<= N i) (<= N (+ j 1))), 8605#(or (<= N (+ 2 j)) (< (+ 3 j) N)), 8615#(or (<= N (+ i 1)) (<= N j) (< (+ j 1) N)), 8603#(or (<= N j) (< (+ j 1) N)), 8610#(or (<= N i) (< j N)), 8614#(or (<= N (+ i 1)) (< j N)), 8618#(or (<= N (+ 2 i)) (< j N)), 8602#(< j N), 8620#(or (< (+ 2 j) N) (<= N (+ 2 i)) (<= N (+ j 1))), 8606#(or (<= (+ N 1) i) (< j N)), 8608#(or (< (+ 2 j) N) (<= (+ N 1) i) (<= N (+ j 1))), 8616#(or (<= N (+ i 1)) (< (+ 2 j) N) (<= N (+ j 1))), 8611#(or (<= N j) (<= N i) (< (+ j 1) N)), 8609#(or (<= N (+ 2 j)) (<= (+ N 1) i) (< (+ 3 j) N)), 8607#(or (<= N j) (<= (+ N 1) i) (< (+ j 1) N)), 8604#(or (< (+ 2 j) N) (<= N (+ j 1))), 8617#(or (<= N (+ i 1)) (<= N (+ 2 j)) (< (+ 3 j) N)), 8619#(or (<= N j) (<= N (+ 2 i)) (< (+ j 1) N)), 8621#(or (<= N (+ 2 j)) (<= N (+ 2 i)) (< (+ 3 j) N))] [2022-03-15 21:28:01,570 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 31 states [2022-03-15 21:28:01,570 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 21:28:01,571 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2022-03-15 21:28:01,571 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=261, Invalid=1379, Unknown=0, NotChecked=0, Total=1640 [2022-03-15 21:28:01,571 INFO L87 Difference]: Start difference. First operand 384 states and 1111 transitions. Second operand has 31 states, 31 states have (on average 2.225806451612903) internal successors, (69), 30 states have internal predecessors, (69), 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:28:02,989 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 21:28:02,989 INFO L93 Difference]: Finished difference Result 807 states and 2132 transitions. [2022-03-15 21:28:02,989 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 71 states. [2022-03-15 21:28:02,990 INFO L78 Accepts]: Start accepts. Automaton has has 31 states, 31 states have (on average 2.225806451612903) internal successors, (69), 30 states have internal predecessors, (69), 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 16 [2022-03-15 21:28:02,990 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 21:28:02,996 INFO L225 Difference]: With dead ends: 807 [2022-03-15 21:28:02,996 INFO L226 Difference]: Without dead ends: 773 [2022-03-15 21:28:02,998 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 134 GetRequests, 34 SyntacticMatches, 1 SemanticMatches, 99 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2948 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=2269, Invalid=7831, Unknown=0, NotChecked=0, Total=10100 [2022-03-15 21:28:02,999 INFO L933 BasicCegarLoop]: 1 mSDtfsCounter, 164 mSDsluCounter, 78 mSDsCounter, 0 mSdLazyCounter, 440 mSolverCounterSat, 90 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 164 SdHoareTripleChecker+Valid, 1 SdHoareTripleChecker+Invalid, 530 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 90 IncrementalHoareTripleChecker+Valid, 440 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-03-15 21:28:02,999 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [164 Valid, 1 Invalid, 530 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [90 Valid, 440 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-03-15 21:28:03,001 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 773 states. [2022-03-15 21:28:03,010 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 773 to 500. [2022-03-15 21:28:03,010 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 500 states, 499 states have (on average 2.8957915831663326) internal successors, (1445), 499 states have internal predecessors, (1445), 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:28:03,012 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 500 states to 500 states and 1445 transitions. [2022-03-15 21:28:03,012 INFO L78 Accepts]: Start accepts. Automaton has 500 states and 1445 transitions. Word has length 16 [2022-03-15 21:28:03,012 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 21:28:03,012 INFO L470 AbstractCegarLoop]: Abstraction has 500 states and 1445 transitions. [2022-03-15 21:28:03,012 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 31 states, 31 states have (on average 2.225806451612903) internal successors, (69), 30 states have internal predecessors, (69), 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:28:03,012 INFO L276 IsEmpty]: Start isEmpty. Operand 500 states and 1445 transitions. [2022-03-15 21:28:03,013 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2022-03-15 21:28:03,013 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 21:28:03,013 INFO L514 BasicCegarLoop]: trace histogram [5, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 21:28:03,028 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Ended with exit code 0 [2022-03-15 21:28:03,228 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable15,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 21:28:03,228 INFO L402 AbstractCegarLoop]: === Iteration 17 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION] === [2022-03-15 21:28:03,229 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 21:28:03,229 INFO L85 PathProgramCache]: Analyzing trace with hash 1363389292, now seen corresponding path program 14 times [2022-03-15 21:28:03,229 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 21:28:03,229 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1724088887] [2022-03-15 21:28:03,229 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 21:28:03,230 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 21:28:03,241 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 21:28:03,324 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 15 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 21:28:03,325 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 21:28:03,325 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1724088887] [2022-03-15 21:28:03,325 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1724088887] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-15 21:28:03,325 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1854659130] [2022-03-15 21:28:03,325 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-15 21:28:03,325 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 21:28:03,325 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 21:28:03,340 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:28:03,341 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:28:03,362 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-15 21:28:03,363 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-15 21:28:03,363 INFO L263 TraceCheckSpWp]: Trace formula consists of 52 conjuncts, 12 conjunts are in the unsatisfiable core [2022-03-15 21:28:03,364 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-15 21:28:03,977 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 15 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 21:28:03,977 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-15 21:28:04,198 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 62 treesize of output 54 [2022-03-15 21:28:04,226 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 15 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 21:28:04,226 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1854659130] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-15 21:28:04,226 INFO L191 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-03-15 21:28:04,227 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11, 11] total 21 [2022-03-15 21:28:04,227 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [1800730230] [2022-03-15 21:28:04,227 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 21:28:04,228 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 21:28:04,246 INFO L252 McrAutomatonBuilder]: Finished intersection with 59 states and 99 transitions. [2022-03-15 21:28:04,246 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 21:28:05,533 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 30 new interpolants: [10670#(or (<= N j) (< i N)), 10672#(or (<= N (+ i 1)) (<= N j) (< (+ 2 i) N)), 10687#(or (< i N) (<= N (+ 3 j))), 10682#(or (<= N (+ 2 j)) (< i N)), 10685#(or (<= N (+ 2 j)) (<= N (+ 2 i)) (< (+ 3 i) N)), 10647#(or (<= N (+ j 4)) (< i N)), 10674#(or (<= N j) (<= N (+ 2 i)) (< (+ 3 i) N)), 10651#(or (<= N i) (< (+ i 1) N) (<= N (+ j 4))), 10679#(or (< (+ i 4) N) (<= N (+ 3 i))), 10690#(or (<= N (+ 2 i)) (< (+ 3 i) N) (<= N (+ 3 j))), 10667#(< i N), 10691#(or (< (+ i 4) N) (<= N (+ 3 i)) (<= N (+ 3 j))), 10677#(or (<= N (+ i 1)) (< (+ 2 i) N) (<= N (+ j 1))), 10686#(or (<= N (+ 2 j)) (< (+ i 4) N) (<= N (+ 3 i))), 10683#(or (<= N (+ 2 j)) (<= N i) (< (+ i 1) N)), 10676#(or (<= N i) (< (+ i 1) N) (<= N (+ j 1))), 10675#(or (<= N (+ j 1)) (< i N)), 10681#(or (< (+ i 4) N) (<= N (+ 3 i)) (<= N (+ j 1))), 10678#(or (<= N (+ 2 i)) (< (+ 3 i) N) (<= N (+ j 1))), 10659#(or (<= N (+ 2 i)) (< (+ 3 i) N) (<= N (+ j 4))), 10692#(or (< (+ i 4) N) (<= N (+ 3 i)) (<= N (+ j 4))), 10688#(or (<= N i) (< (+ i 1) N) (<= N (+ 3 j))), 10680#(or (<= N j) (< (+ i 4) N) (<= N (+ 3 i))), 10671#(or (<= N j) (<= N i) (< (+ i 1) N)), 10684#(or (<= N (+ i 1)) (<= N (+ 2 j)) (< (+ 2 i) N)), 10689#(or (<= N (+ i 1)) (< (+ 2 i) N) (<= N (+ 3 j))), 10673#(or (<= N (+ 2 i)) (< (+ 3 i) N)), 10669#(or (<= N (+ i 1)) (< (+ 2 i) N)), 10668#(or (<= N i) (< (+ i 1) N)), 10655#(or (<= N (+ i 1)) (< (+ 2 i) N) (<= N (+ j 4)))] [2022-03-15 21:28:05,533 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 42 states [2022-03-15 21:28:05,533 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 21:28:05,533 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 42 interpolants. [2022-03-15 21:28:05,534 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=372, Invalid=1884, Unknown=0, NotChecked=0, Total=2256 [2022-03-15 21:28:05,534 INFO L87 Difference]: Start difference. First operand 500 states and 1445 transitions. Second operand has 42 states, 42 states have (on average 2.0714285714285716) internal successors, (87), 41 states have internal predecessors, (87), 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:28:12,160 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 21:28:12,161 INFO L93 Difference]: Finished difference Result 1361 states and 3763 transitions. [2022-03-15 21:28:12,161 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 223 states. [2022-03-15 21:28:12,161 INFO L78 Accepts]: Start accepts. Automaton has has 42 states, 42 states have (on average 2.0714285714285716) internal successors, (87), 41 states have internal predecessors, (87), 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 17 [2022-03-15 21:28:12,161 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 21:28:12,165 INFO L225 Difference]: With dead ends: 1361 [2022-03-15 21:28:12,165 INFO L226 Difference]: Without dead ends: 1316 [2022-03-15 21:28:12,170 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 293 GetRequests, 38 SyntacticMatches, 0 SemanticMatches, 255 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 28971 ImplicationChecksByTransitivity, 6.4s TimeCoverageRelationStatistics Valid=19357, Invalid=46435, Unknown=0, NotChecked=0, Total=65792 [2022-03-15 21:28:12,171 INFO L933 BasicCegarLoop]: 1 mSDtfsCounter, 184 mSDsluCounter, 90 mSDsCounter, 0 mSdLazyCounter, 848 mSolverCounterSat, 140 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 184 SdHoareTripleChecker+Valid, 1 SdHoareTripleChecker+Invalid, 988 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 140 IncrementalHoareTripleChecker+Valid, 848 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2022-03-15 21:28:12,171 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [184 Valid, 1 Invalid, 988 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [140 Valid, 848 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2022-03-15 21:28:12,172 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1316 states. [2022-03-15 21:28:12,191 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1316 to 779. [2022-03-15 21:28:12,192 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 779 states, 778 states have (on average 3.0526992287917736) internal successors, (2375), 778 states have internal predecessors, (2375), 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:28:12,194 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 779 states to 779 states and 2375 transitions. [2022-03-15 21:28:12,194 INFO L78 Accepts]: Start accepts. Automaton has 779 states and 2375 transitions. Word has length 17 [2022-03-15 21:28:12,194 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 21:28:12,194 INFO L470 AbstractCegarLoop]: Abstraction has 779 states and 2375 transitions. [2022-03-15 21:28:12,194 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 42 states, 42 states have (on average 2.0714285714285716) internal successors, (87), 41 states have internal predecessors, (87), 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:28:12,194 INFO L276 IsEmpty]: Start isEmpty. Operand 779 states and 2375 transitions. [2022-03-15 21:28:12,196 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2022-03-15 21:28:12,196 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 21:28:12,196 INFO L514 BasicCegarLoop]: trace histogram [5, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 21:28:12,213 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:28:12,411 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,SelfDestructingSolverStorable16 [2022-03-15 21:28:12,411 INFO L402 AbstractCegarLoop]: === Iteration 18 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION] === [2022-03-15 21:28:12,411 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 21:28:12,411 INFO L85 PathProgramCache]: Analyzing trace with hash -502484268, now seen corresponding path program 15 times [2022-03-15 21:28:12,412 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 21:28:12,412 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1668702207] [2022-03-15 21:28:12,412 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 21:28:12,412 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 21:28:12,419 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 21:28:12,481 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 6 proven. 19 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 21:28:12,481 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 21:28:12,481 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1668702207] [2022-03-15 21:28:12,481 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1668702207] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-15 21:28:12,481 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [897240528] [2022-03-15 21:28:12,482 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-03-15 21:28:12,482 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 21:28:12,482 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 21:28:12,483 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:28:12,484 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:28:12,508 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2022-03-15 21:28:12,508 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-15 21:28:12,509 INFO L263 TraceCheckSpWp]: Trace formula consists of 50 conjuncts, 12 conjunts are in the unsatisfiable core [2022-03-15 21:28:12,509 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-15 21:28:13,625 INFO L353 Elim1Store]: treesize reduction 112, result has 0.9 percent of original size [2022-03-15 21:28:13,626 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 5 select indices, 5 select index equivalence classes, 0 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 10 case distinctions, treesize of input 1008 treesize of output 532 [2022-03-15 21:28:13,687 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 0 proven. 25 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 21:28:13,687 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-15 21:28:13,859 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 62 treesize of output 54 [2022-03-15 21:28:13,875 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 10 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 21:28:13,875 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [897240528] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-15 21:28:13,876 INFO L191 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-03-15 21:28:13,876 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11, 11] total 21 [2022-03-15 21:28:13,876 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [1340784641] [2022-03-15 21:28:13,876 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 21:28:13,877 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 21:28:13,883 INFO L252 McrAutomatonBuilder]: Finished intersection with 59 states and 99 transitions. [2022-03-15 21:28:13,883 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 21:28:15,795 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 36 new interpolants: [14171#(or (< (+ 5 i) N) (<= (+ 3 j) N) (<= N (+ i 4))), 14162#(or (<= N (+ i 1)) (< (+ 2 i) N) (<= (+ 2 j) N)), 14182#(or (< (+ i 4) N) (<= N (+ 3 i)) (<= (+ 5 j) N)), 14153#(or (< (+ 5 i) N) (<= N (+ i 4))), 14160#(or (<= (+ 2 j) N) (< i N)), 14166#(or (<= (+ 3 j) N) (< i N)), 14183#(or (< (+ 5 i) N) (<= N (+ i 4)) (<= (+ 5 j) N)), 14168#(or (<= N (+ i 1)) (< (+ 2 i) N) (<= (+ 3 j) N)), 14180#(or (<= N (+ i 1)) (< (+ 2 i) N) (<= (+ 5 j) N)), 14179#(or (<= N i) (< (+ i 1) N) (<= (+ 5 j) N)), 14156#(or (<= N (+ i 1)) (< (+ 2 i) N) (< j N)), 14161#(or (<= N i) (< (+ i 1) N) (<= (+ 2 j) N)), 14178#(or (< (+ 5 i) N) (<= (+ j 4) N) (<= N (+ i 4))), 14149#(or (<= N i) (< (+ i 1) N)), 14176#(or (<= N (+ 2 i)) (<= (+ j 4) N) (< (+ 3 i) N)), 14177#(or (< (+ i 4) N) (<= (+ j 4) N) (<= N (+ 3 i))), 14181#(or (<= N (+ 2 i)) (< (+ 3 i) N) (<= (+ 5 j) N)), 14152#(or (< (+ i 4) N) (<= N (+ 3 i))), 14154#(or (<= (+ j 1) N) (< i N)), 14164#(or (< (+ i 4) N) (<= N (+ 3 i)) (<= (+ 2 j) N)), 14148#(< i N), 14174#(or (<= N i) (< (+ i 1) N) (<= (+ j 4) N)), 14157#(or (<= N (+ 2 i)) (< (+ 3 i) N) (< j N)), 14175#(or (<= N (+ i 1)) (< (+ 2 i) N) (<= (+ j 4) N)), 14151#(or (<= N (+ 2 i)) (< (+ 3 i) N)), 14172#(or (<= (+ j 4) N) (< i N)), 14169#(or (<= N (+ 2 i)) (< (+ 3 i) N) (<= (+ 3 j) N)), 14165#(or (< (+ 5 i) N) (<= (+ 2 j) N) (<= N (+ i 4))), 14158#(or (< (+ i 4) N) (<= N (+ 3 i)) (< j N)), 14170#(or (< (+ i 4) N) (<= N (+ 3 i)) (<= (+ 3 j) N)), 14159#(or (< (+ 5 i) N) (< j N) (<= N (+ i 4))), 14173#(or (< i N) (<= (+ 5 j) N)), 14163#(or (<= N (+ 2 i)) (<= (+ 2 j) N) (< (+ 3 i) N)), 14155#(or (<= N i) (< (+ i 1) N) (< j N)), 14150#(or (<= N (+ i 1)) (< (+ 2 i) N)), 14167#(or (<= N i) (< (+ i 1) N) (<= (+ 3 j) N))] [2022-03-15 21:28:15,795 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 48 states [2022-03-15 21:28:15,795 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 21:28:15,795 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 48 interpolants. [2022-03-15 21:28:15,796 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=675, Invalid=2631, Unknown=0, NotChecked=0, Total=3306 [2022-03-15 21:28:15,796 INFO L87 Difference]: Start difference. First operand 779 states and 2375 transitions. Second operand has 48 states, 48 states have (on average 1.9583333333333333) internal successors, (94), 47 states have internal predecessors, (94), 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:28:17,517 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 21:28:17,518 INFO L93 Difference]: Finished difference Result 1348 states and 3941 transitions. [2022-03-15 21:28:17,518 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 82 states. [2022-03-15 21:28:17,518 INFO L78 Accepts]: Start accepts. Automaton has has 48 states, 48 states have (on average 1.9583333333333333) internal successors, (94), 47 states have internal predecessors, (94), 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 17 [2022-03-15 21:28:17,518 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 21:28:17,522 INFO L225 Difference]: With dead ends: 1348 [2022-03-15 21:28:17,522 INFO L226 Difference]: Without dead ends: 1339 [2022-03-15 21:28:17,524 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 146 GetRequests, 25 SyntacticMatches, 3 SemanticMatches, 118 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4362 ImplicationChecksByTransitivity, 2.3s TimeCoverageRelationStatistics Valid=3059, Invalid=11221, Unknown=0, NotChecked=0, Total=14280 [2022-03-15 21:28:17,524 INFO L933 BasicCegarLoop]: 1 mSDtfsCounter, 208 mSDsluCounter, 102 mSDsCounter, 0 mSdLazyCounter, 765 mSolverCounterSat, 200 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 208 SdHoareTripleChecker+Valid, 1 SdHoareTripleChecker+Invalid, 965 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 200 IncrementalHoareTripleChecker+Valid, 765 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2022-03-15 21:28:17,524 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [208 Valid, 1 Invalid, 965 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [200 Valid, 765 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2022-03-15 21:28:17,525 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1339 states. [2022-03-15 21:28:17,539 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1339 to 944. [2022-03-15 21:28:17,540 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 944 states, 943 states have (on average 2.9766702014846236) internal successors, (2807), 943 states have internal predecessors, (2807), 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:28:17,542 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 944 states to 944 states and 2807 transitions. [2022-03-15 21:28:17,542 INFO L78 Accepts]: Start accepts. Automaton has 944 states and 2807 transitions. Word has length 17 [2022-03-15 21:28:17,543 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 21:28:17,543 INFO L470 AbstractCegarLoop]: Abstraction has 944 states and 2807 transitions. [2022-03-15 21:28:17,543 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 48 states, 48 states have (on average 1.9583333333333333) internal successors, (94), 47 states have internal predecessors, (94), 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:28:17,544 INFO L276 IsEmpty]: Start isEmpty. Operand 944 states and 2807 transitions. [2022-03-15 21:28:17,545 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2022-03-15 21:28:17,545 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 21:28:17,545 INFO L514 BasicCegarLoop]: trace histogram [5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 21:28:17,563 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:28:17,760 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2022-03-15 21:28:17,761 INFO L402 AbstractCegarLoop]: === Iteration 19 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION] === [2022-03-15 21:28:17,761 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 21:28:17,761 INFO L85 PathProgramCache]: Analyzing trace with hash 1602962623, now seen corresponding path program 16 times [2022-03-15 21:28:17,762 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 21:28:17,762 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [334250894] [2022-03-15 21:28:17,762 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 21:28:17,762 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 21:28:18,077 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat Received shutdown request... [2022-03-15 21:30:07,967 INFO L764 garLoopResultBuilder]: Registering result TIMEOUT for location ULTIMATE.startErr0ASSERT_VIOLATIONASSERT (2 of 3 remaining) [2022-03-15 21:30:07,967 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18 [2022-03-15 21:30:07,967 WARN L594 AbstractCegarLoop]: Verification canceled: while BasicCegarLoop was analyzing trace of length 19 with TraceHistMax 5,while InterpolatingTraceCheckCraig was constructing Craig interpolants,while PolyPacSimplificationTermWalker was simplifying a ∧-33-4-41-4-42-5-37-4-37-4-37-4-37-4-37-4-37-4-23-4-21-4-21-4-19-4-19-4-18-4-17-4-16-4-15-4-15-4-15-4-15-4-14-4-14-4-13-4-13-4-13-4-12-4-10-4-10-4-10-4-10-4-10-4-10-4-10-4-10-3-10-2-1 term,while PolyPacSimplificationTermWalker was simplifying 3 xjuncts wrt. a ∧-5-1 context. [2022-03-15 21:30:07,968 INFO L764 garLoopResultBuilder]: Registering result TIMEOUT for location ULTIMATE.startErr0INUSE_VIOLATION (1 of 3 remaining) [2022-03-15 21:30:07,968 INFO L764 garLoopResultBuilder]: Registering result TIMEOUT for location ULTIMATE.startErr1INUSE_VIOLATION (0 of 3 remaining) [2022-03-15 21:30:07,969 INFO L732 BasicCegarLoop]: Path program histogram: [16, 1, 1, 1] [2022-03-15 21:30:07,972 INFO L230 ceAbstractionStarter]: Analysis of concurrent program completed with 1 thread instances [2022-03-15 21:30:07,972 INFO L180 ceAbstractionStarter]: Computing trace abstraction results [2022-03-15 21:30:07,975 INFO L202 PluginConnector]: Adding new model misc-1.wvr.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 15.03 09:30:07 BasicIcfg [2022-03-15 21:30:07,975 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2022-03-15 21:30:07,975 INFO L158 Benchmark]: Toolchain (without parser) took 872723.85ms. Allocated memory was 194.0MB in the beginning and 1.0GB in the end (delta: 852.5MB). Free memory was 151.1MB in the beginning and 756.1MB in the end (delta: -605.0MB). Peak memory consumption was 668.9MB. Max. memory is 8.0GB. [2022-03-15 21:30:07,975 INFO L158 Benchmark]: Boogie PL CUP Parser took 0.09ms. Allocated memory is still 194.0MB. Free memory is still 152.2MB. There was no memory consumed. Max. memory is 8.0GB. [2022-03-15 21:30:07,975 INFO L158 Benchmark]: Boogie Procedure Inliner took 17.79ms. Allocated memory is still 194.0MB. Free memory was 151.0MB in the beginning and 149.5MB in the end (delta: 1.5MB). Peak memory consumption was 3.1MB. Max. memory is 8.0GB. [2022-03-15 21:30:07,976 INFO L158 Benchmark]: Boogie Preprocessor took 17.25ms. Allocated memory is still 194.0MB. Free memory was 149.5MB in the beginning and 148.6MB in the end (delta: 916.6kB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. [2022-03-15 21:30:07,976 INFO L158 Benchmark]: RCFGBuilder took 178.38ms. Allocated memory is still 194.0MB. Free memory was 148.4MB in the beginning and 139.5MB in the end (delta: 8.9MB). Peak memory consumption was 8.4MB. Max. memory is 8.0GB. [2022-03-15 21:30:07,976 INFO L158 Benchmark]: TraceAbstraction took 872505.97ms. Allocated memory was 194.0MB in the beginning and 1.0GB in the end (delta: 852.5MB). Free memory was 139.0MB in the beginning and 756.1MB in the end (delta: -617.1MB). Peak memory consumption was 655.3MB. Max. memory is 8.0GB. [2022-03-15 21:30:07,977 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 194.0MB. Free memory is still 152.2MB. There was no memory consumed. Max. memory is 8.0GB. * Boogie Procedure Inliner took 17.79ms. Allocated memory is still 194.0MB. Free memory was 151.0MB in the beginning and 149.5MB in the end (delta: 1.5MB). Peak memory consumption was 3.1MB. Max. memory is 8.0GB. * Boogie Preprocessor took 17.25ms. Allocated memory is still 194.0MB. Free memory was 149.5MB in the beginning and 148.6MB in the end (delta: 916.6kB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. * RCFGBuilder took 178.38ms. Allocated memory is still 194.0MB. Free memory was 148.4MB in the beginning and 139.5MB in the end (delta: 8.9MB). Peak memory consumption was 8.4MB. Max. memory is 8.0GB. * TraceAbstraction took 872505.97ms. Allocated memory was 194.0MB in the beginning and 1.0GB in the end (delta: 852.5MB). Free memory was 139.0MB in the beginning and 756.1MB in the end (delta: -617.1MB). Peak memory consumption was 655.3MB. Max. memory is 8.0GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: PetriNetLargeBlockEncoding benchmarks Lipton Reduction Statistics: ReductionTime: 0.5s, 34 PlacesBefore, 18 PlacesAfterwards, 31 TransitionsBefore, 13 TransitionsAfterwards, 240 CoEnabledTransitionPairs, 3 FixpointIterations, 3 TrivialSequentialCompositions, 15 ConcurrentSequentialCompositions, 0 TrivialYvCompositions, 2 ConcurrentYvCompositions, 2 ChoiceCompositions, 22 TotalNumberOfCompositions, 190 MoverChecksTotal, Independence Relation Statistics: CachedIndependenceRelation.Independence Queries: [ total: 190, positive: 190, positive conditional: 0, positive unconditional: 190, 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: 129, positive: 129, positive conditional: 0, positive unconditional: 129, negative: 0, negative conditional: 0, negative unconditional: 0, unknown: 0, unknown conditional: 0, unknown unconditional: 0] , Cache Queries: [ total: 190, positive: 61, positive conditional: 0, positive unconditional: 61, negative: 0, negative conditional: 0, negative unconditional: 0, unknown: 129, unknown conditional: 0, unknown unconditional: 129] , Statistics on independence cache: Total cache size (in pairs): 5, Positive cache size: 5, Positive conditional cache size: 0, Positive unconditional cache size: 5, 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: 65]: Timeout (TraceAbstraction) Unable to prove that assertion always holds Cancelled while BasicCegarLoop was analyzing trace of length 19 with TraceHistMax 5,while InterpolatingTraceCheckCraig was constructing Craig interpolants,while PolyPacSimplificationTermWalker was simplifying a ∧-33-4-41-4-42-5-37-4-37-4-37-4-37-4-37-4-37-4-23-4-21-4-21-4-19-4-19-4-18-4-17-4-16-4-15-4-15-4-15-4-15-4-14-4-14-4-13-4-13-4-13-4-12-4-10-4-10-4-10-4-10-4-10-4-10-4-10-4-10-3-10-2-1 term,while PolyPacSimplificationTermWalker was simplifying 3 xjuncts wrt. a ∧-5-1 context. - TimeoutResultAtElement [Line: 60]: 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 19 with TraceHistMax 5,while InterpolatingTraceCheckCraig was constructing Craig interpolants,while PolyPacSimplificationTermWalker was simplifying a ∧-33-4-41-4-42-5-37-4-37-4-37-4-37-4-37-4-37-4-23-4-21-4-21-4-19-4-19-4-18-4-17-4-16-4-15-4-15-4-15-4-15-4-14-4-14-4-13-4-13-4-13-4-12-4-10-4-10-4-10-4-10-4-10-4-10-4-10-4-10-3-10-2-1 term,while PolyPacSimplificationTermWalker was simplifying 3 xjuncts wrt. a ∧-5-1 context. - TimeoutResultAtElement [Line: 60]: 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 19 with TraceHistMax 5,while InterpolatingTraceCheckCraig was constructing Craig interpolants,while PolyPacSimplificationTermWalker was simplifying a ∧-33-4-41-4-42-5-37-4-37-4-37-4-37-4-37-4-37-4-23-4-21-4-21-4-19-4-19-4-18-4-17-4-16-4-15-4-15-4-15-4-15-4-14-4-14-4-13-4-13-4-13-4-12-4-10-4-10-4-10-4-10-4-10-4-10-4-10-4-10-3-10-2-1 term,while PolyPacSimplificationTermWalker was simplifying 3 xjuncts wrt. a ∧-5-1 context. - StatisticsResult: Ultimate Automizer benchmark data with 1 thread instances CFG has 5 procedures, 48 locations, 3 error locations. Started 1 CEGAR loops. OverallTime: 872.4s, OverallIterations: 19, TraceHistogramMax: 5, PathProgramHistogramMax: 16, EmptinessCheckTime: 0.0s, AutomataDifference: 18.4s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.6s, PartialOrderReductionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 1324 SdHoareTripleChecker+Valid, 4.5s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 1324 mSDsluCounter, 18 SdHoareTripleChecker+Invalid, 3.7s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 1706 mSDsCounter, 1107 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 8585 IncrementalHoareTripleChecker+Invalid, 9692 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 1107 mSolverCounterUnsat, 18 mSDtfsCounter, 8585 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 1513 GetRequests, 361 SyntacticMatches, 34 SemanticMatches, 1118 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 49788 ImplicationChecksByTransitivity, 20.7s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=944occurred in iteration=18, InterpolantAutomatonStates: 841, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.2s AutomataMinimizationTime, 18 MinimizatonAttempts, 2067 StatesRemovedByMinimization, 16 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.5s SatisfiabilityAnalysisTime, 724.0s InterpolantComputationTime, 447 NumberOfCodeBlocks, 447 NumberOfCodeBlocksAsserted, 51 NumberOfCheckSat, 612 ConstructedInterpolants, 0 QuantifiedInterpolants, 11658 SizeOfPredicates, 156 NumberOfNonLiveVariables, 695 ConjunctsInSsa, 208 ConjunctsInUnsatCore, 50 InterpolantComputations, 2 PerfectInterpolantSequences, 216/571 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