/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/unroll-3.wvr.bpl -------------------------------------------------------------------------------- This is Ultimate 0.2.2-wip.dk.mcr-reduction-c7b2d19 [2022-03-15 20:44:04,273 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-03-15 20:44:04,275 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-03-15 20:44:04,329 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-03-15 20:44:04,329 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-03-15 20:44:04,330 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-03-15 20:44:04,330 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-03-15 20:44:04,332 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-03-15 20:44:04,333 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-03-15 20:44:04,333 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-03-15 20:44:04,334 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-03-15 20:44:04,339 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-03-15 20:44:04,339 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-03-15 20:44:04,343 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-03-15 20:44:04,344 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-03-15 20:44:04,346 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-03-15 20:44:04,346 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-03-15 20:44:04,347 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-03-15 20:44:04,353 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-03-15 20:44:04,355 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-03-15 20:44:04,357 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-03-15 20:44:04,358 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-03-15 20:44:04,358 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-03-15 20:44:04,359 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-03-15 20:44:04,362 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-03-15 20:44:04,362 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-03-15 20:44:04,363 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-03-15 20:44:04,363 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-03-15 20:44:04,363 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-03-15 20:44:04,364 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-03-15 20:44:04,364 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-03-15 20:44:04,364 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-03-15 20:44:04,365 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-03-15 20:44:04,365 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-03-15 20:44:04,366 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-03-15 20:44:04,366 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-03-15 20:44:04,366 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-03-15 20:44:04,366 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-03-15 20:44:04,367 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-03-15 20:44:04,367 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-03-15 20:44:04,367 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-03-15 20:44:04,371 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/mcr/svcomp-Reach-32bit-Automizer_Default-noMmResRef-FA-McrAutomaton-WP.epf [2022-03-15 20:44:04,395 INFO L113 SettingsManager]: Loading preferences was successful [2022-03-15 20:44:04,395 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-03-15 20:44:04,396 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-03-15 20:44:04,396 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-03-15 20:44:04,397 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-03-15 20:44:04,397 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-03-15 20:44:04,397 INFO L138 SettingsManager]: * Use SBE=true [2022-03-15 20:44:04,397 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-03-15 20:44:04,397 INFO L138 SettingsManager]: * sizeof long=4 [2022-03-15 20:44:04,397 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-03-15 20:44:04,398 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-03-15 20:44:04,398 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-03-15 20:44:04,398 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-03-15 20:44:04,398 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-03-15 20:44:04,398 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-03-15 20:44:04,398 INFO L138 SettingsManager]: * sizeof long double=12 [2022-03-15 20:44:04,398 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-03-15 20:44:04,398 INFO L138 SettingsManager]: * Use constant arrays=true [2022-03-15 20:44:04,398 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-03-15 20:44:04,399 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-03-15 20:44:04,399 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-03-15 20:44:04,399 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-03-15 20:44:04,399 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-03-15 20:44:04,399 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-15 20:44:04,399 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-03-15 20:44:04,399 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_NestedInterpolation [2022-03-15 20:44:04,399 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-03-15 20:44:04,399 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-03-15 20:44:04,400 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2022-03-15 20:44:04,400 INFO L138 SettingsManager]: * Override the interpolant automaton setting of the refinement strategy=true [2022-03-15 20:44:04,400 INFO L138 SettingsManager]: * Large block encoding in concurrent analysis=VARIABLE_BASED_MOVER_CHECK [2022-03-15 20:44:04,400 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-03-15 20:44:04,400 INFO L138 SettingsManager]: * Interpolant automaton=MCR WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release [2022-03-15 20:44:04,578 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-03-15 20:44:04,594 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-03-15 20:44:04,595 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-03-15 20:44:04,596 INFO L271 PluginConnector]: Initializing Boogie PL CUP Parser... [2022-03-15 20:44:04,600 INFO L275 PluginConnector]: Boogie PL CUP Parser initialized [2022-03-15 20:44:04,601 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/concurrent/bpl/weaver-benchmarks/generated/unroll-3.wvr.bpl [2022-03-15 20:44:04,601 INFO L110 BoogieParser]: Parsing: '/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/concurrent/bpl/weaver-benchmarks/generated/unroll-3.wvr.bpl' [2022-03-15 20:44:04,625 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-03-15 20:44:04,626 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-03-15 20:44:04,627 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2022-03-15 20:44:04,627 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2022-03-15 20:44:04,627 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2022-03-15 20:44:04,636 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "unroll-3.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.03 08:44:04" (1/1) ... [2022-03-15 20:44:04,644 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "unroll-3.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.03 08:44:04" (1/1) ... [2022-03-15 20:44:04,649 INFO L137 Inliner]: procedures = 3, calls = 2, calls flagged for inlining = 0, calls inlined = 0, statements flattened = 0 [2022-03-15 20:44:04,650 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2022-03-15 20:44:04,651 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-03-15 20:44:04,651 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-03-15 20:44:04,651 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-03-15 20:44:04,656 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "unroll-3.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.03 08:44:04" (1/1) ... [2022-03-15 20:44:04,656 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "unroll-3.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.03 08:44:04" (1/1) ... [2022-03-15 20:44:04,657 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "unroll-3.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.03 08:44:04" (1/1) ... [2022-03-15 20:44:04,657 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "unroll-3.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.03 08:44:04" (1/1) ... [2022-03-15 20:44:04,659 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "unroll-3.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.03 08:44:04" (1/1) ... [2022-03-15 20:44:04,661 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "unroll-3.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.03 08:44:04" (1/1) ... [2022-03-15 20:44:04,662 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "unroll-3.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.03 08:44:04" (1/1) ... [2022-03-15 20:44:04,663 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-03-15 20:44:04,664 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-03-15 20:44:04,664 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-03-15 20:44:04,665 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-03-15 20:44:04,666 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "unroll-3.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.03 08:44:04" (1/1) ... [2022-03-15 20:44:04,671 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-15 20:44:04,679 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 20:44:04,695 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2022-03-15 20:44:04,703 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2022-03-15 20:44:04,726 INFO L124 BoogieDeclarations]: Specification and implementation of procedure thread1 given in one single declaration [2022-03-15 20:44:04,727 INFO L130 BoogieDeclarations]: Found specification of procedure thread1 [2022-03-15 20:44:04,727 INFO L138 BoogieDeclarations]: Found implementation of procedure thread1 [2022-03-15 20:44:04,727 INFO L124 BoogieDeclarations]: Specification and implementation of procedure thread2 given in one single declaration [2022-03-15 20:44:04,727 INFO L130 BoogieDeclarations]: Found specification of procedure thread2 [2022-03-15 20:44:04,727 INFO L138 BoogieDeclarations]: Found implementation of procedure thread2 [2022-03-15 20:44:04,727 INFO L124 BoogieDeclarations]: Specification and implementation of procedure ULTIMATE.start given in one single declaration [2022-03-15 20:44:04,727 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-03-15 20:44:04,727 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-03-15 20:44:04,728 WARN L208 CfgBuilder]: User set CodeBlockSize to SequenceOfStatements but program contains fork statements. Overwriting the user preferences and setting CodeBlockSize to SingleStatement [2022-03-15 20:44:04,758 INFO L234 CfgBuilder]: Building ICFG [2022-03-15 20:44:04,759 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-03-15 20:44:04,828 INFO L275 CfgBuilder]: Performing block encoding [2022-03-15 20:44:04,848 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-03-15 20:44:04,848 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-03-15 20:44:04,849 WARN L329 CfgBuilder]: Unexpected successor node of atomic block begin: thread1EXIT is neither atomic block end nor error location. [2022-03-15 20:44:04,849 WARN L329 CfgBuilder]: Unexpected successor node of atomic block begin: thread2EXIT is neither atomic block end nor error location. [2022-03-15 20:44:04,850 INFO L202 PluginConnector]: Adding new model unroll-3.wvr.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 15.03 08:44:04 BoogieIcfgContainer [2022-03-15 20:44:04,850 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-03-15 20:44:04,851 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-03-15 20:44:04,851 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-03-15 20:44:04,853 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-03-15 20:44:04,853 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "unroll-3.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.03 08:44:04" (1/2) ... [2022-03-15 20:44:04,854 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@657f5fc1 and model type unroll-3.wvr.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 15.03 08:44:04, skipping insertion in model container [2022-03-15 20:44:04,854 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "unroll-3.wvr.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 15.03 08:44:04" (2/2) ... [2022-03-15 20:44:04,855 INFO L111 eAbstractionObserver]: Analyzing ICFG unroll-3.wvr.bpl [2022-03-15 20:44:04,858 WARN L150 ceAbstractionStarter]: Switching off computation of Hoare annotation because input is a concurrent program [2022-03-15 20:44:04,858 INFO L205 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:Craig_NestedInterpolation Determinization: PREDICATE_ABSTRACTION [2022-03-15 20:44:04,858 INFO L164 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-03-15 20:44:04,858 INFO L534 ceAbstractionStarter]: Constructing petrified ICFG for 1 thread instances. [2022-03-15 20:44:04,875 INFO L148 ThreadInstanceAdder]: Constructed 2 joinOtherThreadTransitions. [2022-03-15 20:44:04,901 INFO L338 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-03-15 20:44:04,908 INFO L339 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=Craig_NestedInterpolation, mInterpolantAutomaton=MCR, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=FINITE_AUTOMATA, mLazyFiniteAutomaton=false, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopsAndPotentialCycles, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=true, mMcrInterpolantMethod=WP, mLoopAccelerationTechnique=FAST_UPR, mMcrOptimizeForkJoin=true, mMcrOverapproximateWrwc=true [2022-03-15 20:44:04,909 INFO L340 AbstractCegarLoop]: Starting to check reachability of 3 error locations. [2022-03-15 20:44:04,916 INFO L126 etLargeBlockEncoding]: Petri net LBE is using variable-based independence relation. [2022-03-15 20:44:04,922 INFO L133 etLargeBlockEncoding]: Starting large block encoding on Petri net that has 20 places, 15 transitions, 46 flow [2022-03-15 20:44:04,924 INFO L110 LiptonReduction]: Starting Lipton reduction on Petri net that has 20 places, 15 transitions, 46 flow [2022-03-15 20:44:04,925 INFO L74 FinitePrefix]: Start finitePrefix. Operand has 20 places, 15 transitions, 46 flow [2022-03-15 20:44:04,941 INFO L129 PetriNetUnfolder]: 2/13 cut-off events. [2022-03-15 20:44:04,941 INFO L130 PetriNetUnfolder]: For 2/2 co-relation queries the response was YES. [2022-03-15 20:44:04,943 INFO L84 FinitePrefix]: Finished finitePrefix Result has 22 conditions, 13 events. 2/13 cut-off events. For 2/2 co-relation queries the response was YES. Maximal size of possible extension queue 2. Compared 6 event pairs, 0 based on Foata normal form. 0/10 useless extension candidates. Maximal degree in co-relation 8. Up to 2 conditions per place. [2022-03-15 20:44:04,943 INFO L116 LiptonReduction]: Number of co-enabled transitions 16 [2022-03-15 20:44:04,982 INFO L131 LiptonReduction]: Checked pairs total: 18 [2022-03-15 20:44:04,982 INFO L133 LiptonReduction]: Total number of compositions: 3 [2022-03-15 20:44:04,987 INFO L111 iNet2FiniteAutomaton]: Start petriNet2FiniteAutomaton. Operand has 18 places, 13 transitions, 42 flow [2022-03-15 20:44:04,994 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 20:44:04,995 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 20:44:04,998 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2022-03-15 20:44:04,998 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 20:44:04,998 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 20:44:04,999 INFO L402 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION] === [2022-03-15 20:44:05,002 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 20:44:05,002 INFO L85 PathProgramCache]: Analyzing trace with hash -1964353950, now seen corresponding path program 1 times [2022-03-15 20:44:05,030 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 20:44:05,030 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1695478662] [2022-03-15 20:44:05,030 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 20:44:05,031 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 20:44:05,152 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 20:44:05,190 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 20:44:05,190 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 20:44:05,190 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1695478662] [2022-03-15 20:44:05,191 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1695478662] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-15 20:44:05,191 INFO L191 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-15 20:44:05,191 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2022-03-15 20:44:05,192 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [1703372410] [2022-03-15 20:44:05,192 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 20:44:05,194 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 20:44:05,235 INFO L252 McrAutomatonBuilder]: Finished intersection with 12 states and 14 transitions. [2022-03-15 20:44:05,235 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 20:44:05,337 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 0 new interpolants: [] [2022-03-15 20:44:05,338 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-03-15 20:44:05,339 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 20:44:05,372 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-03-15 20:44:05,373 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-03-15 20:44:05,374 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 3 states, 2 states have (on average 4.0) internal successors, (8), 2 states have internal predecessors, (8), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:44:05,418 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 20:44:05,419 INFO L93 Difference]: Finished difference Result 21 states and 37 transitions. [2022-03-15 20:44:05,421 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-03-15 20:44:05,422 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 2 states have (on average 4.0) internal successors, (8), 2 states have internal predecessors, (8), 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 20:44:05,422 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 20:44:05,430 INFO L225 Difference]: With dead ends: 21 [2022-03-15 20:44:05,431 INFO L226 Difference]: Without dead ends: 18 [2022-03-15 20:44:05,432 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-03-15 20:44:05,435 INFO L933 BasicCegarLoop]: 1 mSDtfsCounter, 0 mSDsluCounter, 5 mSDsCounter, 0 mSdLazyCounter, 17 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 1 SdHoareTripleChecker+Invalid, 17 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 17 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-15 20:44:05,436 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 1 Invalid, 17 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 17 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-15 20:44:05,447 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 18 states. [2022-03-15 20:44:05,462 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 18 to 18. [2022-03-15 20:44:05,463 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 20:44:05,463 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 18 states to 18 states and 32 transitions. [2022-03-15 20:44:05,464 INFO L78 Accepts]: Start accepts. Automaton has 18 states and 32 transitions. Word has length 8 [2022-03-15 20:44:05,464 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 20:44:05,464 INFO L470 AbstractCegarLoop]: Abstraction has 18 states and 32 transitions. [2022-03-15 20:44:05,464 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 2 states have (on average 4.0) internal successors, (8), 2 states have internal predecessors, (8), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:44:05,464 INFO L276 IsEmpty]: Start isEmpty. Operand 18 states and 32 transitions. [2022-03-15 20:44:05,465 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2022-03-15 20:44:05,465 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 20:44:05,465 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 20:44:05,465 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-03-15 20:44:05,465 INFO L402 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION] === [2022-03-15 20:44:05,466 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 20:44:05,466 INFO L85 PathProgramCache]: Analyzing trace with hash -764686491, now seen corresponding path program 1 times [2022-03-15 20:44:05,470 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 20:44:05,470 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [131235187] [2022-03-15 20:44:05,470 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 20:44:05,470 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 20:44:05,480 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 20:44:05,500 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 20:44:05,500 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 20:44:05,500 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [131235187] [2022-03-15 20:44:05,500 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [131235187] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-15 20:44:05,500 INFO L191 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-15 20:44:05,501 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-03-15 20:44:05,501 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [518694902] [2022-03-15 20:44:05,501 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 20:44:05,502 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 20:44:05,504 INFO L252 McrAutomatonBuilder]: Finished intersection with 15 states and 19 transitions. [2022-03-15 20:44:05,504 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 20:44:05,573 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 4 new interpolants: [111#(< i2 (* 3 n)), 113#(< i1 (* 3 n)), 112#(or (<= (* 3 n) i2) (< (+ 3 i2) (* 3 n))), 114#(or (<= (* 3 n) i2) (< i1 (* 3 n)))] [2022-03-15 20:44:05,574 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-03-15 20:44:05,574 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 20:44:05,574 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-03-15 20:44:05,575 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2022-03-15 20:44:05,575 INFO L87 Difference]: Start difference. First operand 18 states and 32 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 20:44:05,647 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 20:44:05,647 INFO L93 Difference]: Finished difference Result 23 states and 39 transitions. [2022-03-15 20:44:05,647 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-03-15 20:44:05,647 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 20:44:05,647 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 20:44:05,649 INFO L225 Difference]: With dead ends: 23 [2022-03-15 20:44:05,649 INFO L226 Difference]: Without dead ends: 19 [2022-03-15 20:44:05,650 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=29, Invalid=61, Unknown=0, NotChecked=0, Total=90 [2022-03-15 20:44:05,651 INFO L933 BasicCegarLoop]: 1 mSDtfsCounter, 29 mSDsluCounter, 23 mSDsCounter, 0 mSdLazyCounter, 81 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 29 SdHoareTripleChecker+Valid, 1 SdHoareTripleChecker+Invalid, 96 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 81 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-15 20:44:05,653 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [29 Valid, 1 Invalid, 96 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 81 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-15 20:44:05,655 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 19 states. [2022-03-15 20:44:05,659 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 19 to 19. [2022-03-15 20:44:05,659 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 20:44:05,660 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 19 states to 19 states and 34 transitions. [2022-03-15 20:44:05,660 INFO L78 Accepts]: Start accepts. Automaton has 19 states and 34 transitions. Word has length 9 [2022-03-15 20:44:05,661 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 20:44:05,661 INFO L470 AbstractCegarLoop]: Abstraction has 19 states and 34 transitions. [2022-03-15 20:44:05,661 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 20:44:05,662 INFO L276 IsEmpty]: Start isEmpty. Operand 19 states and 34 transitions. [2022-03-15 20:44:05,662 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2022-03-15 20:44:05,662 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 20:44:05,663 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 20:44:05,664 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-03-15 20:44:05,665 INFO L402 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION] === [2022-03-15 20:44:05,667 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 20:44:05,668 INFO L85 PathProgramCache]: Analyzing trace with hash 2005034838, now seen corresponding path program 1 times [2022-03-15 20:44:05,669 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 20:44:05,669 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [283946663] [2022-03-15 20:44:05,669 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 20:44:05,669 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 20:44:05,684 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 20:44:05,739 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2022-03-15 20:44:05,739 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 20:44:05,739 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [283946663] [2022-03-15 20:44:05,739 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [283946663] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-15 20:44:05,740 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1183149354] [2022-03-15 20:44:05,740 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 20:44:05,740 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 20:44:05,740 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 20:44:05,752 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-15 20:44:05,755 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2022-03-15 20:44:05,781 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 20:44:05,782 INFO L263 TraceCheckSpWp]: Trace formula consists of 35 conjuncts, 5 conjunts are in the unsatisfiable core [2022-03-15 20:44:05,785 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-15 20:44:05,812 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2022-03-15 20:44:05,812 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-15 20:44:05,841 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2022-03-15 20:44:05,842 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1183149354] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-15 20:44:05,842 INFO L191 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-03-15 20:44:05,842 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [3, 3, 3] total 5 [2022-03-15 20:44:05,842 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [321799072] [2022-03-15 20:44:05,842 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 20:44:05,843 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 20:44:05,845 INFO L252 McrAutomatonBuilder]: Finished intersection with 19 states and 26 transitions. [2022-03-15 20:44:05,845 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 20:44:05,909 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 2 new interpolants: [240#(or (< (+ i1 1) (* 3 n)) (<= (* 3 n) i1)), 232#(< i1 (* 3 n))] [2022-03-15 20:44:05,909 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-03-15 20:44:05,909 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 20:44:05,909 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-03-15 20:44:05,909 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=26, Unknown=0, NotChecked=0, Total=42 [2022-03-15 20:44:05,910 INFO L87 Difference]: Start difference. First operand 19 states and 34 transitions. Second operand has 6 states, 6 states have (on average 3.0) internal successors, (18), 5 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 20:44:05,941 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 20:44:05,941 INFO L93 Difference]: Finished difference Result 27 states and 50 transitions. [2022-03-15 20:44:05,941 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-03-15 20:44:05,941 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 3.0) internal successors, (18), 5 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 10 [2022-03-15 20:44:05,942 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 20:44:05,942 INFO L225 Difference]: With dead ends: 27 [2022-03-15 20:44:05,942 INFO L226 Difference]: Without dead ends: 27 [2022-03-15 20:44:05,942 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 30 GetRequests, 24 SyntacticMatches, 1 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=16, Invalid=26, Unknown=0, NotChecked=0, Total=42 [2022-03-15 20:44:05,945 INFO L933 BasicCegarLoop]: 1 mSDtfsCounter, 12 mSDsluCounter, 16 mSDsCounter, 0 mSdLazyCounter, 49 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 1 SdHoareTripleChecker+Invalid, 52 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 49 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-15 20:44:05,945 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [12 Valid, 1 Invalid, 52 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 49 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-15 20:44:05,947 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2022-03-15 20:44:05,949 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 27. [2022-03-15 20:44:05,950 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 27 states, 26 states have (on average 1.9230769230769231) internal successors, (50), 26 states have internal predecessors, (50), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:44:05,950 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 50 transitions. [2022-03-15 20:44:05,950 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 50 transitions. Word has length 10 [2022-03-15 20:44:05,950 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 20:44:05,950 INFO L470 AbstractCegarLoop]: Abstraction has 27 states and 50 transitions. [2022-03-15 20:44:05,950 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 3.0) internal successors, (18), 5 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 20:44:05,950 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 50 transitions. [2022-03-15 20:44:05,951 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2022-03-15 20:44:05,951 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 20:44:05,951 INFO L514 BasicCegarLoop]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 20:44:05,969 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2022-03-15 20:44:06,156 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 20:44:06,157 INFO L402 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION] === [2022-03-15 20:44:06,158 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 20:44:06,158 INFO L85 PathProgramCache]: Analyzing trace with hash 789523766, now seen corresponding path program 2 times [2022-03-15 20:44:06,163 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 20:44:06,164 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1897048990] [2022-03-15 20:44:06,164 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 20:44:06,164 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 20:44:06,170 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 20:44:06,231 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 20:44:06,232 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 20:44:06,233 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1897048990] [2022-03-15 20:44:06,234 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1897048990] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-15 20:44:06,234 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1365989412] [2022-03-15 20:44:06,234 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-15 20:44:06,234 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 20:44:06,234 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 20:44:06,235 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-15 20:44:06,236 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2022-03-15 20:44:06,264 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-15 20:44:06,264 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-15 20:44:06,264 INFO L263 TraceCheckSpWp]: Trace formula consists of 45 conjuncts, 15 conjunts are in the unsatisfiable core [2022-03-15 20:44:06,265 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-15 20:44:06,366 INFO L353 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2022-03-15 20:44:06,366 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 5 new quantified variables, introduced 3 case distinctions, treesize of input 19 treesize of output 37 [2022-03-15 20:44:06,397 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 20:44:06,397 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-15 20:44:06,524 INFO L353 Elim1Store]: treesize reduction 15, result has 87.6 percent of original size [2022-03-15 20:44:06,525 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 6 select indices, 6 select index equivalence classes, 0 disjoint index pairs (out of 15 index pairs), introduced 10 new quantified variables, introduced 15 case distinctions, treesize of input 15 treesize of output 125 [2022-03-15 20:44:06,938 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 20:44:06,938 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1365989412] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-15 20:44:06,938 INFO L191 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-03-15 20:44:06,938 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 5, 4] total 10 [2022-03-15 20:44:06,938 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [729375188] [2022-03-15 20:44:06,939 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 20:44:06,939 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 20:44:06,941 INFO L252 McrAutomatonBuilder]: Finished intersection with 27 states and 40 transitions. [2022-03-15 20:44:06,941 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 20:44:07,072 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 6 new interpolants: [403#(= (select f (select f (select f x1))) (select f (select f (select f x2)))), 400#(= (select f x1) x2), 389#(= (select f x1) (select f (select f (select f x2)))), 402#(= (select f (select f (select f x1))) x2), 393#(= (select f (select f x1)) (select f (select f (select f x2)))), 401#(= (select f (select f x1)) x2)] [2022-03-15 20:44:07,073 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-03-15 20:44:07,073 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 20:44:07,073 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-03-15 20:44:07,073 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=39, Invalid=201, Unknown=0, NotChecked=0, Total=240 [2022-03-15 20:44:07,073 INFO L87 Difference]: Start difference. First operand 27 states and 50 transitions. Second operand has 12 states, 11 states have (on average 2.6363636363636362) internal successors, (29), 11 states have internal predecessors, (29), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:44:07,260 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 20:44:07,260 INFO L93 Difference]: Finished difference Result 93 states and 169 transitions. [2022-03-15 20:44:07,260 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-03-15 20:44:07,260 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 2.6363636363636362) internal successors, (29), 11 states have internal predecessors, (29), 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 20:44:07,260 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 20:44:07,262 INFO L225 Difference]: With dead ends: 93 [2022-03-15 20:44:07,262 INFO L226 Difference]: Without dead ends: 90 [2022-03-15 20:44:07,262 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 41 GetRequests, 27 SyntacticMatches, 0 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 42 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=39, Invalid=201, Unknown=0, NotChecked=0, Total=240 [2022-03-15 20:44:07,262 INFO L933 BasicCegarLoop]: 1 mSDtfsCounter, 33 mSDsluCounter, 282 mSDsCounter, 0 mSdLazyCounter, 522 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 33 SdHoareTripleChecker+Valid, 1 SdHoareTripleChecker+Invalid, 525 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 522 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-03-15 20:44:07,263 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [33 Valid, 1 Invalid, 525 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 522 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-03-15 20:44:07,263 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 90 states. [2022-03-15 20:44:07,267 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 90 to 48. [2022-03-15 20:44:07,267 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 48 states, 47 states have (on average 2.3191489361702127) internal successors, (109), 47 states have internal predecessors, (109), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:44:07,267 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 109 transitions. [2022-03-15 20:44:07,267 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 109 transitions. Word has length 12 [2022-03-15 20:44:07,267 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 20:44:07,267 INFO L470 AbstractCegarLoop]: Abstraction has 48 states and 109 transitions. [2022-03-15 20:44:07,267 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 2.6363636363636362) internal successors, (29), 11 states have internal predecessors, (29), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:44:07,268 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 109 transitions. [2022-03-15 20:44:07,268 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2022-03-15 20:44:07,268 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 20:44:07,268 INFO L514 BasicCegarLoop]: trace histogram [3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 20:44:07,284 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 20:44:07,483 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 20:44:07,484 INFO L402 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION] === [2022-03-15 20:44:07,484 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 20:44:07,484 INFO L85 PathProgramCache]: Analyzing trace with hash -1293823215, now seen corresponding path program 3 times [2022-03-15 20:44:07,486 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 20:44:07,486 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [509868875] [2022-03-15 20:44:07,486 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 20:44:07,486 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 20:44:07,494 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 20:44:07,535 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 20:44:07,536 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 20:44:07,538 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [509868875] [2022-03-15 20:44:07,538 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [509868875] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-15 20:44:07,538 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [357716301] [2022-03-15 20:44:07,538 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-03-15 20:44:07,538 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 20:44:07,538 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 20:44:07,552 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-15 20:44:07,552 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2022-03-15 20:44:07,579 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2022-03-15 20:44:07,579 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-15 20:44:07,580 INFO L263 TraceCheckSpWp]: Trace formula consists of 50 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-15 20:44:07,580 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-15 20:44:07,603 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 20:44:07,603 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-15 20:44:07,674 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 20:44:07,674 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [357716301] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-15 20:44:07,674 INFO L191 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-03-15 20:44:07,674 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 12 [2022-03-15 20:44:07,674 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [2065233136] [2022-03-15 20:44:07,674 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 20:44:07,675 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 20:44:07,680 INFO L252 McrAutomatonBuilder]: Finished intersection with 33 states and 51 transitions. [2022-03-15 20:44:07,680 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 20:44:07,991 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 15 new interpolants: [691#(or (<= (* 3 n) (+ 3 i2)) (<= (* 3 n) (+ 2 i1)) (< (+ 3 i1) (* 3 n))), 678#(< i1 (* 3 n)), 690#(or (<= (* 3 n) i2) (<= (* 3 n) (+ 2 i1)) (< (+ 3 i1) (* 3 n))), 687#(or (<= (* 3 n) (+ 2 i1)) (< (+ 3 i1) (* 3 n))), 686#(or (<= (* 3 n) (+ i1 1)) (<= (* 3 n) (+ 3 i2)) (< (+ 2 i1) (* 3 n))), 692#(or (<= (* 3 n) (+ 3 i2)) (< (+ 6 i2) (* 3 n))), 688#(< i2 (* 3 n)), 683#(or (<= (* 3 n) (+ 3 i2)) (< i1 (* 3 n))), 679#(or (< (+ i1 1) (* 3 n)) (<= (* 3 n) i1)), 681#(or (<= (* 3 n) i2) (< i1 (* 3 n))), 682#(or (<= (* 3 n) i2) (< (+ i1 1) (* 3 n)) (<= (* 3 n) i1)), 689#(or (<= (* 3 n) i2) (< (+ 3 i2) (* 3 n))), 684#(or (< (+ i1 1) (* 3 n)) (<= (* 3 n) (+ 3 i2)) (<= (* 3 n) i1)), 685#(or (<= (* 3 n) i2) (<= (* 3 n) (+ i1 1)) (< (+ 2 i1) (* 3 n))), 680#(or (<= (* 3 n) (+ i1 1)) (< (+ 2 i1) (* 3 n)))] [2022-03-15 20:44:07,992 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2022-03-15 20:44:07,992 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 20:44:07,992 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2022-03-15 20:44:07,992 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=141, Invalid=615, Unknown=0, NotChecked=0, Total=756 [2022-03-15 20:44:07,992 INFO L87 Difference]: Start difference. First operand 48 states and 109 transitions. Second operand has 23 states, 23 states have (on average 2.0434782608695654) internal successors, (47), 22 states have internal predecessors, (47), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:44:09,313 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 20:44:09,313 INFO L93 Difference]: Finished difference Result 185 states and 446 transitions. [2022-03-15 20:44:09,314 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 56 states. [2022-03-15 20:44:09,314 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 23 states have (on average 2.0434782608695654) internal successors, (47), 22 states have internal predecessors, (47), 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 20:44:09,314 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 20:44:09,315 INFO L225 Difference]: With dead ends: 185 [2022-03-15 20:44:09,315 INFO L226 Difference]: Without dead ends: 174 [2022-03-15 20:44:09,316 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 99 GetRequests, 23 SyntacticMatches, 1 SemanticMatches, 75 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1715 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=1428, Invalid=4424, Unknown=0, NotChecked=0, Total=5852 [2022-03-15 20:44:09,317 INFO L933 BasicCegarLoop]: 1 mSDtfsCounter, 205 mSDsluCounter, 70 mSDsCounter, 0 mSdLazyCounter, 281 mSolverCounterSat, 276 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 205 SdHoareTripleChecker+Valid, 1 SdHoareTripleChecker+Invalid, 557 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 276 IncrementalHoareTripleChecker+Valid, 281 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-03-15 20:44:09,317 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [205 Valid, 1 Invalid, 557 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [276 Valid, 281 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-03-15 20:44:09,317 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 174 states. [2022-03-15 20:44:09,329 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 174 to 109. [2022-03-15 20:44:09,329 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 109 states, 108 states have (on average 2.935185185185185) internal successors, (317), 108 states have internal predecessors, (317), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:44:09,330 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 109 states to 109 states and 317 transitions. [2022-03-15 20:44:09,330 INFO L78 Accepts]: Start accepts. Automaton has 109 states and 317 transitions. Word has length 13 [2022-03-15 20:44:09,330 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 20:44:09,330 INFO L470 AbstractCegarLoop]: Abstraction has 109 states and 317 transitions. [2022-03-15 20:44:09,330 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 2.0434782608695654) internal successors, (47), 22 states have internal predecessors, (47), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:44:09,330 INFO L276 IsEmpty]: Start isEmpty. Operand 109 states and 317 transitions. [2022-03-15 20:44:09,331 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2022-03-15 20:44:09,331 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 20:44:09,331 INFO L514 BasicCegarLoop]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 20:44:09,358 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 20:44:09,547 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 20:44:09,547 INFO L402 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION] === [2022-03-15 20:44:09,547 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 20:44:09,547 INFO L85 PathProgramCache]: Analyzing trace with hash -1354054747, now seen corresponding path program 4 times [2022-03-15 20:44:09,548 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 20:44:09,548 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [623687103] [2022-03-15 20:44:09,548 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 20:44:09,548 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 20:44:09,555 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 20:44:09,587 INFO L134 CoverageAnalysis]: Checked inductivity of 11 backedges. 3 proven. 8 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 20:44:09,587 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 20:44:09,587 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [623687103] [2022-03-15 20:44:09,587 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [623687103] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-15 20:44:09,587 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1230279377] [2022-03-15 20:44:09,587 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-03-15 20:44:09,588 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 20:44:09,588 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 20:44:09,604 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-15 20:44:09,623 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-03-15 20:44:09,624 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-15 20:44:09,624 INFO L263 TraceCheckSpWp]: Trace formula consists of 50 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-15 20:44:09,625 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-15 20:44:09,639 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2022-03-15 20:44:09,650 INFO L134 CoverageAnalysis]: Checked inductivity of 11 backedges. 6 proven. 5 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 20:44:09,650 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-15 20:44:09,720 INFO L134 CoverageAnalysis]: Checked inductivity of 11 backedges. 6 proven. 5 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 20:44:09,720 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1230279377] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-15 20:44:09,720 INFO L191 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-03-15 20:44:09,720 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 12 [2022-03-15 20:44:09,720 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [1746811382] [2022-03-15 20:44:09,720 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 20:44:09,721 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 20:44:09,723 INFO L252 McrAutomatonBuilder]: Finished intersection with 31 states and 47 transitions. [2022-03-15 20:44:09,723 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 20:44:10,095 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 16 new interpolants: [1282#(or (< (+ i1 1) (* 3 n)) (<= (* 3 n) i1)), 1286#(or (<= (* 3 n) (+ i1 1)) (< i2 (* 3 n)) (< (+ 2 i1) (* 3 n))), 1281#(or (<= (+ i2 4) (* 3 n)) (< i1 (* 3 n))), 1290#(or (<= (* 3 n) (+ 2 i1)) (<= (+ i2 4) (* 3 n)) (< (+ 3 i1) (* 3 n))), 1287#(or (<= (* 3 n) (+ i1 1)) (<= (+ i2 4) (* 3 n)) (< (+ 2 i1) (* 3 n))), 1288#(or (<= (* 3 n) (+ 2 i1)) (< (+ 3 i1) (* 3 n))), 1292#(or (<= (* 3 n) i2) (<= (+ i2 4) (* 3 n))), 1291#(or (<= (* 3 n) (+ 3 i1)) (< (+ i1 4) (* 3 n))), 1294#(or (<= (* 3 n) (+ 3 i1)) (<= (+ i2 4) (* 3 n)) (< (+ i1 4) (* 3 n))), 1289#(or (< i2 (* 3 n)) (<= (* 3 n) (+ 2 i1)) (< (+ 3 i1) (* 3 n))), 1293#(or (<= (* 3 n) (+ 3 i1)) (< i2 (* 3 n)) (< (+ i1 4) (* 3 n))), 1284#(or (< (+ i1 1) (* 3 n)) (<= (+ i2 4) (* 3 n)) (<= (* 3 n) i1)), 1280#(or (< i2 (* 3 n)) (< i1 (* 3 n))), 1279#(< i1 (* 3 n)), 1283#(or (< (+ i1 1) (* 3 n)) (< i2 (* 3 n)) (<= (* 3 n) i1)), 1285#(or (<= (* 3 n) (+ i1 1)) (< (+ 2 i1) (* 3 n)))] [2022-03-15 20:44:10,096 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2022-03-15 20:44:10,096 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 20:44:10,096 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2022-03-15 20:44:10,097 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=171, Invalid=641, Unknown=0, NotChecked=0, Total=812 [2022-03-15 20:44:10,097 INFO L87 Difference]: Start difference. First operand 109 states and 317 transitions. Second operand has 24 states, 24 states have (on average 1.9166666666666667) internal successors, (46), 23 states have internal predecessors, (46), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:44:11,255 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 20:44:11,255 INFO L93 Difference]: Finished difference Result 252 states and 665 transitions. [2022-03-15 20:44:11,255 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 66 states. [2022-03-15 20:44:11,255 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 24 states have (on average 1.9166666666666667) internal successors, (46), 23 states have internal predecessors, (46), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 13 [2022-03-15 20:44:11,256 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 20:44:11,257 INFO L225 Difference]: With dead ends: 252 [2022-03-15 20:44:11,257 INFO L226 Difference]: Without dead ends: 250 [2022-03-15 20:44:11,258 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 102 GetRequests, 18 SyntacticMatches, 3 SemanticMatches, 81 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2040 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=1105, Invalid=5701, Unknown=0, NotChecked=0, Total=6806 [2022-03-15 20:44:11,259 INFO L933 BasicCegarLoop]: 1 mSDtfsCounter, 169 mSDsluCounter, 67 mSDsCounter, 0 mSdLazyCounter, 402 mSolverCounterSat, 169 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 169 SdHoareTripleChecker+Valid, 1 SdHoareTripleChecker+Invalid, 571 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 169 IncrementalHoareTripleChecker+Valid, 402 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-03-15 20:44:11,259 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [169 Valid, 1 Invalid, 571 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [169 Valid, 402 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-03-15 20:44:11,260 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 250 states. [2022-03-15 20:44:11,268 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 250 to 157. [2022-03-15 20:44:11,268 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 157 states, 156 states have (on average 2.871794871794872) internal successors, (448), 156 states have internal predecessors, (448), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:44:11,269 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 157 states to 157 states and 448 transitions. [2022-03-15 20:44:11,269 INFO L78 Accepts]: Start accepts. Automaton has 157 states and 448 transitions. Word has length 13 [2022-03-15 20:44:11,269 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 20:44:11,269 INFO L470 AbstractCegarLoop]: Abstraction has 157 states and 448 transitions. [2022-03-15 20:44:11,269 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 24 states have (on average 1.9166666666666667) internal successors, (46), 23 states have internal predecessors, (46), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:44:11,269 INFO L276 IsEmpty]: Start isEmpty. Operand 157 states and 448 transitions. [2022-03-15 20:44:11,270 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2022-03-15 20:44:11,270 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 20:44:11,270 INFO L514 BasicCegarLoop]: trace histogram [5, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 20:44:11,297 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2022-03-15 20:44:11,490 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 20:44:11,490 INFO L402 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION] === [2022-03-15 20:44:11,490 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 20:44:11,491 INFO L85 PathProgramCache]: Analyzing trace with hash -1191960106, now seen corresponding path program 5 times [2022-03-15 20:44:11,492 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 20:44:11,492 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1317966776] [2022-03-15 20:44:11,492 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 20:44:11,492 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 20:44:11,498 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 20:44:11,547 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 20:44:11,548 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 20:44:11,548 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1317966776] [2022-03-15 20:44:11,548 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1317966776] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-15 20:44:11,551 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [442646568] [2022-03-15 20:44:11,551 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2022-03-15 20:44:11,551 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 20:44:11,552 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 20:44:11,553 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-15 20:44:11,553 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2022-03-15 20:44:11,585 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 5 check-sat command(s) [2022-03-15 20:44:11,585 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-15 20:44:11,585 INFO L263 TraceCheckSpWp]: Trace formula consists of 55 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-15 20:44:11,586 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-15 20:44:11,629 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 6 proven. 9 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2022-03-15 20:44:11,629 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-15 20:44:11,702 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 6 proven. 9 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2022-03-15 20:44:11,703 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [442646568] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-15 20:44:11,703 INFO L191 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-03-15 20:44:11,703 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 6, 6] total 14 [2022-03-15 20:44:11,703 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [466047214] [2022-03-15 20:44:11,703 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 20:44:11,704 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 20:44:11,706 INFO L252 McrAutomatonBuilder]: Finished intersection with 35 states and 54 transitions. [2022-03-15 20:44:11,706 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 20:44:12,024 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 13 new interpolants: [2069#(or (<= (* 3 n) i2) (<= (+ 5 i2) (* 3 n))), 2072#(or (<= (* 3 n) i2) (<= (+ 2 i2) i1)), 2071#(or (<= (* 3 n) i2) (<= (+ 3 i2) i1)), 2003#(< i2 (* 3 n)), 2063#(or (< (+ i1 1) (* 3 n)) (<= (* 3 n) i1)), 2068#(or (<= (* 3 n) i2) (< (+ 3 i2) (* 3 n))), 2062#(< i1 (* 3 n)), 2065#(or (<= (* 3 n) (+ 2 i1)) (< (+ 3 i1) (* 3 n))), 2067#(or (< (+ 5 i1) (* 3 n)) (<= (* 3 n) (+ i1 4))), 2064#(or (<= (* 3 n) (+ i1 1)) (< (+ 2 i1) (* 3 n))), 2073#(or (<= (* 3 n) i2) (<= (+ i2 1) i1)), 2070#(or (<= (* 3 n) i2) (<= (+ i2 4) i1)), 2066#(or (<= (* 3 n) (+ 3 i1)) (< (+ i1 4) (* 3 n)))] [2022-03-15 20:44:12,025 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2022-03-15 20:44:12,025 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 20:44:12,025 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2022-03-15 20:44:12,025 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=112, Invalid=590, Unknown=0, NotChecked=0, Total=702 [2022-03-15 20:44:12,025 INFO L87 Difference]: Start difference. First operand 157 states and 448 transitions. Second operand has 22 states, 22 states have (on average 2.090909090909091) internal successors, (46), 21 states have internal predecessors, (46), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:44:13,803 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 20:44:13,803 INFO L93 Difference]: Finished difference Result 413 states and 926 transitions. [2022-03-15 20:44:13,803 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 74 states. [2022-03-15 20:44:13,804 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 22 states have (on average 2.090909090909091) internal successors, (46), 21 states have internal predecessors, (46), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 14 [2022-03-15 20:44:13,804 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 20:44:13,805 INFO L225 Difference]: With dead ends: 413 [2022-03-15 20:44:13,805 INFO L226 Difference]: Without dead ends: 413 [2022-03-15 20:44:13,807 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 121 GetRequests, 28 SyntacticMatches, 1 SemanticMatches, 92 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2642 ImplicationChecksByTransitivity, 1.7s TimeCoverageRelationStatistics Valid=1597, Invalid=7145, Unknown=0, NotChecked=0, Total=8742 [2022-03-15 20:44:13,807 INFO L933 BasicCegarLoop]: 1 mSDtfsCounter, 267 mSDsluCounter, 126 mSDsCounter, 0 mSdLazyCounter, 468 mSolverCounterSat, 228 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 267 SdHoareTripleChecker+Valid, 1 SdHoareTripleChecker+Invalid, 696 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 228 IncrementalHoareTripleChecker+Valid, 468 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-03-15 20:44:13,807 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [267 Valid, 1 Invalid, 696 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [228 Valid, 468 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-03-15 20:44:13,808 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 413 states. [2022-03-15 20:44:13,828 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 413 to 171. [2022-03-15 20:44:13,828 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 171 states, 170 states have (on average 2.735294117647059) internal successors, (465), 170 states have internal predecessors, (465), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:44:13,829 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 171 states to 171 states and 465 transitions. [2022-03-15 20:44:13,829 INFO L78 Accepts]: Start accepts. Automaton has 171 states and 465 transitions. Word has length 14 [2022-03-15 20:44:13,829 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 20:44:13,829 INFO L470 AbstractCegarLoop]: Abstraction has 171 states and 465 transitions. [2022-03-15 20:44:13,829 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 22 states have (on average 2.090909090909091) internal successors, (46), 21 states have internal predecessors, (46), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:44:13,829 INFO L276 IsEmpty]: Start isEmpty. Operand 171 states and 465 transitions. [2022-03-15 20:44:13,830 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2022-03-15 20:44:13,830 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 20:44:13,830 INFO L514 BasicCegarLoop]: trace histogram [6, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 20:44:13,863 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2022-03-15 20:44:14,063 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 20:44:14,064 INFO L402 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION] === [2022-03-15 20:44:14,064 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 20:44:14,064 INFO L85 PathProgramCache]: Analyzing trace with hash -65542639, now seen corresponding path program 6 times [2022-03-15 20:44:14,065 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 20:44:14,065 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [656443891] [2022-03-15 20:44:14,065 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 20:44:14,065 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 20:44:14,078 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 20:44:14,153 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 16 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 20:44:14,154 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 20:44:14,154 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [656443891] [2022-03-15 20:44:14,154 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [656443891] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-15 20:44:14,154 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [796277] [2022-03-15 20:44:14,154 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-03-15 20:44:14,154 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 20:44:14,154 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 20:44:14,171 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-15 20:44:14,172 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2022-03-15 20:44:14,201 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2022-03-15 20:44:14,201 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-15 20:44:14,201 INFO L263 TraceCheckSpWp]: Trace formula consists of 60 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-15 20:44:14,203 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-15 20:44:14,234 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 18 proven. 1 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2022-03-15 20:44:14,234 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-15 20:44:14,283 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 18 proven. 1 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2022-03-15 20:44:14,283 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [796277] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-15 20:44:14,283 INFO L191 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-03-15 20:44:14,284 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 7, 7] total 14 [2022-03-15 20:44:14,284 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [537951883] [2022-03-15 20:44:14,284 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 20:44:14,285 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 20:44:14,289 INFO L252 McrAutomatonBuilder]: Finished intersection with 39 states and 61 transitions. [2022-03-15 20:44:14,289 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 20:44:14,661 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 12 new interpolants: [3070#(or (<= (* 3 n) i2) (< (+ 3 i2) (* 3 n)) (<= (+ (* 3 n) 1) i1)), 3066#(or (<= (* 3 n) (+ i1 1)) (< i2 (* 3 n))), 3073#(or (<= (* 3 n) i2) (< (+ 3 i2) (* 3 n)) (<= (* 3 n) (+ 2 i1))), 3062#(< i2 (* 3 n)), 3064#(or (<= (+ (* 3 n) 1) i1) (< i2 (* 3 n))), 3071#(or (<= (* 3 n) i2) (< (+ 3 i2) (* 3 n)) (<= (* 3 n) i1)), 3063#(or (< i2 (* 3 n)) (<= (+ (* 3 n) 2) i1)), 3065#(or (< i2 (* 3 n)) (<= (* 3 n) i1)), 3067#(or (< i2 (* 3 n)) (<= (* 3 n) (+ 2 i1))), 3069#(or (<= (* 3 n) i2) (< (+ 3 i2) (* 3 n)) (<= (+ (* 3 n) 2) i1)), 3072#(or (<= (* 3 n) i2) (<= (* 3 n) (+ i1 1)) (< (+ 3 i2) (* 3 n))), 3068#(or (<= (* 3 n) i2) (< (+ 3 i2) (* 3 n)))] [2022-03-15 20:44:14,661 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2022-03-15 20:44:14,662 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 20:44:14,662 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2022-03-15 20:44:14,662 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=149, Invalid=553, Unknown=0, NotChecked=0, Total=702 [2022-03-15 20:44:14,662 INFO L87 Difference]: Start difference. First operand 171 states and 465 transitions. Second operand has 22 states, 22 states have (on average 2.227272727272727) internal successors, (49), 21 states have internal predecessors, (49), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:44:14,866 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 20:44:14,866 INFO L93 Difference]: Finished difference Result 193 states and 498 transitions. [2022-03-15 20:44:14,866 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2022-03-15 20:44:14,867 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 22 states have (on average 2.227272727272727) internal successors, (49), 21 states have internal predecessors, (49), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 15 [2022-03-15 20:44:14,867 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 20:44:14,868 INFO L225 Difference]: With dead ends: 193 [2022-03-15 20:44:14,868 INFO L226 Difference]: Without dead ends: 183 [2022-03-15 20:44:14,869 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 70 GetRequests, 34 SyntacticMatches, 1 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 285 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=306, Invalid=1026, Unknown=0, NotChecked=0, Total=1332 [2022-03-15 20:44:14,870 INFO L933 BasicCegarLoop]: 1 mSDtfsCounter, 65 mSDsluCounter, 61 mSDsCounter, 0 mSdLazyCounter, 223 mSolverCounterSat, 43 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 65 SdHoareTripleChecker+Valid, 1 SdHoareTripleChecker+Invalid, 266 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 43 IncrementalHoareTripleChecker+Valid, 223 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-15 20:44:14,871 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [65 Valid, 1 Invalid, 266 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [43 Valid, 223 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-15 20:44:14,871 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 183 states. [2022-03-15 20:44:14,885 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 183 to 171. [2022-03-15 20:44:14,886 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 171 states, 170 states have (on average 2.676470588235294) internal successors, (455), 170 states have internal predecessors, (455), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:44:14,887 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 171 states to 171 states and 455 transitions. [2022-03-15 20:44:14,887 INFO L78 Accepts]: Start accepts. Automaton has 171 states and 455 transitions. Word has length 15 [2022-03-15 20:44:14,887 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 20:44:14,887 INFO L470 AbstractCegarLoop]: Abstraction has 171 states and 455 transitions. [2022-03-15 20:44:14,887 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 22 states have (on average 2.227272727272727) internal successors, (49), 21 states have internal predecessors, (49), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:44:14,887 INFO L276 IsEmpty]: Start isEmpty. Operand 171 states and 455 transitions. [2022-03-15 20:44:14,888 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2022-03-15 20:44:14,888 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 20:44:14,888 INFO L514 BasicCegarLoop]: trace histogram [6, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 20:44:14,906 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2022-03-15 20:44:15,089 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 20:44:15,091 INFO L402 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION] === [2022-03-15 20:44:15,091 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 20:44:15,091 INFO L85 PathProgramCache]: Analyzing trace with hash 806346850, now seen corresponding path program 7 times [2022-03-15 20:44:15,092 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 20:44:15,092 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1671694814] [2022-03-15 20:44:15,092 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 20:44:15,096 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 20:44:15,101 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 20:44:15,139 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 24 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 20:44:15,139 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 20:44:15,140 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1671694814] [2022-03-15 20:44:15,140 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1671694814] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-15 20:44:15,140 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2025789131] [2022-03-15 20:44:15,140 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2022-03-15 20:44:15,140 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 20:44:15,140 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 20:44:15,156 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-15 20:44:15,157 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2022-03-15 20:44:15,176 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 20:44:15,176 INFO L263 TraceCheckSpWp]: Trace formula consists of 65 conjuncts, 23 conjunts are in the unsatisfiable core [2022-03-15 20:44:15,177 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-15 20:44:15,312 INFO L353 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2022-03-15 20:44:15,313 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 6 select indices, 6 select index equivalence classes, 0 disjoint index pairs (out of 15 index pairs), introduced 11 new quantified variables, introduced 15 case distinctions, treesize of input 31 treesize of output 142 [2022-03-15 20:44:15,668 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 24 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 20:44:15,668 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-15 20:44:16,216 INFO L353 Elim1Store]: treesize reduction 30, result has 94.3 percent of original size [2022-03-15 20:44:16,218 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 12 select indices, 12 select index equivalence classes, 0 disjoint index pairs (out of 66 index pairs), introduced 22 new quantified variables, introduced 66 case distinctions, treesize of input 27 treesize of output 542 [2022-03-15 20:46:34,497 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 24 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 20:46:34,497 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2025789131] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-15 20:46:34,497 INFO L191 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-03-15 20:46:34,497 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 9, 8] total 20 [2022-03-15 20:46:34,499 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [1371099626] [2022-03-15 20:46:34,499 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 20:46:34,501 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 20:46:34,504 INFO L252 McrAutomatonBuilder]: Finished intersection with 48 states and 78 transitions. [2022-03-15 20:46:34,504 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 20:46:34,945 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 18 new interpolants: [3743#(= (select f (select f x1)) x2), 3753#(= (select f (select f (select f (select f (select f (select f x2)))))) (select f (select f (select f (select f (select f (select f x1))))))), 3742#(= (select f x1) (select f (select f (select f x2)))), 3718#(= (select f x1) (select f (select f (select f (select f (select f (select f x2))))))), 3745#(= (select f (select f (select f x1))) x2), 3744#(= (select f (select f x1)) (select f (select f (select f x2)))), 3748#(= (select f (select f (select f (select f x1)))) (select f (select f (select f x2)))), 3746#(= (select f (select f (select f x1))) (select f (select f (select f x2)))), 3734#(= (select f (select f (select f (select f (select f (select f x2)))))) (select f (select f (select f (select f (select f x1)))))), 3722#(= (select f (select f x1)) (select f (select f (select f (select f (select f (select f x2))))))), 3726#(= (select f (select f (select f x1))) (select f (select f (select f (select f (select f (select f x2))))))), 3749#(= (select f (select f (select f (select f (select f x1))))) x2), 3751#(= x2 (select f (select f (select f (select f (select f (select f x1))))))), 3730#(= (select f (select f (select f (select f x1)))) (select f (select f (select f (select f (select f (select f x2))))))), 3752#(= (select f (select f (select f x2))) (select f (select f (select f (select f (select f (select f x1))))))), 3747#(= (select f (select f (select f (select f x1)))) x2), 3741#(= (select f x1) x2), 3750#(= (select f (select f (select f (select f (select f x1))))) (select f (select f (select f x2))))] [2022-03-15 20:46:34,945 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2022-03-15 20:46:34,945 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 20:46:34,946 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2022-03-15 20:46:34,946 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=100, Invalid=1090, Unknown=0, NotChecked=0, Total=1190 [2022-03-15 20:46:34,946 INFO L87 Difference]: Start difference. First operand 171 states and 455 transitions. Second operand has 27 states, 26 states have (on average 2.3846153846153846) internal successors, (62), 26 states have internal predecessors, (62), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:46:35,548 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 20:46:35,549 INFO L93 Difference]: Finished difference Result 498 states and 1159 transitions. [2022-03-15 20:46:35,549 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2022-03-15 20:46:35,549 INFO L78 Accepts]: Start accepts. Automaton has has 27 states, 26 states have (on average 2.3846153846153846) internal successors, (62), 26 states have internal predecessors, (62), 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 20:46:35,549 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 20:46:35,551 INFO L225 Difference]: With dead ends: 498 [2022-03-15 20:46:35,551 INFO L226 Difference]: Without dead ends: 495 [2022-03-15 20:46:35,551 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 70 GetRequests, 37 SyntacticMatches, 0 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 309 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=100, Invalid=1090, Unknown=0, NotChecked=0, Total=1190 [2022-03-15 20:46:35,552 INFO L933 BasicCegarLoop]: 1 mSDtfsCounter, 92 mSDsluCounter, 1107 mSDsCounter, 0 mSdLazyCounter, 1932 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 92 SdHoareTripleChecker+Valid, 1 SdHoareTripleChecker+Invalid, 1942 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 1932 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2022-03-15 20:46:35,552 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [92 Valid, 1 Invalid, 1942 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 1932 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2022-03-15 20:46:35,552 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 495 states. [2022-03-15 20:46:35,577 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 495 to 287. [2022-03-15 20:46:35,577 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 287 states, 286 states have (on average 2.8426573426573425) internal successors, (813), 286 states have internal predecessors, (813), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:46:35,578 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 287 states to 287 states and 813 transitions. [2022-03-15 20:46:35,578 INFO L78 Accepts]: Start accepts. Automaton has 287 states and 813 transitions. Word has length 16 [2022-03-15 20:46:35,578 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 20:46:35,578 INFO L470 AbstractCegarLoop]: Abstraction has 287 states and 813 transitions. [2022-03-15 20:46:35,578 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 26 states have (on average 2.3846153846153846) internal successors, (62), 26 states have internal predecessors, (62), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:46:35,578 INFO L276 IsEmpty]: Start isEmpty. Operand 287 states and 813 transitions. [2022-03-15 20:46:35,580 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2022-03-15 20:46:35,580 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 20:46:35,580 INFO L514 BasicCegarLoop]: trace histogram [6, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 20:46:35,600 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2022-03-15 20:46:35,780 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 20:46:35,781 INFO L402 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION] === [2022-03-15 20:46:35,781 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 20:46:35,781 INFO L85 PathProgramCache]: Analyzing trace with hash -772307611, now seen corresponding path program 8 times [2022-03-15 20:46:35,782 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 20:46:35,782 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1406548029] [2022-03-15 20:46:35,782 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 20:46:35,782 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 20:46:35,789 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 20:46:35,878 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 6 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 20:46:35,878 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 20:46:35,878 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1406548029] [2022-03-15 20:46:35,878 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1406548029] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-15 20:46:35,878 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [458247243] [2022-03-15 20:46:35,878 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-15 20:46:35,878 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 20:46:35,878 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 20:46:35,879 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-15 20:46:35,880 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2022-03-15 20:46:35,904 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-15 20:46:35,904 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-15 20:46:35,904 INFO L263 TraceCheckSpWp]: Trace formula consists of 70 conjuncts, 11 conjunts are in the unsatisfiable core [2022-03-15 20:46:35,905 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-15 20:46:35,933 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 6 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 20:46:35,934 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-15 20:46:36,045 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 6 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 20:46:36,045 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [458247243] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-15 20:46:36,045 INFO L191 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-03-15 20:46:36,046 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11, 11] total 19 [2022-03-15 20:46:36,046 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [219539047] [2022-03-15 20:46:36,046 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 20:46:36,047 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 20:46:36,051 INFO L252 McrAutomatonBuilder]: Finished intersection with 57 states and 95 transitions. [2022-03-15 20:46:36,051 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 20:46:36,983 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 32 new interpolants: [4951#(or (<= (* 3 n) i2) (<= (* 3 n) (+ 2 i1)) (< (+ 3 i1) (* 3 n))), 4970#(or (<= (* 3 n) (+ 3 i2)) (< (+ 5 i1) (* 3 n)) (<= (* 3 n) (+ i1 4))), 4956#(< i2 (* 3 n)), 4944#(or (<= (* 3 n) (+ i1 1)) (< (+ 2 i1) (* 3 n))), 4957#(or (<= (* 3 n) i2) (< (+ 3 i2) (* 3 n))), 4971#(or (<= (* 3 n) (+ 5 i1)) (<= (* 3 n) (+ 3 i2)) (< (+ 6 i1) (* 3 n))), 4952#(or (<= (* 3 n) i2) (<= (* 3 n) (+ 3 i1)) (< (+ i1 4) (* 3 n))), 4965#(or (< (+ i1 1) (* 3 n)) (<= (* 3 n) (+ 6 i2)) (<= (* 3 n) i1)), 4954#(or (<= (* 3 n) (+ 5 i1)) (< (+ 6 i1) (* 3 n))), 4953#(or (<= (* 3 n) i2) (< (+ 5 i1) (* 3 n)) (<= (* 3 n) (+ i1 4))), 4960#(or (<= (* 3 n) (+ 3 i2)) (< i1 (* 3 n))), 4969#(or (<= (* 3 n) (+ 3 i1)) (<= (* 3 n) (+ 6 i2)) (< (+ i1 4) (* 3 n))), 4961#(or (< (+ i1 1) (* 3 n)) (<= (* 3 n) (+ 3 i2)) (<= (* 3 n) i1)), 4945#(or (<= (* 3 n) (+ 2 i1)) (< (+ 3 i1) (* 3 n))), 4946#(or (<= (* 3 n) (+ 3 i1)) (< (+ i1 4) (* 3 n))), 4947#(or (< (+ 5 i1) (* 3 n)) (<= (* 3 n) (+ i1 4))), 4967#(or (<= (* 3 n) (+ 2 i1)) (<= (* 3 n) (+ 6 i2)) (< (+ 3 i1) (* 3 n))), 4964#(or (<= (* 3 n) (+ 6 i2)) (< i1 (* 3 n))), 4963#(or (<= (* 3 n) (+ 3 i2)) (<= (* 3 n) (+ 2 i1)) (< (+ 3 i1) (* 3 n))), 4968#(or (<= (* 3 n) (+ 3 i1)) (<= (* 3 n) (+ 3 i2)) (< (+ i1 4) (* 3 n))), 4966#(or (<= (* 3 n) (+ i1 1)) (<= (* 3 n) (+ 6 i2)) (< (+ 2 i1) (* 3 n))), 4955#(or (<= (* 3 n) i2) (<= (* 3 n) (+ 5 i1)) (< (+ 6 i1) (* 3 n))), 4958#(or (<= (* 3 n) (+ 3 i2)) (< (+ 6 i2) (* 3 n))), 4950#(or (<= (* 3 n) i2) (<= (* 3 n) (+ i1 1)) (< (+ 2 i1) (* 3 n))), 4943#(or (< (+ i1 1) (* 3 n)) (<= (* 3 n) i1)), 4962#(or (<= (* 3 n) (+ i1 1)) (<= (* 3 n) (+ 3 i2)) (< (+ 2 i1) (* 3 n))), 4948#(or (<= (* 3 n) i2) (< i1 (* 3 n))), 4973#(or (<= (* 3 n) (+ 5 i1)) (<= (* 3 n) (+ 6 i2)) (< (+ 6 i1) (* 3 n))), 4949#(or (<= (* 3 n) i2) (< (+ i1 1) (* 3 n)) (<= (* 3 n) i1)), 4972#(or (< (+ 5 i1) (* 3 n)) (<= (* 3 n) (+ 6 i2)) (<= (* 3 n) (+ i1 4))), 4942#(< i1 (* 3 n)), 4959#(or (<= (* 3 n) (+ 6 i2)) (< (+ 9 i2) (* 3 n)))] [2022-03-15 20:46:36,983 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 44 states [2022-03-15 20:46:36,983 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 20:46:36,984 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 44 interpolants. [2022-03-15 20:46:36,984 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=383, Invalid=2269, Unknown=0, NotChecked=0, Total=2652 [2022-03-15 20:46:36,984 INFO L87 Difference]: Start difference. First operand 287 states and 813 transitions. Second operand has 44 states, 44 states have (on average 2.0) internal successors, (88), 43 states have internal predecessors, (88), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:46:48,061 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 20:46:48,061 INFO L93 Difference]: Finished difference Result 1900 states and 5765 transitions. [2022-03-15 20:46:48,061 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 290 states. [2022-03-15 20:46:48,062 INFO L78 Accepts]: Start accepts. Automaton has has 44 states, 44 states have (on average 2.0) internal successors, (88), 43 states have internal predecessors, (88), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 17 [2022-03-15 20:46:48,062 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 20:46:48,069 INFO L225 Difference]: With dead ends: 1900 [2022-03-15 20:46:48,069 INFO L226 Difference]: Without dead ends: 1865 [2022-03-15 20:46:48,079 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 358 GetRequests, 31 SyntacticMatches, 1 SemanticMatches, 326 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 50616 ImplicationChecksByTransitivity, 10.7s TimeCoverageRelationStatistics Valid=28993, Invalid=78263, Unknown=0, NotChecked=0, Total=107256 [2022-03-15 20:46:48,079 INFO L933 BasicCegarLoop]: 1 mSDtfsCounter, 691 mSDsluCounter, 133 mSDsCounter, 0 mSdLazyCounter, 693 mSolverCounterSat, 1038 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 691 SdHoareTripleChecker+Valid, 1 SdHoareTripleChecker+Invalid, 1731 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1038 IncrementalHoareTripleChecker+Valid, 693 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2022-03-15 20:46:48,080 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [691 Valid, 1 Invalid, 1731 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1038 Valid, 693 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2022-03-15 20:46:48,081 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1865 states. [2022-03-15 20:46:48,104 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1865 to 1133. [2022-03-15 20:46:48,106 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1133 states, 1132 states have (on average 3.2985865724381624) internal successors, (3734), 1132 states have internal predecessors, (3734), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:46:48,109 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1133 states to 1133 states and 3734 transitions. [2022-03-15 20:46:48,109 INFO L78 Accepts]: Start accepts. Automaton has 1133 states and 3734 transitions. Word has length 17 [2022-03-15 20:46:48,110 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 20:46:48,110 INFO L470 AbstractCegarLoop]: Abstraction has 1133 states and 3734 transitions. [2022-03-15 20:46:48,110 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 44 states, 44 states have (on average 2.0) internal successors, (88), 43 states have internal predecessors, (88), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:46:48,110 INFO L276 IsEmpty]: Start isEmpty. Operand 1133 states and 3734 transitions. [2022-03-15 20:46:48,112 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2022-03-15 20:46:48,112 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 20:46:48,112 INFO L514 BasicCegarLoop]: trace histogram [7, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 20:46:48,129 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2022-03-15 20:46:48,327 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 20:46:48,328 INFO L402 AbstractCegarLoop]: === Iteration 11 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION] === [2022-03-15 20:46:48,328 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 20:46:48,328 INFO L85 PathProgramCache]: Analyzing trace with hash 1655482193, now seen corresponding path program 9 times [2022-03-15 20:46:48,329 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 20:46:48,329 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1391978092] [2022-03-15 20:46:48,329 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 20:46:48,329 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 20:46:48,338 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 20:46:48,417 INFO L134 CoverageAnalysis]: Checked inductivity of 31 backedges. 15 proven. 16 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 20:46:48,417 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 20:46:48,417 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1391978092] [2022-03-15 20:46:48,417 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1391978092] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-15 20:46:48,417 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1432457176] [2022-03-15 20:46:48,417 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-03-15 20:46:48,417 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 20:46:48,418 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 20:46:48,419 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-15 20:46:48,420 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2022-03-15 20:46:48,448 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2022-03-15 20:46:48,448 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-15 20:46:48,449 INFO L263 TraceCheckSpWp]: Trace formula consists of 70 conjuncts, 11 conjunts are in the unsatisfiable core [2022-03-15 20:46:48,450 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-15 20:46:48,488 INFO L134 CoverageAnalysis]: Checked inductivity of 31 backedges. 21 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 20:46:48,488 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-15 20:46:48,596 INFO L134 CoverageAnalysis]: Checked inductivity of 31 backedges. 21 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 20:46:48,596 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1432457176] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-15 20:46:48,596 INFO L191 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-03-15 20:46:48,596 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11, 11] total 19 [2022-03-15 20:46:48,597 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [1522999240] [2022-03-15 20:46:48,597 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 20:46:48,598 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 20:46:48,604 INFO L252 McrAutomatonBuilder]: Finished intersection with 53 states and 87 transitions. [2022-03-15 20:46:48,604 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 20:46:49,391 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 34 new interpolants: [9811#(or (< i2 (* 3 n)) (< i1 (* 3 n))), 9838#(or (<= (* 3 n) (+ 3 i2)) (<= (+ 7 i2) (* 3 n))), 9822#(or (< (+ i1 1) (* 3 n)) (<= (+ i2 4) (* 3 n)) (<= (* 3 n) i1)), 9829#(or (<= (* 3 n) (+ 2 i1)) (< (+ 3 i1) (* 3 n)) (<= (+ 7 i2) (* 3 n))), 9817#(or (<= (* 3 n) (+ 3 i1)) (< (+ i1 4) (* 3 n))), 9828#(or (<= (* 3 n) (+ i1 1)) (< (+ 2 i1) (* 3 n)) (<= (+ 7 i2) (* 3 n))), 9833#(or (<= (* 3 n) (+ 5 i1)) (< (+ 6 i1) (* 3 n))), 9816#(or (< i2 (* 3 n)) (<= (* 3 n) (+ 2 i1)) (< (+ 3 i1) (* 3 n))), 9823#(or (<= (* 3 n) (+ i1 1)) (<= (+ i2 4) (* 3 n)) (< (+ 2 i1) (* 3 n))), 9810#(or (< (+ i1 1) (* 3 n)) (<= (* 3 n) i1)), 9812#(or (< (+ i1 1) (* 3 n)) (< i2 (* 3 n)) (<= (* 3 n) i1)), 9824#(or (<= (* 3 n) (+ 2 i1)) (<= (+ i2 4) (* 3 n)) (< (+ 3 i1) (* 3 n))), 9834#(or (<= (* 3 n) (+ 5 i1)) (< i2 (* 3 n)) (< (+ 6 i1) (* 3 n))), 9825#(or (<= (* 3 n) (+ 3 i1)) (<= (+ i2 4) (* 3 n)) (< (+ i1 4) (* 3 n))), 9835#(or (<= (* 3 n) (+ 5 i1)) (<= (+ i2 4) (* 3 n)) (< (+ 6 i1) (* 3 n))), 9831#(or (< (+ 5 i1) (* 3 n)) (<= (+ i2 4) (* 3 n)) (<= (* 3 n) (+ i1 4))), 9808#(or (<= (* 3 n) i2) (<= (+ i2 4) (* 3 n))), 9821#(or (<= (+ i2 4) (* 3 n)) (< i1 (* 3 n))), 9840#(or (< (+ 7 i1) (* 3 n)) (<= (+ i2 4) (* 3 n)) (<= (* 3 n) (+ 6 i1))), 9818#(or (< (+ 5 i1) (* 3 n)) (<= (* 3 n) (+ i1 4))), 9830#(or (<= (* 3 n) (+ 3 i1)) (<= (+ 7 i2) (* 3 n)) (< (+ i1 4) (* 3 n))), 9819#(or (<= (* 3 n) (+ 3 i1)) (< i2 (* 3 n)) (< (+ i1 4) (* 3 n))), 9827#(or (< (+ i1 1) (* 3 n)) (<= (* 3 n) i1) (<= (+ 7 i2) (* 3 n))), 9820#(or (< (+ 5 i1) (* 3 n)) (< i2 (* 3 n)) (<= (* 3 n) (+ i1 4))), 9832#(or (< (+ 5 i1) (* 3 n)) (<= (+ 7 i2) (* 3 n)) (<= (* 3 n) (+ i1 4))), 9813#(or (<= (* 3 n) (+ i1 1)) (< (+ 2 i1) (* 3 n))), 9826#(or (<= (+ 7 i2) (* 3 n)) (< i1 (* 3 n))), 9809#(< i1 (* 3 n)), 9839#(or (< (+ 7 i1) (* 3 n)) (< i2 (* 3 n)) (<= (* 3 n) (+ 6 i1))), 9814#(or (<= (* 3 n) (+ i1 1)) (< i2 (* 3 n)) (< (+ 2 i1) (* 3 n))), 9841#(or (< (+ 7 i1) (* 3 n)) (<= (+ 7 i2) (* 3 n)) (<= (* 3 n) (+ 6 i1))), 9815#(or (<= (* 3 n) (+ 2 i1)) (< (+ 3 i1) (* 3 n))), 9836#(or (<= (* 3 n) (+ 5 i1)) (<= (+ 7 i2) (* 3 n)) (< (+ 6 i1) (* 3 n))), 9837#(or (< (+ 7 i1) (* 3 n)) (<= (* 3 n) (+ 6 i1)))] [2022-03-15 20:46:49,392 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 46 states [2022-03-15 20:46:49,392 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 20:46:49,392 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 46 interpolants. [2022-03-15 20:46:49,393 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=546, Invalid=2316, Unknown=0, NotChecked=0, Total=2862 [2022-03-15 20:46:49,393 INFO L87 Difference]: Start difference. First operand 1133 states and 3734 transitions. Second operand has 46 states, 46 states have (on average 1.8695652173913044) internal successors, (86), 45 states have internal predecessors, (86), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:46:56,106 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 20:46:56,106 INFO L93 Difference]: Finished difference Result 2533 states and 7496 transitions. [2022-03-15 20:46:56,106 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 251 states. [2022-03-15 20:46:56,106 INFO L78 Accepts]: Start accepts. Automaton has has 46 states, 46 states have (on average 1.8695652173913044) internal successors, (86), 45 states have internal predecessors, (86), 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 20:46:56,106 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 20:46:56,115 INFO L225 Difference]: With dead ends: 2533 [2022-03-15 20:46:56,115 INFO L226 Difference]: Without dead ends: 2531 [2022-03-15 20:46:56,119 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 314 GetRequests, 23 SyntacticMatches, 3 SemanticMatches, 288 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 34941 ImplicationChecksByTransitivity, 6.6s TimeCoverageRelationStatistics Valid=10746, Invalid=73064, Unknown=0, NotChecked=0, Total=83810 [2022-03-15 20:46:56,119 INFO L933 BasicCegarLoop]: 1 mSDtfsCounter, 540 mSDsluCounter, 111 mSDsCounter, 0 mSdLazyCounter, 874 mSolverCounterSat, 790 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 540 SdHoareTripleChecker+Valid, 1 SdHoareTripleChecker+Invalid, 1664 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 790 IncrementalHoareTripleChecker+Valid, 874 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2022-03-15 20:46:56,119 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [540 Valid, 1 Invalid, 1664 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [790 Valid, 874 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2022-03-15 20:46:56,122 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2531 states. [2022-03-15 20:46:56,145 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2531 to 1584. [2022-03-15 20:46:56,147 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1584 states, 1583 states have (on average 3.22236260265319) internal successors, (5101), 1583 states have internal predecessors, (5101), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:46:56,151 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1584 states to 1584 states and 5101 transitions. [2022-03-15 20:46:56,151 INFO L78 Accepts]: Start accepts. Automaton has 1584 states and 5101 transitions. Word has length 17 [2022-03-15 20:46:56,151 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 20:46:56,151 INFO L470 AbstractCegarLoop]: Abstraction has 1584 states and 5101 transitions. [2022-03-15 20:46:56,151 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 46 states, 46 states have (on average 1.8695652173913044) internal successors, (86), 45 states have internal predecessors, (86), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:46:56,151 INFO L276 IsEmpty]: Start isEmpty. Operand 1584 states and 5101 transitions. [2022-03-15 20:46:56,153 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2022-03-15 20:46:56,154 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 20:46:56,154 INFO L514 BasicCegarLoop]: trace histogram [8, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 20:46:56,172 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2022-03-15 20:46:56,369 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 20:46:56,370 INFO L402 AbstractCegarLoop]: === Iteration 12 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION] === [2022-03-15 20:46:56,370 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 20:46:56,370 INFO L85 PathProgramCache]: Analyzing trace with hash -780403432, now seen corresponding path program 10 times [2022-03-15 20:46:56,371 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 20:46:56,371 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1798161517] [2022-03-15 20:46:56,371 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 20:46:56,371 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 20:46:56,393 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 20:46:56,451 INFO L134 CoverageAnalysis]: Checked inductivity of 39 backedges. 16 proven. 21 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2022-03-15 20:46:56,451 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 20:46:56,451 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1798161517] [2022-03-15 20:46:56,451 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1798161517] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-15 20:46:56,451 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [299247412] [2022-03-15 20:46:56,451 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-03-15 20:46:56,452 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 20:46:56,452 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 20:46:56,453 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-15 20:46:56,454 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2022-03-15 20:46:56,473 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-03-15 20:46:56,474 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-15 20:46:56,474 INFO L263 TraceCheckSpWp]: Trace formula consists of 75 conjuncts, 12 conjunts are in the unsatisfiable core [2022-03-15 20:46:56,475 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-15 20:46:56,502 INFO L134 CoverageAnalysis]: Checked inductivity of 39 backedges. 22 proven. 13 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-15 20:46:56,503 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-15 20:46:56,626 INFO L134 CoverageAnalysis]: Checked inductivity of 39 backedges. 22 proven. 13 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-15 20:46:56,626 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [299247412] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-15 20:46:56,626 INFO L191 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-03-15 20:46:56,626 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 7, 7] total 15 [2022-03-15 20:46:56,626 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [568935852] [2022-03-15 20:46:56,626 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 20:46:56,627 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 20:46:56,632 INFO L252 McrAutomatonBuilder]: Finished intersection with 58 states and 96 transitions. [2022-03-15 20:46:56,632 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 20:46:57,179 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 25 new interpolants: [16142#(or (<= (* 3 n) (+ 3 i2)) (<= (+ 5 i2) i1)), 16133#(or (<= (* 3 n) i2) (< (+ 3 i2) (* 3 n))), 16150#(or (< (+ 5 i1) (* 3 n)) (<= (* 3 n) (+ i1 4))), 16153#(or (<= (* 3 n) (+ 7 i1)) (< (+ i1 8) (* 3 n))), 16138#(or (<= (+ 7 i2) i1) (<= (* 3 n) (+ 3 i2))), 16137#(or (<= (* 3 n) i2) (<= (+ i2 4) i1)), 16139#(or (<= (* 3 n) i2) (<= (+ 3 i2) i1)), 16149#(or (<= (* 3 n) (+ 3 i1)) (< (+ i1 4) (* 3 n))), 16141#(or (<= (* 3 n) i2) (<= (+ 2 i2) i1)), 16145#(< i1 (* 3 n)), 16143#(or (<= (* 3 n) i2) (<= (+ i2 1) i1)), 16146#(or (< (+ i1 1) (* 3 n)) (<= (* 3 n) i1)), 16152#(or (< (+ 7 i1) (* 3 n)) (<= (* 3 n) (+ 6 i1))), 16136#(or (<= (* 3 n) (+ 3 i2)) (<= (+ i2 8) (* 3 n))), 16154#(or (<= i2 (+ i1 4)) (<= (* 3 n) i1)), 16135#(or (<= (* 3 n) (+ 3 i2)) (< (+ 6 i2) (* 3 n))), 16134#(or (<= (* 3 n) i2) (<= (+ 5 i2) (* 3 n))), 16144#(or (<= (+ i2 4) i1) (<= (* 3 n) (+ 3 i2))), 16148#(or (<= (* 3 n) (+ 2 i1)) (< (+ 3 i1) (* 3 n))), 16140#(or (<= (* 3 n) (+ 3 i2)) (<= (+ 6 i2) i1)), 16155#(or (<= (* 3 n) (+ i1 1)) (<= i2 (+ 5 i1))), 16147#(or (<= (* 3 n) (+ i1 1)) (< (+ 2 i1) (* 3 n))), 16151#(or (<= (* 3 n) (+ 5 i1)) (< (+ 6 i1) (* 3 n))), 16156#(or (<= (* 3 n) (+ 2 i1)) (<= i2 (+ 6 i1))), 16088#(< i2 (* 3 n))] [2022-03-15 20:46:57,179 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 35 states [2022-03-15 20:46:57,179 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 20:46:57,180 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 35 interpolants. [2022-03-15 20:46:57,180 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=197, Invalid=1363, Unknown=0, NotChecked=0, Total=1560 [2022-03-15 20:46:57,180 INFO L87 Difference]: Start difference. First operand 1584 states and 5101 transitions. Second operand has 35 states, 35 states have (on average 2.2) internal successors, (77), 34 states have internal predecessors, (77), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:47:03,443 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 20:47:03,443 INFO L93 Difference]: Finished difference Result 3055 states and 8325 transitions. [2022-03-15 20:47:03,443 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 176 states. [2022-03-15 20:47:03,443 INFO L78 Accepts]: Start accepts. Automaton has has 35 states, 35 states have (on average 2.2) internal successors, (77), 34 states have internal predecessors, (77), 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 18 [2022-03-15 20:47:03,445 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 20:47:03,454 INFO L225 Difference]: With dead ends: 3055 [2022-03-15 20:47:03,455 INFO L226 Difference]: Without dead ends: 3055 [2022-03-15 20:47:03,457 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 250 GetRequests, 44 SyntacticMatches, 3 SemanticMatches, 203 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15056 ImplicationChecksByTransitivity, 6.0s TimeCoverageRelationStatistics Valid=6356, Invalid=35464, Unknown=0, NotChecked=0, Total=41820 [2022-03-15 20:47:03,458 INFO L933 BasicCegarLoop]: 1 mSDtfsCounter, 529 mSDsluCounter, 234 mSDsCounter, 0 mSdLazyCounter, 903 mSolverCounterSat, 579 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 529 SdHoareTripleChecker+Valid, 1 SdHoareTripleChecker+Invalid, 1482 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 579 IncrementalHoareTripleChecker+Valid, 903 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2022-03-15 20:47:03,459 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [529 Valid, 1 Invalid, 1482 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [579 Valid, 903 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2022-03-15 20:47:03,461 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3055 states. [2022-03-15 20:47:03,485 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3055 to 1239. [2022-03-15 20:47:03,486 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1239 states, 1238 states have (on average 3.11389337641357) internal successors, (3855), 1238 states have internal predecessors, (3855), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:47:03,489 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1239 states to 1239 states and 3855 transitions. [2022-03-15 20:47:03,489 INFO L78 Accepts]: Start accepts. Automaton has 1239 states and 3855 transitions. Word has length 18 [2022-03-15 20:47:03,490 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 20:47:03,490 INFO L470 AbstractCegarLoop]: Abstraction has 1239 states and 3855 transitions. [2022-03-15 20:47:03,490 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 35 states, 35 states have (on average 2.2) internal successors, (77), 34 states have internal predecessors, (77), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:47:03,490 INFO L276 IsEmpty]: Start isEmpty. Operand 1239 states and 3855 transitions. [2022-03-15 20:47:03,492 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2022-03-15 20:47:03,493 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 20:47:03,493 INFO L514 BasicCegarLoop]: trace histogram [9, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 20:47:03,511 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2022-03-15 20:47:03,705 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 20:47:03,706 INFO L402 AbstractCegarLoop]: === Iteration 13 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION] === [2022-03-15 20:47:03,706 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 20:47:03,706 INFO L85 PathProgramCache]: Analyzing trace with hash -438824015, now seen corresponding path program 11 times [2022-03-15 20:47:03,707 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 20:47:03,707 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1956629344] [2022-03-15 20:47:03,707 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 20:47:03,707 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 20:47:03,712 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 20:47:03,825 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 37 proven. 11 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 20:47:03,825 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 20:47:03,826 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1956629344] [2022-03-15 20:47:03,826 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1956629344] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-15 20:47:03,826 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [874227497] [2022-03-15 20:47:03,826 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2022-03-15 20:47:03,826 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 20:47:03,826 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 20:47:03,827 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-15 20:47:03,828 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2022-03-15 20:47:03,851 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2022-03-15 20:47:03,851 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-15 20:47:03,852 INFO L263 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjunts are in the unsatisfiable core [2022-03-15 20:47:03,852 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-15 20:47:03,910 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 42 proven. 3 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2022-03-15 20:47:03,910 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-15 20:47:03,985 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 42 proven. 3 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2022-03-15 20:47:03,986 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [874227497] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-15 20:47:03,986 INFO L191 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-03-15 20:47:03,986 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 11, 11] total 20 [2022-03-15 20:47:03,986 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleMcr [542601847] [2022-03-15 20:47:03,986 INFO L194 McrAutomatonBuilder]: Constructing automaton for MCR equivalence class. [2022-03-15 20:47:03,987 INFO L249 McrAutomatonBuilder]: Started intersection. [2022-03-15 20:47:03,994 INFO L252 McrAutomatonBuilder]: Finished intersection with 63 states and 105 transitions. [2022-03-15 20:47:03,995 INFO L276 McrAutomatonBuilder]: Constructing interpolant automaton by labelling MCR automaton with interpolants from WpInterpolantProvider [2022-03-15 20:47:04,869 INFO L301 McrAutomatonBuilder]: Construction finished. MCR generated 27 new interpolants: [22162#(or (<= (* 3 n) (+ 3 i2)) (< (+ 6 i2) (* 3 n)) (<= (+ (* 3 n) 2) i1)), 22155#(or (<= (* 3 n) i2) (< (+ 3 i2) (* 3 n))), 22170#(or (<= (* 3 n) (+ 3 i2)) (<= (* 3 n) i1) (< (+ 6 i2) (* 3 n))), 22164#(or (<= (* 3 n) (+ 3 i1)) (< i2 (* 3 n))), 22159#(or (<= (* 3 n) i2) (<= (* 3 n) (+ i1 1)) (< (+ 3 i2) (* 3 n))), 22171#(or (<= (* 3 n) (+ i1 1)) (<= (* 3 n) (+ 3 i2)) (< (+ 6 i2) (* 3 n))), 22175#(or (<= (* 3 n) (+ 5 i1)) (<= (* 3 n) (+ 3 i2)) (< (+ 6 i2) (* 3 n))), 22173#(or (<= (* 3 n) (+ 3 i1)) (<= (* 3 n) (+ 3 i2)) (< (+ 6 i2) (* 3 n))), 22149#(< i2 (* 3 n)), 22158#(or (<= (* 3 n) i2) (< (+ 3 i2) (* 3 n)) (<= (* 3 n) i1)), 22160#(or (<= (* 3 n) i2) (< (+ 3 i2) (* 3 n)) (<= (* 3 n) (+ 2 i1))), 22167#(or (<= (* 3 n) i2) (< (+ 3 i2) (* 3 n)) (<= (* 3 n) (+ i1 4))), 22161#(or (<= (* 3 n) (+ 3 i2)) (< (+ 6 i2) (* 3 n))), 22156#(or (<= (* 3 n) i2) (< (+ 3 i2) (* 3 n)) (<= (+ (* 3 n) 2) i1)), 22172#(or (<= (* 3 n) (+ 3 i2)) (<= (* 3 n) (+ 2 i1)) (< (+ 6 i2) (* 3 n))), 22163#(or (<= (+ (* 3 n) 1) i1) (<= (* 3 n) (+ 3 i2)) (< (+ 6 i2) (* 3 n))), 22152#(or (< i2 (* 3 n)) (<= (* 3 n) i1)), 22150#(or (< i2 (* 3 n)) (<= (+ (* 3 n) 2) i1)), 22151#(or (<= (+ (* 3 n) 1) i1) (< i2 (* 3 n))), 22166#(or (<= (* 3 n) i2) (<= (* 3 n) (+ 3 i1)) (< (+ 3 i2) (* 3 n))), 22174#(or (<= (* 3 n) (+ 3 i2)) (< (+ 6 i2) (* 3 n)) (<= (* 3 n) (+ i1 4))), 22153#(or (<= (* 3 n) (+ i1 1)) (< i2 (* 3 n))), 22165#(or (< i2 (* 3 n)) (<= (* 3 n) (+ i1 4))), 22169#(or (<= (* 3 n) i2) (<= (* 3 n) (+ 5 i1)) (< (+ 3 i2) (* 3 n))), 22168#(or (<= (* 3 n) (+ 5 i1)) (< i2 (* 3 n))), 22154#(or (< i2 (* 3 n)) (<= (* 3 n) (+ 2 i1))), 22157#(or (<= (* 3 n) i2) (< (+ 3 i2) (* 3 n)) (<= (+ (* 3 n) 1) i1))] [2022-03-15 20:47:04,870 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 41 states [2022-03-15 20:47:04,870 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-15 20:47:04,871 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 41 interpolants. [2022-03-15 20:47:04,871 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=412, Invalid=1844, Unknown=0, NotChecked=0, Total=2256 [2022-03-15 20:47:04,871 INFO L87 Difference]: Start difference. First operand 1239 states and 3855 transitions. Second operand has 41 states, 41 states have (on average 2.1463414634146343) internal successors, (88), 40 states have internal predecessors, (88), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:47:05,566 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-15 20:47:05,567 INFO L93 Difference]: Finished difference Result 1322 states and 4010 transitions. [2022-03-15 20:47:05,567 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 38 states. [2022-03-15 20:47:05,567 INFO L78 Accepts]: Start accepts. Automaton has has 41 states, 41 states have (on average 2.1463414634146343) internal successors, (88), 40 states have internal predecessors, (88), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 19 [2022-03-15 20:47:05,567 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-15 20:47:05,571 INFO L225 Difference]: With dead ends: 1322 [2022-03-15 20:47:05,571 INFO L226 Difference]: Without dead ends: 1294 [2022-03-15 20:47:05,572 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 117 GetRequests, 45 SyntacticMatches, 1 SemanticMatches, 71 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1282 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=1176, Invalid=4080, Unknown=0, NotChecked=0, Total=5256 [2022-03-15 20:47:05,572 INFO L933 BasicCegarLoop]: 1 mSDtfsCounter, 105 mSDsluCounter, 101 mSDsCounter, 0 mSdLazyCounter, 476 mSolverCounterSat, 77 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 105 SdHoareTripleChecker+Valid, 1 SdHoareTripleChecker+Invalid, 553 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 77 IncrementalHoareTripleChecker+Valid, 476 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-03-15 20:47:05,573 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [105 Valid, 1 Invalid, 553 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [77 Valid, 476 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-03-15 20:47:05,574 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1294 states. [2022-03-15 20:47:05,588 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1294 to 1239. [2022-03-15 20:47:05,590 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1239 states, 1238 states have (on average 3.0775444264943457) internal successors, (3810), 1238 states have internal predecessors, (3810), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:47:05,593 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1239 states to 1239 states and 3810 transitions. [2022-03-15 20:47:05,593 INFO L78 Accepts]: Start accepts. Automaton has 1239 states and 3810 transitions. Word has length 19 [2022-03-15 20:47:05,593 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-15 20:47:05,593 INFO L470 AbstractCegarLoop]: Abstraction has 1239 states and 3810 transitions. [2022-03-15 20:47:05,593 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 41 states, 41 states have (on average 2.1463414634146343) internal successors, (88), 40 states have internal predecessors, (88), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-15 20:47:05,594 INFO L276 IsEmpty]: Start isEmpty. Operand 1239 states and 3810 transitions. [2022-03-15 20:47:05,596 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2022-03-15 20:47:05,596 INFO L506 BasicCegarLoop]: Found error trace [2022-03-15 20:47:05,596 INFO L514 BasicCegarLoop]: trace histogram [9, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-15 20:47:05,627 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2022-03-15 20:47:05,828 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 20:47:05,828 INFO L402 AbstractCegarLoop]: === Iteration 14 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONASSERT === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr1INUSE_VIOLATION] === [2022-03-15 20:47:05,829 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-15 20:47:05,829 INFO L85 PathProgramCache]: Analyzing trace with hash -1010007498, now seen corresponding path program 12 times [2022-03-15 20:47:05,830 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-15 20:47:05,830 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1694538180] [2022-03-15 20:47:05,830 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-15 20:47:05,830 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-15 20:47:05,842 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-15 20:47:05,932 INFO L134 CoverageAnalysis]: Checked inductivity of 51 backedges. 0 proven. 51 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 20:47:05,933 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-15 20:47:05,933 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1694538180] [2022-03-15 20:47:05,933 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1694538180] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-15 20:47:05,933 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [853573513] [2022-03-15 20:47:05,933 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-03-15 20:47:05,933 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-15 20:47:05,933 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-15 20:47:05,934 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-15 20:47:05,935 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2022-03-15 20:47:05,959 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 6 check-sat command(s) [2022-03-15 20:47:05,959 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-15 20:47:05,960 INFO L263 TraceCheckSpWp]: Trace formula consists of 85 conjuncts, 31 conjunts are in the unsatisfiable core [2022-03-15 20:47:05,961 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-15 20:47:06,265 INFO L353 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2022-03-15 20:47:06,265 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 9 select indices, 9 select index equivalence classes, 0 disjoint index pairs (out of 36 index pairs), introduced 17 new quantified variables, introduced 36 case distinctions, treesize of input 43 treesize of output 319 [2022-03-15 20:47:08,056 INFO L134 CoverageAnalysis]: Checked inductivity of 51 backedges. 0 proven. 51 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-15 20:47:08,057 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-15 20:47:10,244 INFO L353 Elim1Store]: treesize reduction 45, result has 96.3 percent of original size [2022-03-15 20:47:10,245 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 18 select indices, 18 select index equivalence classes, 0 disjoint index pairs (out of 153 index pairs), introduced 34 new quantified variables, introduced 153 case distinctions, treesize of input 39 treesize of output 1247 Received shutdown request... [2022-03-15 20:58:29,514 WARN L244 SmtUtils]: Removed 2 from assertion stack [2022-03-15 20:58:29,515 INFO L764 garLoopResultBuilder]: Registering result TIMEOUT for location ULTIMATE.startErr0ASSERT_VIOLATIONASSERT (2 of 3 remaining) [2022-03-15 20:58:29,529 WARN L340 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Timeout while monitored process is still running, waiting 1000 ms for graceful end [2022-03-15 20:58:29,529 WARN L340 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Timeout while monitored process is still running, waiting 1000 ms for graceful end [2022-03-15 20:58:29,531 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2022-03-15 20:58:29,731 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 20:58:29,732 WARN L594 AbstractCegarLoop]: Verification canceled: while BasicCegarLoop was analyzing trace of length 21 with TraceHistMax 9,while TraceCheckSpWp was constructing backward predicates,while SimplifyDDAWithTimeout was simplifying term of DAG size 3 for 30ms.. [2022-03-15 20:58:29,734 INFO L764 garLoopResultBuilder]: Registering result TIMEOUT for location ULTIMATE.startErr0INUSE_VIOLATION (1 of 3 remaining) [2022-03-15 20:58:29,734 INFO L764 garLoopResultBuilder]: Registering result TIMEOUT for location ULTIMATE.startErr1INUSE_VIOLATION (0 of 3 remaining) [2022-03-15 20:58:29,735 INFO L732 BasicCegarLoop]: Path program histogram: [12, 1, 1] [2022-03-15 20:58:29,737 INFO L230 ceAbstractionStarter]: Analysis of concurrent program completed with 1 thread instances [2022-03-15 20:58:29,737 INFO L180 ceAbstractionStarter]: Computing trace abstraction results [2022-03-15 20:58:29,738 INFO L202 PluginConnector]: Adding new model unroll-3.wvr.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 15.03 08:58:29 BasicIcfg [2022-03-15 20:58:29,738 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2022-03-15 20:58:29,738 INFO L158 Benchmark]: Toolchain (without parser) took 865112.36ms. Allocated memory was 175.1MB in the beginning and 1.3GB in the end (delta: 1.1GB). Free memory was 141.0MB in the beginning and 685.1MB in the end (delta: -544.1MB). Peak memory consumption was 807.0MB. Max. memory is 8.0GB. [2022-03-15 20:58:29,738 INFO L158 Benchmark]: Boogie PL CUP Parser took 0.09ms. Allocated memory is still 175.1MB. Free memory is still 142.1MB. There was no memory consumed. Max. memory is 8.0GB. [2022-03-15 20:58:29,738 INFO L158 Benchmark]: Boogie Procedure Inliner took 23.66ms. Allocated memory is still 175.1MB. Free memory was 140.9MB in the beginning and 139.3MB in the end (delta: 1.5MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. [2022-03-15 20:58:29,739 INFO L158 Benchmark]: Boogie Preprocessor took 12.61ms. Allocated memory is still 175.1MB. Free memory was 139.3MB in the beginning and 138.5MB in the end (delta: 856.8kB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. [2022-03-15 20:58:29,739 INFO L158 Benchmark]: RCFGBuilder took 185.65ms. Allocated memory is still 175.1MB. Free memory was 138.3MB in the beginning and 128.4MB in the end (delta: 9.9MB). Peak memory consumption was 9.4MB. Max. memory is 8.0GB. [2022-03-15 20:58:29,739 INFO L158 Benchmark]: TraceAbstraction took 864886.96ms. Allocated memory was 175.1MB in the beginning and 1.3GB in the end (delta: 1.1GB). Free memory was 128.0MB in the beginning and 685.1MB in the end (delta: -557.2MB). Peak memory consumption was 793.3MB. Max. memory is 8.0GB. [2022-03-15 20:58:29,740 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 175.1MB. Free memory is still 142.1MB. There was no memory consumed. Max. memory is 8.0GB. * Boogie Procedure Inliner took 23.66ms. Allocated memory is still 175.1MB. Free memory was 140.9MB in the beginning and 139.3MB in the end (delta: 1.5MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. * Boogie Preprocessor took 12.61ms. Allocated memory is still 175.1MB. Free memory was 139.3MB in the beginning and 138.5MB in the end (delta: 856.8kB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. * RCFGBuilder took 185.65ms. Allocated memory is still 175.1MB. Free memory was 138.3MB in the beginning and 128.4MB in the end (delta: 9.9MB). Peak memory consumption was 9.4MB. Max. memory is 8.0GB. * TraceAbstraction took 864886.96ms. Allocated memory was 175.1MB in the beginning and 1.3GB in the end (delta: 1.1GB). Free memory was 128.0MB in the beginning and 685.1MB in the end (delta: -557.2MB). Peak memory consumption was 793.3MB. Max. memory is 8.0GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: PetriNetLargeBlockEncoding benchmarks Lipton Reduction Statistics: ReductionTime: 0.1s, 20 PlacesBefore, 18 PlacesAfterwards, 15 TransitionsBefore, 13 TransitionsAfterwards, 16 CoEnabledTransitionPairs, 2 FixpointIterations, 3 TrivialSequentialCompositions, 0 ConcurrentSequentialCompositions, 0 TrivialYvCompositions, 0 ConcurrentYvCompositions, 0 ChoiceCompositions, 3 TotalNumberOfCompositions, 18 MoverChecksTotal, Independence Relation Statistics: CachedIndependenceRelation.Independence Queries: [ total: 18, positive: 18, positive conditional: 0, positive unconditional: 18, 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: 5, positive: 5, positive conditional: 0, positive unconditional: 5, negative: 0, negative conditional: 0, negative unconditional: 0, unknown: 0, unknown conditional: 0, unknown unconditional: 0] , Cache Queries: [ total: 18, positive: 13, positive conditional: 0, positive unconditional: 13, negative: 0, negative conditional: 0, negative unconditional: 0, unknown: 5, unknown conditional: 0, unknown unconditional: 5] , 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: 55]: Timeout (TraceAbstraction) Unable to prove that assertion always holds Cancelled while BasicCegarLoop was analyzing trace of length 21 with TraceHistMax 9,while TraceCheckSpWp was constructing backward predicates,while SimplifyDDAWithTimeout was simplifying term of DAG size 3 for 30ms.. - TimeoutResultAtElement [Line: 50]: 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 21 with TraceHistMax 9,while TraceCheckSpWp was constructing backward predicates,while SimplifyDDAWithTimeout was simplifying term of DAG size 3 for 30ms.. - TimeoutResultAtElement [Line: 50]: 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 21 with TraceHistMax 9,while TraceCheckSpWp was constructing backward predicates,while SimplifyDDAWithTimeout was simplifying term of DAG size 3 for 30ms.. - StatisticsResult: Ultimate Automizer benchmark data with 1 thread instances CFG has 5 procedures, 20 locations, 3 error locations. Started 1 CEGAR loops. OverallTime: 864.8s, OverallIterations: 14, TraceHistogramMax: 9, PathProgramHistogramMax: 12, EmptinessCheckTime: 0.0s, AutomataDifference: 30.3s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.1s, PartialOrderReductionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 2737 SdHoareTripleChecker+Valid, 3.5s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 2737 mSDsluCounter, 13 SdHoareTripleChecker+Invalid, 2.9s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 2336 mSDsCounter, 3231 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 6921 IncrementalHoareTripleChecker+Invalid, 10152 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 3231 mSolverCounterUnsat, 13 mSDtfsCounter, 6921 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 1586 GetRequests, 339 SyntacticMatches, 15 SemanticMatches, 1232 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 108931 ImplicationChecksByTransitivity, 29.2s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=1584occurred in iteration=11, InterpolantAutomatonStates: 1012, 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, 13 MinimizatonAttempts, 4212 StatesRemovedByMinimization, 10 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.0s SsaConstructionTime, 0.2s SatisfiabilityAnalysisTime, 141.8s InterpolantComputationTime, 345 NumberOfCodeBlocks, 345 NumberOfCodeBlocksAsserted, 44 NumberOfCheckSat, 474 ConstructedInterpolants, 0 QuantifiedInterpolants, 2904 SizeOfPredicates, 21 NumberOfNonLiveVariables, 655 ConjunctsInSsa, 116 ConjunctsInUnsatCore, 35 InterpolantComputations, 2 PerfectInterpolantSequences, 378/709 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