/usr/bin/java -Xmx16000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data -s ../../../trunk/examples/settings/automizer/concurrent/svcomp-Reach-32bit-Automizer_Default-noMmResRef-PN-VariableLbe.epf --traceabstraction.order.of.the.error.locations.to.be.checked PROGRAM_FIRST -tc ../../../trunk/examples/toolchains/AutomizerCInline.xml -i ../../../trunk/examples/svcomp/goblint-regression/28-race_reach_24-sound_lock_racing.i -------------------------------------------------------------------------------- This is Ultimate 0.2.3-dev-ac9dbd0-m [2023-08-24 12:40:55,266 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-08-24 12:40:55,347 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/concurrent/svcomp-Reach-32bit-Automizer_Default-noMmResRef-PN-VariableLbe.epf [2023-08-24 12:40:55,352 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-08-24 12:40:55,353 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.Checked method. Library mode if empty. [2023-08-24 12:40:55,386 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-08-24 12:40:55,386 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-08-24 12:40:55,391 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-08-24 12:40:55,392 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2023-08-24 12:40:55,395 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2023-08-24 12:40:55,396 INFO L153 SettingsManager]: * Use SBE=true [2023-08-24 12:40:55,396 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-08-24 12:40:55,396 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-08-24 12:40:55,397 INFO L153 SettingsManager]: * sizeof long=4 [2023-08-24 12:40:55,397 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-08-24 12:40:55,398 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-08-24 12:40:55,398 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-08-24 12:40:55,398 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-08-24 12:40:55,398 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-08-24 12:40:55,398 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-08-24 12:40:55,399 INFO L153 SettingsManager]: * sizeof long double=12 [2023-08-24 12:40:55,399 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-08-24 12:40:55,400 INFO L153 SettingsManager]: * Use constant arrays=true [2023-08-24 12:40:55,400 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-08-24 12:40:55,400 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2023-08-24 12:40:55,401 INFO L153 SettingsManager]: * To the following directory=./dump/ [2023-08-24 12:40:55,401 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-08-24 12:40:55,401 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-08-24 12:40:55,401 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-08-24 12:40:55,402 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-08-24 12:40:55,402 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2023-08-24 12:40:55,403 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2023-08-24 12:40:55,403 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-08-24 12:40:55,403 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2023-08-24 12:40:55,403 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-08-24 12:40:55,403 INFO L153 SettingsManager]: * Independence relation used for large block encoding in concurrent analysis=SYNTACTIC WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: Order of the error locations to be checked -> PROGRAM_FIRST [2023-08-24 12:40:55,704 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-08-24 12:40:55,723 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-08-24 12:40:55,725 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-08-24 12:40:55,726 INFO L270 PluginConnector]: Initializing CDTParser... [2023-08-24 12:40:55,728 INFO L274 PluginConnector]: CDTParser initialized [2023-08-24 12:40:55,729 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/goblint-regression/28-race_reach_24-sound_lock_racing.i [2023-08-24 12:40:56,833 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-08-24 12:40:57,151 INFO L384 CDTParser]: Found 1 translation units. [2023-08-24 12:40:57,152 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/goblint-regression/28-race_reach_24-sound_lock_racing.i [2023-08-24 12:40:57,167 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/4e5f00fe8/add1b70754d04783b85803be2d505f3f/FLAG1e8e846f0 [2023-08-24 12:40:57,184 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/4e5f00fe8/add1b70754d04783b85803be2d505f3f [2023-08-24 12:40:57,186 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-08-24 12:40:57,187 INFO L133 ToolchainWalker]: Walking toolchain with 5 elements. [2023-08-24 12:40:57,188 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-08-24 12:40:57,188 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-08-24 12:40:57,190 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-08-24 12:40:57,191 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 24.08 12:40:57" (1/1) ... [2023-08-24 12:40:57,191 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@4ad4b2f7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.08 12:40:57, skipping insertion in model container [2023-08-24 12:40:57,192 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 24.08 12:40:57" (1/1) ... [2023-08-24 12:40:57,234 INFO L176 MainTranslator]: Built tables and reachable declarations [2023-08-24 12:40:57,544 WARN L240 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/goblint-regression/28-race_reach_24-sound_lock_racing.i[30176,30189] [2023-08-24 12:40:57,565 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-08-24 12:40:57,581 INFO L201 MainTranslator]: Completed pre-run [2023-08-24 12:40:57,611 WARN L75 lationResultReporter]: Unsoundness Warning: unspecified type, defaulting to int C: short [244] [2023-08-24 12:40:57,613 WARN L75 lationResultReporter]: Unsoundness Warning: unspecified type, defaulting to int C: short [244] [2023-08-24 12:40:57,627 WARN L240 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/goblint-regression/28-race_reach_24-sound_lock_racing.i[30176,30189] [2023-08-24 12:40:57,645 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-08-24 12:40:57,690 INFO L206 MainTranslator]: Completed translation [2023-08-24 12:40:57,690 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.08 12:40:57 WrapperNode [2023-08-24 12:40:57,691 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-08-24 12:40:57,692 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-08-24 12:40:57,692 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-08-24 12:40:57,692 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-08-24 12:40:57,699 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.08 12:40:57" (1/1) ... [2023-08-24 12:40:57,727 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.08 12:40:57" (1/1) ... [2023-08-24 12:40:57,757 INFO L138 Inliner]: procedures = 170, calls = 36, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 88 [2023-08-24 12:40:57,758 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-08-24 12:40:57,759 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-08-24 12:40:57,759 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-08-24 12:40:57,759 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-08-24 12:40:57,766 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.08 12:40:57" (1/1) ... [2023-08-24 12:40:57,767 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.08 12:40:57" (1/1) ... [2023-08-24 12:40:57,774 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.08 12:40:57" (1/1) ... [2023-08-24 12:40:57,774 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.08 12:40:57" (1/1) ... [2023-08-24 12:40:57,793 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.08 12:40:57" (1/1) ... [2023-08-24 12:40:57,796 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.08 12:40:57" (1/1) ... [2023-08-24 12:40:57,797 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.08 12:40:57" (1/1) ... [2023-08-24 12:40:57,798 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.08 12:40:57" (1/1) ... [2023-08-24 12:40:57,800 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-08-24 12:40:57,810 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-08-24 12:40:57,810 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-08-24 12:40:57,810 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-08-24 12:40:57,811 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.08 12:40:57" (1/1) ... [2023-08-24 12:40:57,815 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-08-24 12:40:57,826 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-08-24 12:40:57,837 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) [2023-08-24 12:40:57,845 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 [2023-08-24 12:40:57,871 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2023-08-24 12:40:57,871 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2023-08-24 12:40:57,871 INFO L130 BoogieDeclarations]: Found specification of procedure #PthreadsMutexLock [2023-08-24 12:40:57,872 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-08-24 12:40:57,872 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2023-08-24 12:40:57,872 INFO L130 BoogieDeclarations]: Found specification of procedure t_fun [2023-08-24 12:40:57,872 INFO L138 BoogieDeclarations]: Found implementation of procedure t_fun [2023-08-24 12:40:57,873 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2023-08-24 12:40:57,873 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-08-24 12:40:57,873 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-08-24 12:40:57,873 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-08-24 12:40:57,874 WARN L210 CfgBuilder]: User set CodeBlockSize to SequenceOfStatements but program contains fork statements. Overwriting the user preferences and setting CodeBlockSize to OneNontrivialStatement [2023-08-24 12:40:58,024 INFO L236 CfgBuilder]: Building ICFG [2023-08-24 12:40:58,025 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2023-08-24 12:40:58,218 INFO L277 CfgBuilder]: Performing block encoding [2023-08-24 12:40:58,225 INFO L297 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-08-24 12:40:58,225 INFO L302 CfgBuilder]: Removed 10 assume(true) statements. [2023-08-24 12:40:58,227 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.08 12:40:58 BoogieIcfgContainer [2023-08-24 12:40:58,227 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-08-24 12:40:58,229 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-08-24 12:40:58,229 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-08-24 12:40:58,232 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-08-24 12:40:58,232 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 24.08 12:40:57" (1/3) ... [2023-08-24 12:40:58,233 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1cc7eef9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 24.08 12:40:58, skipping insertion in model container [2023-08-24 12:40:58,233 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.08 12:40:57" (2/3) ... [2023-08-24 12:40:58,234 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1cc7eef9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 24.08 12:40:58, skipping insertion in model container [2023-08-24 12:40:58,234 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.08 12:40:58" (3/3) ... [2023-08-24 12:40:58,235 INFO L112 eAbstractionObserver]: Analyzing ICFG 28-race_reach_24-sound_lock_racing.i [2023-08-24 12:40:58,249 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-08-24 12:40:58,249 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-08-24 12:40:58,249 INFO L515 ceAbstractionStarter]: Constructing petrified ICFG for 1 thread instances. [2023-08-24 12:40:58,305 INFO L144 ThreadInstanceAdder]: Constructed 1 joinOtherThreadTransitions. [2023-08-24 12:40:58,334 INFO L73 FinitePrefix]: Start finitePrefix. Operand has 106 places, 116 transitions, 240 flow [2023-08-24 12:40:58,396 INFO L124 PetriNetUnfolderBase]: 18/151 cut-off events. [2023-08-24 12:40:58,397 INFO L125 PetriNetUnfolderBase]: For 1/1 co-relation queries the response was YES. [2023-08-24 12:40:58,402 INFO L83 FinitePrefix]: Finished finitePrefix Result has 157 conditions, 151 events. 18/151 cut-off events. For 1/1 co-relation queries the response was YES. Maximal size of possible extension queue 10. Compared 312 event pairs, 0 based on Foata normal form. 0/128 useless extension candidates. Maximal degree in co-relation 76. Up to 4 conditions per place. [2023-08-24 12:40:58,403 INFO L82 GeneralOperation]: Start removeDead. Operand has 106 places, 116 transitions, 240 flow [2023-08-24 12:40:58,406 INFO L88 GeneralOperation]: Finished RemoveDead, result has has 102 places, 111 transitions, 227 flow [2023-08-24 12:40:58,409 INFO L124 etLargeBlockEncoding]: Petri net LBE is using variable-based independence relation. [2023-08-24 12:40:58,420 INFO L131 etLargeBlockEncoding]: Starting large block encoding on Petri net that has 102 places, 111 transitions, 227 flow [2023-08-24 12:40:58,426 INFO L113 LiptonReduction]: Starting Lipton reduction on Petri net that has 102 places, 111 transitions, 227 flow [2023-08-24 12:40:58,427 INFO L73 FinitePrefix]: Start finitePrefix. Operand has 102 places, 111 transitions, 227 flow [2023-08-24 12:40:58,484 INFO L124 PetriNetUnfolderBase]: 17/146 cut-off events. [2023-08-24 12:40:58,485 INFO L125 PetriNetUnfolderBase]: For 0/0 co-relation queries the response was YES. [2023-08-24 12:40:58,486 INFO L83 FinitePrefix]: Finished finitePrefix Result has 151 conditions, 146 events. 17/146 cut-off events. For 0/0 co-relation queries the response was YES. Maximal size of possible extension queue 10. Compared 298 event pairs, 0 based on Foata normal form. 0/123 useless extension candidates. Maximal degree in co-relation 76. Up to 4 conditions per place. [2023-08-24 12:40:58,487 INFO L119 LiptonReduction]: Number of co-enabled transitions 2296 [2023-08-24 12:41:03,134 INFO L134 LiptonReduction]: Checked pairs total: 4056 [2023-08-24 12:41:03,135 INFO L136 LiptonReduction]: Total number of compositions: 103 [2023-08-24 12:41:03,147 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-08-24 12:41:03,152 INFO L357 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=false, mAutomataTypeConcurrency=PETRI_NET, 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=false, mMcrInterpolantMethod=WP, mPorIndependenceSettings=[Lde.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings;@1e6d47e7, mLbeIndependenceSettings=[IndependenceType=SYNTACTIC, AbstractionType=NONE, UseConditional=, UseSemiCommutativity=, Solver=, SolverTimeout=] [2023-08-24 12:41:03,153 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-08-24 12:41:03,157 INFO L185 PetriNetUnfolderBase]: Found word, exiting Unfolder. [2023-08-24 12:41:03,157 INFO L124 PetriNetUnfolderBase]: 1/12 cut-off events. [2023-08-24 12:41:03,157 INFO L125 PetriNetUnfolderBase]: For 0/0 co-relation queries the response was YES. [2023-08-24 12:41:03,157 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-24 12:41:03,158 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1] [2023-08-24 12:41:03,158 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-08-24 12:41:03,162 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-24 12:41:03,163 INFO L85 PathProgramCache]: Analyzing trace with hash 13857248, now seen corresponding path program 1 times [2023-08-24 12:41:03,170 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-24 12:41:03,171 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1902491332] [2023-08-24 12:41:03,171 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-24 12:41:03,171 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-24 12:41:03,311 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-24 12:41:03,589 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-24 12:41:03,590 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-24 12:41:03,590 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1902491332] [2023-08-24 12:41:03,591 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1902491332] provided 1 perfect and 0 imperfect interpolant sequences [2023-08-24 12:41:03,591 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-08-24 12:41:03,592 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2023-08-24 12:41:03,593 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1266256193] [2023-08-24 12:41:03,593 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-08-24 12:41:03,600 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-08-24 12:41:03,606 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-24 12:41:03,630 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-08-24 12:41:03,631 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-08-24 12:41:03,634 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 96 out of 219 [2023-08-24 12:41:03,639 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 25 places, 30 transitions, 65 flow. Second operand has 3 states, 3 states have (on average 97.33333333333333) internal successors, (292), 3 states have internal predecessors, (292), 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) [2023-08-24 12:41:03,639 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-24 12:41:03,639 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 96 of 219 [2023-08-24 12:41:03,640 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-24 12:41:03,728 INFO L124 PetriNetUnfolderBase]: 69/170 cut-off events. [2023-08-24 12:41:03,728 INFO L125 PetriNetUnfolderBase]: For 0/0 co-relation queries the response was YES. [2023-08-24 12:41:03,728 INFO L83 FinitePrefix]: Finished finitePrefix Result has 340 conditions, 170 events. 69/170 cut-off events. For 0/0 co-relation queries the response was YES. Maximal size of possible extension queue 11. Compared 540 event pairs, 21 based on Foata normal form. 9/162 useless extension candidates. Maximal degree in co-relation 315. Up to 114 conditions per place. [2023-08-24 12:41:03,730 INFO L140 encePairwiseOnDemand]: 207/219 looper letters, 16 selfloop transitions, 2 changer transitions 10/29 dead transitions. [2023-08-24 12:41:03,731 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 26 places, 29 transitions, 117 flow [2023-08-24 12:41:03,732 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-08-24 12:41:03,734 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3 states. [2023-08-24 12:41:03,745 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 328 transitions. [2023-08-24 12:41:03,749 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.4992389649923896 [2023-08-24 12:41:03,750 INFO L72 ComplementDD]: Start complementDD. Operand 3 states and 328 transitions. [2023-08-24 12:41:03,751 INFO L73 IsDeterministic]: Start isDeterministic. Operand 3 states and 328 transitions. [2023-08-24 12:41:03,753 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-24 12:41:03,756 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 3 states and 328 transitions. [2023-08-24 12:41:03,762 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 4 states, 3 states have (on average 109.33333333333333) internal successors, (328), 3 states have internal predecessors, (328), 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) [2023-08-24 12:41:03,766 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 4 states, 4 states have (on average 219.0) internal successors, (876), 4 states have internal predecessors, (876), 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) [2023-08-24 12:41:03,767 INFO L81 ComplementDD]: Finished complementDD. Result has 4 states, 4 states have (on average 219.0) internal successors, (876), 4 states have internal predecessors, (876), 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) [2023-08-24 12:41:03,769 INFO L175 Difference]: Start difference. First operand has 25 places, 30 transitions, 65 flow. Second operand 3 states and 328 transitions. [2023-08-24 12:41:03,769 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 26 places, 29 transitions, 117 flow [2023-08-24 12:41:03,772 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 26 places, 29 transitions, 117 flow, removed 0 selfloop flow, removed 0 redundant places. [2023-08-24 12:41:03,774 INFO L231 Difference]: Finished difference. Result has 27 places, 16 transitions, 43 flow [2023-08-24 12:41:03,776 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=219, PETRI_DIFFERENCE_MINUEND_FLOW=47, PETRI_DIFFERENCE_MINUEND_PLACES=24, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=21, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=2, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=19, PETRI_DIFFERENCE_SUBTRAHEND_STATES=3, PETRI_FLOW=43, PETRI_PLACES=27, PETRI_TRANSITIONS=16} [2023-08-24 12:41:03,779 INFO L281 CegarLoopForPetriNet]: 25 programPoint places, 2 predicate places. [2023-08-24 12:41:03,779 INFO L495 AbstractCegarLoop]: Abstraction has has 27 places, 16 transitions, 43 flow [2023-08-24 12:41:03,779 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 97.33333333333333) internal successors, (292), 3 states have internal predecessors, (292), 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) [2023-08-24 12:41:03,779 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-24 12:41:03,780 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-08-24 12:41:03,780 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2023-08-24 12:41:03,780 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-08-24 12:41:03,788 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-24 12:41:03,788 INFO L85 PathProgramCache]: Analyzing trace with hash -1380031815, now seen corresponding path program 1 times [2023-08-24 12:41:03,788 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-24 12:41:03,789 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1898480950] [2023-08-24 12:41:03,789 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-24 12:41:03,789 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-24 12:41:03,814 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-24 12:41:03,979 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-08-24 12:41:03,979 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-24 12:41:03,980 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1898480950] [2023-08-24 12:41:03,980 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1898480950] provided 1 perfect and 0 imperfect interpolant sequences [2023-08-24 12:41:03,980 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-08-24 12:41:03,980 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2023-08-24 12:41:03,980 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [863295688] [2023-08-24 12:41:03,981 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-08-24 12:41:03,982 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-08-24 12:41:03,982 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-24 12:41:03,983 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-08-24 12:41:03,983 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2023-08-24 12:41:03,985 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 79 out of 219 [2023-08-24 12:41:03,985 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 27 places, 16 transitions, 43 flow. Second operand has 4 states, 4 states have (on average 81.5) internal successors, (326), 4 states have internal predecessors, (326), 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) [2023-08-24 12:41:03,985 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-24 12:41:03,985 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 79 of 219 [2023-08-24 12:41:03,986 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-24 12:41:04,048 INFO L124 PetriNetUnfolderBase]: 26/80 cut-off events. [2023-08-24 12:41:04,049 INFO L125 PetriNetUnfolderBase]: For 1/1 co-relation queries the response was YES. [2023-08-24 12:41:04,050 INFO L83 FinitePrefix]: Finished finitePrefix Result has 176 conditions, 80 events. 26/80 cut-off events. For 1/1 co-relation queries the response was YES. Maximal size of possible extension queue 5. Compared 177 event pairs, 12 based on Foata normal form. 7/77 useless extension candidates. Maximal degree in co-relation 158. Up to 38 conditions per place. [2023-08-24 12:41:04,051 INFO L140 encePairwiseOnDemand]: 213/219 looper letters, 13 selfloop transitions, 6 changer transitions 2/22 dead transitions. [2023-08-24 12:41:04,051 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 25 places, 22 transitions, 99 flow [2023-08-24 12:41:04,051 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-08-24 12:41:04,051 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 4 states. [2023-08-24 12:41:04,053 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 340 transitions. [2023-08-24 12:41:04,054 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.3881278538812785 [2023-08-24 12:41:04,055 INFO L72 ComplementDD]: Start complementDD. Operand 4 states and 340 transitions. [2023-08-24 12:41:04,055 INFO L73 IsDeterministic]: Start isDeterministic. Operand 4 states and 340 transitions. [2023-08-24 12:41:04,056 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-24 12:41:04,056 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 4 states and 340 transitions. [2023-08-24 12:41:04,057 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 5 states, 4 states have (on average 85.0) internal successors, (340), 4 states have internal predecessors, (340), 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) [2023-08-24 12:41:04,060 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 5 states, 5 states have (on average 219.0) internal successors, (1095), 5 states have internal predecessors, (1095), 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) [2023-08-24 12:41:04,061 INFO L81 ComplementDD]: Finished complementDD. Result has 5 states, 5 states have (on average 219.0) internal successors, (1095), 5 states have internal predecessors, (1095), 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) [2023-08-24 12:41:04,061 INFO L175 Difference]: Start difference. First operand has 27 places, 16 transitions, 43 flow. Second operand 4 states and 340 transitions. [2023-08-24 12:41:04,061 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 25 places, 22 transitions, 99 flow [2023-08-24 12:41:04,062 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 23 places, 22 transitions, 95 flow, removed 0 selfloop flow, removed 2 redundant places. [2023-08-24 12:41:04,062 INFO L231 Difference]: Finished difference. Result has 24 places, 17 transitions, 61 flow [2023-08-24 12:41:04,063 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=219, PETRI_DIFFERENCE_MINUEND_FLOW=39, PETRI_DIFFERENCE_MINUEND_PLACES=20, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=16, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=5, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=10, PETRI_DIFFERENCE_SUBTRAHEND_STATES=4, PETRI_FLOW=61, PETRI_PLACES=24, PETRI_TRANSITIONS=17} [2023-08-24 12:41:04,064 INFO L281 CegarLoopForPetriNet]: 25 programPoint places, -1 predicate places. [2023-08-24 12:41:04,064 INFO L495 AbstractCegarLoop]: Abstraction has has 24 places, 17 transitions, 61 flow [2023-08-24 12:41:04,065 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 81.5) internal successors, (326), 4 states have internal predecessors, (326), 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) [2023-08-24 12:41:04,065 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-24 12:41:04,065 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-08-24 12:41:04,065 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2023-08-24 12:41:04,066 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-08-24 12:41:04,069 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-24 12:41:04,071 INFO L85 PathProgramCache]: Analyzing trace with hash 2065902876, now seen corresponding path program 1 times [2023-08-24 12:41:04,071 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-24 12:41:04,075 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [240007863] [2023-08-24 12:41:04,076 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-24 12:41:04,076 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-24 12:41:04,095 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-24 12:41:04,213 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-24 12:41:04,213 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-24 12:41:04,213 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [240007863] [2023-08-24 12:41:04,213 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [240007863] provided 0 perfect and 1 imperfect interpolant sequences [2023-08-24 12:41:04,213 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1529247399] [2023-08-24 12:41:04,213 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-24 12:41:04,214 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-24 12:41:04,214 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-08-24 12:41:04,225 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) [2023-08-24 12:41:04,277 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-08-24 12:41:04,326 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-24 12:41:04,328 INFO L262 TraceCheckSpWp]: Trace formula consists of 68 conjuncts, 3 conjunts are in the unsatisfiable core [2023-08-24 12:41:04,333 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-08-24 12:41:04,828 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-24 12:41:04,828 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-08-24 12:41:04,850 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-24 12:41:04,851 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1529247399] provided 0 perfect and 2 imperfect interpolant sequences [2023-08-24 12:41:04,851 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-08-24 12:41:04,851 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [3, 3, 3] total 5 [2023-08-24 12:41:04,852 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [311969233] [2023-08-24 12:41:04,852 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-08-24 12:41:04,852 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2023-08-24 12:41:04,853 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-24 12:41:04,853 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2023-08-24 12:41:04,853 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=15, Unknown=0, NotChecked=0, Total=30 [2023-08-24 12:41:04,854 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 94 out of 219 [2023-08-24 12:41:04,855 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 24 places, 17 transitions, 61 flow. Second operand has 6 states, 6 states have (on average 96.66666666666667) internal successors, (580), 6 states have internal predecessors, (580), 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) [2023-08-24 12:41:04,855 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-24 12:41:04,855 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 94 of 219 [2023-08-24 12:41:04,855 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-24 12:41:04,897 INFO L124 PetriNetUnfolderBase]: 16/46 cut-off events. [2023-08-24 12:41:04,898 INFO L125 PetriNetUnfolderBase]: For 21/21 co-relation queries the response was YES. [2023-08-24 12:41:04,900 INFO L83 FinitePrefix]: Finished finitePrefix Result has 123 conditions, 46 events. 16/46 cut-off events. For 21/21 co-relation queries the response was YES. Maximal size of possible extension queue 3. Compared 83 event pairs, 0 based on Foata normal form. 0/46 useless extension candidates. Maximal degree in co-relation 109. Up to 34 conditions per place. [2023-08-24 12:41:04,901 INFO L140 encePairwiseOnDemand]: 216/219 looper letters, 0 selfloop transitions, 0 changer transitions 22/22 dead transitions. [2023-08-24 12:41:04,901 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 23 places, 22 transitions, 120 flow [2023-08-24 12:41:04,902 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-08-24 12:41:04,902 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 4 states. [2023-08-24 12:41:04,903 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 399 transitions. [2023-08-24 12:41:04,903 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.4554794520547945 [2023-08-24 12:41:04,903 INFO L72 ComplementDD]: Start complementDD. Operand 4 states and 399 transitions. [2023-08-24 12:41:04,903 INFO L73 IsDeterministic]: Start isDeterministic. Operand 4 states and 399 transitions. [2023-08-24 12:41:04,904 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-24 12:41:04,904 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 4 states and 399 transitions. [2023-08-24 12:41:04,905 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 5 states, 4 states have (on average 99.75) internal successors, (399), 4 states have internal predecessors, (399), 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) [2023-08-24 12:41:04,906 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 5 states, 5 states have (on average 219.0) internal successors, (1095), 5 states have internal predecessors, (1095), 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) [2023-08-24 12:41:04,907 INFO L81 ComplementDD]: Finished complementDD. Result has 5 states, 5 states have (on average 219.0) internal successors, (1095), 5 states have internal predecessors, (1095), 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) [2023-08-24 12:41:04,907 INFO L175 Difference]: Start difference. First operand has 24 places, 17 transitions, 61 flow. Second operand 4 states and 399 transitions. [2023-08-24 12:41:04,907 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 23 places, 22 transitions, 120 flow [2023-08-24 12:41:04,908 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 19 places, 22 transitions, 89 flow, removed 2 selfloop flow, removed 4 redundant places. [2023-08-24 12:41:04,908 INFO L231 Difference]: Finished difference. Result has 19 places, 0 transitions, 0 flow [2023-08-24 12:41:04,908 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=219, PETRI_DIFFERENCE_MINUEND_FLOW=29, PETRI_DIFFERENCE_MINUEND_PLACES=16, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=13, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=0, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=13, PETRI_DIFFERENCE_SUBTRAHEND_STATES=4, PETRI_FLOW=0, PETRI_PLACES=19, PETRI_TRANSITIONS=0} [2023-08-24 12:41:04,910 INFO L281 CegarLoopForPetriNet]: 25 programPoint places, -6 predicate places. [2023-08-24 12:41:04,910 INFO L495 AbstractCegarLoop]: Abstraction has has 19 places, 0 transitions, 0 flow [2023-08-24 12:41:04,910 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 96.66666666666667) internal successors, (580), 6 states have internal predecessors, (580), 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) [2023-08-24 12:41:04,913 INFO L805 garLoopResultBuilder]: Registering result SAFE for location ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2023-08-24 12:41:04,924 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2023-08-24 12:41:05,119 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-24 12:41:05,119 INFO L445 BasicCegarLoop]: Path program histogram: [1, 1, 1] [2023-08-24 12:41:05,121 INFO L307 ceAbstractionStarter]: Result for error location AllErrorsAtOnce was SAFE (1/2) [2023-08-24 12:41:05,129 INFO L73 FinitePrefix]: Start finitePrefix. Operand has 106 places, 116 transitions, 240 flow [2023-08-24 12:41:05,145 INFO L124 PetriNetUnfolderBase]: 18/151 cut-off events. [2023-08-24 12:41:05,145 INFO L125 PetriNetUnfolderBase]: For 1/1 co-relation queries the response was YES. [2023-08-24 12:41:05,146 INFO L83 FinitePrefix]: Finished finitePrefix Result has 157 conditions, 151 events. 18/151 cut-off events. For 1/1 co-relation queries the response was YES. Maximal size of possible extension queue 10. Compared 312 event pairs, 0 based on Foata normal form. 0/128 useless extension candidates. Maximal degree in co-relation 76. Up to 4 conditions per place. [2023-08-24 12:41:05,146 INFO L82 GeneralOperation]: Start removeDead. Operand has 106 places, 116 transitions, 240 flow [2023-08-24 12:41:05,147 INFO L88 GeneralOperation]: Finished RemoveDead, result has has 102 places, 111 transitions, 227 flow [2023-08-24 12:41:05,147 INFO L124 etLargeBlockEncoding]: Petri net LBE is using variable-based independence relation. [2023-08-24 12:41:05,147 INFO L131 etLargeBlockEncoding]: Starting large block encoding on Petri net that has 102 places, 111 transitions, 227 flow [2023-08-24 12:41:05,148 INFO L113 LiptonReduction]: Starting Lipton reduction on Petri net that has 102 places, 111 transitions, 227 flow [2023-08-24 12:41:05,148 INFO L73 FinitePrefix]: Start finitePrefix. Operand has 102 places, 111 transitions, 227 flow [2023-08-24 12:41:05,160 INFO L124 PetriNetUnfolderBase]: 17/146 cut-off events. [2023-08-24 12:41:05,160 INFO L125 PetriNetUnfolderBase]: For 0/0 co-relation queries the response was YES. [2023-08-24 12:41:05,161 INFO L83 FinitePrefix]: Finished finitePrefix Result has 151 conditions, 146 events. 17/146 cut-off events. For 0/0 co-relation queries the response was YES. Maximal size of possible extension queue 10. Compared 298 event pairs, 0 based on Foata normal form. 0/123 useless extension candidates. Maximal degree in co-relation 76. Up to 4 conditions per place. [2023-08-24 12:41:05,162 INFO L119 LiptonReduction]: Number of co-enabled transitions 2296 [2023-08-24 12:41:08,326 INFO L134 LiptonReduction]: Checked pairs total: 4056 [2023-08-24 12:41:08,326 INFO L136 LiptonReduction]: Total number of compositions: 99 [2023-08-24 12:41:08,328 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == InUseError ======== [2023-08-24 12:41:08,329 INFO L357 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=false, mAutomataTypeConcurrency=PETRI_NET, 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=false, mMcrInterpolantMethod=WP, mPorIndependenceSettings=[Lde.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings;@1e6d47e7, mLbeIndependenceSettings=[IndependenceType=SYNTACTIC, AbstractionType=NONE, UseConditional=, UseSemiCommutativity=, Solver=, SolverTimeout=] [2023-08-24 12:41:08,329 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-08-24 12:41:08,332 INFO L185 PetriNetUnfolderBase]: Found word, exiting Unfolder. [2023-08-24 12:41:08,332 INFO L124 PetriNetUnfolderBase]: 2/21 cut-off events. [2023-08-24 12:41:08,333 INFO L125 PetriNetUnfolderBase]: For 0/0 co-relation queries the response was YES. [2023-08-24 12:41:08,333 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-24 12:41:08,333 INFO L208 CegarLoopForPetriNet]: trace histogram [2, 1, 1, 1, 1] [2023-08-24 12:41:08,333 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES === [ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES] === [2023-08-24 12:41:08,333 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-24 12:41:08,334 INFO L85 PathProgramCache]: Analyzing trace with hash -928882894, now seen corresponding path program 1 times [2023-08-24 12:41:08,334 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-24 12:41:08,335 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1417196101] [2023-08-24 12:41:08,335 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-24 12:41:08,335 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-24 12:41:08,363 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-08-24 12:41:08,363 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2023-08-24 12:41:08,379 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-08-24 12:41:08,399 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2023-08-24 12:41:08,399 INFO L360 BasicCegarLoop]: Counterexample is feasible [2023-08-24 12:41:08,399 INFO L805 garLoopResultBuilder]: Registering result UNSAFE for location ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (0 of 1 remaining) [2023-08-24 12:41:08,400 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2023-08-24 12:41:08,400 INFO L445 BasicCegarLoop]: Path program histogram: [1] [2023-08-24 12:41:08,400 INFO L307 ceAbstractionStarter]: Result for error location InUseError was UNSAFE (2/2) [2023-08-24 12:41:08,401 WARN L233 ceAbstractionStarter]: 1 thread instances were not sufficient, I will increase this number and restart the analysis [2023-08-24 12:41:08,401 INFO L515 ceAbstractionStarter]: Constructing petrified ICFG for 2 thread instances. [2023-08-24 12:41:08,421 INFO L144 ThreadInstanceAdder]: Constructed 2 joinOtherThreadTransitions. [2023-08-24 12:41:08,427 INFO L73 FinitePrefix]: Start finitePrefix. Operand has 131 places, 146 transitions, 310 flow [2023-08-24 12:41:08,454 INFO L124 PetriNetUnfolderBase]: 32/241 cut-off events. [2023-08-24 12:41:08,455 INFO L125 PetriNetUnfolderBase]: For 6/6 co-relation queries the response was YES. [2023-08-24 12:41:08,456 INFO L83 FinitePrefix]: Finished finitePrefix Result has 255 conditions, 241 events. 32/241 cut-off events. For 6/6 co-relation queries the response was YES. Maximal size of possible extension queue 11. Compared 640 event pairs, 0 based on Foata normal form. 0/202 useless extension candidates. Maximal degree in co-relation 153. Up to 8 conditions per place. [2023-08-24 12:41:08,456 INFO L82 GeneralOperation]: Start removeDead. Operand has 131 places, 146 transitions, 310 flow [2023-08-24 12:41:08,458 INFO L88 GeneralOperation]: Finished RemoveDead, result has has 131 places, 146 transitions, 310 flow [2023-08-24 12:41:08,458 INFO L124 etLargeBlockEncoding]: Petri net LBE is using variable-based independence relation. [2023-08-24 12:41:08,458 INFO L131 etLargeBlockEncoding]: Starting large block encoding on Petri net that has 131 places, 146 transitions, 310 flow [2023-08-24 12:41:08,458 INFO L113 LiptonReduction]: Starting Lipton reduction on Petri net that has 131 places, 146 transitions, 310 flow [2023-08-24 12:41:08,458 INFO L73 FinitePrefix]: Start finitePrefix. Operand has 131 places, 146 transitions, 310 flow [2023-08-24 12:41:08,488 INFO L124 PetriNetUnfolderBase]: 32/241 cut-off events. [2023-08-24 12:41:08,488 INFO L125 PetriNetUnfolderBase]: For 6/6 co-relation queries the response was YES. [2023-08-24 12:41:08,489 INFO L83 FinitePrefix]: Finished finitePrefix Result has 255 conditions, 241 events. 32/241 cut-off events. For 6/6 co-relation queries the response was YES. Maximal size of possible extension queue 11. Compared 640 event pairs, 0 based on Foata normal form. 0/202 useless extension candidates. Maximal degree in co-relation 153. Up to 8 conditions per place. [2023-08-24 12:41:08,494 INFO L119 LiptonReduction]: Number of co-enabled transitions 6776 [2023-08-24 12:41:11,844 INFO L134 LiptonReduction]: Checked pairs total: 15394 [2023-08-24 12:41:11,845 INFO L136 LiptonReduction]: Total number of compositions: 113 [2023-08-24 12:41:11,846 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-08-24 12:41:11,847 INFO L357 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=false, mAutomataTypeConcurrency=PETRI_NET, 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=false, mMcrInterpolantMethod=WP, mPorIndependenceSettings=[Lde.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings;@1e6d47e7, mLbeIndependenceSettings=[IndependenceType=SYNTACTIC, AbstractionType=NONE, UseConditional=, UseSemiCommutativity=, Solver=, SolverTimeout=] [2023-08-24 12:41:11,847 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-08-24 12:41:11,849 INFO L185 PetriNetUnfolderBase]: Found word, exiting Unfolder. [2023-08-24 12:41:11,850 INFO L124 PetriNetUnfolderBase]: 1/11 cut-off events. [2023-08-24 12:41:11,850 INFO L125 PetriNetUnfolderBase]: For 0/0 co-relation queries the response was YES. [2023-08-24 12:41:11,850 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-24 12:41:11,850 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1] [2023-08-24 12:41:11,850 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-08-24 12:41:11,850 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-24 12:41:11,850 INFO L85 PathProgramCache]: Analyzing trace with hash 25804017, now seen corresponding path program 1 times [2023-08-24 12:41:11,851 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-24 12:41:11,851 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [289527006] [2023-08-24 12:41:11,851 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-24 12:41:11,851 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-24 12:41:11,858 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-24 12:41:11,891 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-24 12:41:11,892 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-24 12:41:11,892 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [289527006] [2023-08-24 12:41:11,892 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [289527006] provided 1 perfect and 0 imperfect interpolant sequences [2023-08-24 12:41:11,892 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-08-24 12:41:11,892 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2023-08-24 12:41:11,892 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [127043606] [2023-08-24 12:41:11,893 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-08-24 12:41:11,893 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-08-24 12:41:11,893 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-24 12:41:11,893 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-08-24 12:41:11,893 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-08-24 12:41:11,894 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 114 out of 259 [2023-08-24 12:41:11,894 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 44 places, 55 transitions, 128 flow. Second operand has 3 states, 3 states have (on average 115.33333333333333) internal successors, (346), 3 states have internal predecessors, (346), 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) [2023-08-24 12:41:11,895 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-24 12:41:11,895 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 114 of 259 [2023-08-24 12:41:11,895 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-24 12:41:12,161 INFO L124 PetriNetUnfolderBase]: 1818/3178 cut-off events. [2023-08-24 12:41:12,161 INFO L125 PetriNetUnfolderBase]: For 64/64 co-relation queries the response was YES. [2023-08-24 12:41:12,165 INFO L83 FinitePrefix]: Finished finitePrefix Result has 6215 conditions, 3178 events. 1818/3178 cut-off events. For 64/64 co-relation queries the response was YES. Maximal size of possible extension queue 118. Compared 17705 event pairs, 639 based on Foata normal form. 555/3413 useless extension candidates. Maximal degree in co-relation 4478. Up to 2714 conditions per place. [2023-08-24 12:41:12,173 INFO L140 encePairwiseOnDemand]: 241/259 looper letters, 33 selfloop transitions, 3 changer transitions 15/57 dead transitions. [2023-08-24 12:41:12,173 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 46 places, 57 transitions, 235 flow [2023-08-24 12:41:12,174 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-08-24 12:41:12,174 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3 states. [2023-08-24 12:41:12,175 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 412 transitions. [2023-08-24 12:41:12,175 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.5302445302445302 [2023-08-24 12:41:12,175 INFO L72 ComplementDD]: Start complementDD. Operand 3 states and 412 transitions. [2023-08-24 12:41:12,175 INFO L73 IsDeterministic]: Start isDeterministic. Operand 3 states and 412 transitions. [2023-08-24 12:41:12,176 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-24 12:41:12,176 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 3 states and 412 transitions. [2023-08-24 12:41:12,177 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 4 states, 3 states have (on average 137.33333333333334) internal successors, (412), 3 states have internal predecessors, (412), 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) [2023-08-24 12:41:12,178 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 4 states, 4 states have (on average 259.0) internal successors, (1036), 4 states have internal predecessors, (1036), 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) [2023-08-24 12:41:12,179 INFO L81 ComplementDD]: Finished complementDD. Result has 4 states, 4 states have (on average 259.0) internal successors, (1036), 4 states have internal predecessors, (1036), 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) [2023-08-24 12:41:12,179 INFO L175 Difference]: Start difference. First operand has 44 places, 55 transitions, 128 flow. Second operand 3 states and 412 transitions. [2023-08-24 12:41:12,179 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 46 places, 57 transitions, 235 flow [2023-08-24 12:41:12,182 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 46 places, 57 transitions, 235 flow, removed 0 selfloop flow, removed 0 redundant places. [2023-08-24 12:41:12,184 INFO L231 Difference]: Finished difference. Result has 47 places, 33 transitions, 89 flow [2023-08-24 12:41:12,184 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=259, PETRI_DIFFERENCE_MINUEND_FLOW=100, PETRI_DIFFERENCE_MINUEND_PLACES=44, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=41, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=1, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=38, PETRI_DIFFERENCE_SUBTRAHEND_STATES=3, PETRI_FLOW=89, PETRI_PLACES=47, PETRI_TRANSITIONS=33} [2023-08-24 12:41:12,187 INFO L281 CegarLoopForPetriNet]: 44 programPoint places, 3 predicate places. [2023-08-24 12:41:12,187 INFO L495 AbstractCegarLoop]: Abstraction has has 47 places, 33 transitions, 89 flow [2023-08-24 12:41:12,187 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 115.33333333333333) internal successors, (346), 3 states have internal predecessors, (346), 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) [2023-08-24 12:41:12,187 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-24 12:41:12,188 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-08-24 12:41:12,188 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4 [2023-08-24 12:41:12,188 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-08-24 12:41:12,188 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-24 12:41:12,188 INFO L85 PathProgramCache]: Analyzing trace with hash -1994549080, now seen corresponding path program 1 times [2023-08-24 12:41:12,189 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-24 12:41:12,189 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1676052759] [2023-08-24 12:41:12,189 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-24 12:41:12,189 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-24 12:41:12,204 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-24 12:41:12,327 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-08-24 12:41:12,327 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-24 12:41:12,329 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1676052759] [2023-08-24 12:41:12,329 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1676052759] provided 1 perfect and 0 imperfect interpolant sequences [2023-08-24 12:41:12,329 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-08-24 12:41:12,329 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2023-08-24 12:41:12,329 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [610010196] [2023-08-24 12:41:12,329 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-08-24 12:41:12,330 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-08-24 12:41:12,330 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-24 12:41:12,331 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-08-24 12:41:12,331 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2023-08-24 12:41:12,332 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 95 out of 259 [2023-08-24 12:41:12,332 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 47 places, 33 transitions, 89 flow. Second operand has 5 states, 5 states have (on average 97.0) internal successors, (485), 5 states have internal predecessors, (485), 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) [2023-08-24 12:41:12,332 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-24 12:41:12,332 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 95 of 259 [2023-08-24 12:41:12,332 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-24 12:41:12,448 INFO L124 PetriNetUnfolderBase]: 410/872 cut-off events. [2023-08-24 12:41:12,451 INFO L125 PetriNetUnfolderBase]: For 22/22 co-relation queries the response was YES. [2023-08-24 12:41:12,452 INFO L83 FinitePrefix]: Finished finitePrefix Result has 1773 conditions, 872 events. 410/872 cut-off events. For 22/22 co-relation queries the response was YES. Maximal size of possible extension queue 36. Compared 4273 event pairs, 140 based on Foata normal form. 159/952 useless extension candidates. Maximal degree in co-relation 863. Up to 505 conditions per place. [2023-08-24 12:41:12,455 INFO L140 encePairwiseOnDemand]: 249/259 looper letters, 24 selfloop transitions, 10 changer transitions 0/41 dead transitions. [2023-08-24 12:41:12,455 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 42 places, 41 transitions, 178 flow [2023-08-24 12:41:12,455 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-08-24 12:41:12,456 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 4 states. [2023-08-24 12:41:12,457 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 418 transitions. [2023-08-24 12:41:12,457 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.4034749034749035 [2023-08-24 12:41:12,457 INFO L72 ComplementDD]: Start complementDD. Operand 4 states and 418 transitions. [2023-08-24 12:41:12,457 INFO L73 IsDeterministic]: Start isDeterministic. Operand 4 states and 418 transitions. [2023-08-24 12:41:12,457 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-24 12:41:12,457 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 4 states and 418 transitions. [2023-08-24 12:41:12,458 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 5 states, 4 states have (on average 104.5) internal successors, (418), 4 states have internal predecessors, (418), 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) [2023-08-24 12:41:12,460 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 5 states, 5 states have (on average 259.0) internal successors, (1295), 5 states have internal predecessors, (1295), 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) [2023-08-24 12:41:12,461 INFO L81 ComplementDD]: Finished complementDD. Result has 5 states, 5 states have (on average 259.0) internal successors, (1295), 5 states have internal predecessors, (1295), 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) [2023-08-24 12:41:12,461 INFO L175 Difference]: Start difference. First operand has 47 places, 33 transitions, 89 flow. Second operand 4 states and 418 transitions. [2023-08-24 12:41:12,461 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 42 places, 41 transitions, 178 flow [2023-08-24 12:41:12,463 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 41 places, 41 transitions, 175 flow, removed 0 selfloop flow, removed 1 redundant places. [2023-08-24 12:41:12,464 INFO L231 Difference]: Finished difference. Result has 41 places, 33 transitions, 106 flow [2023-08-24 12:41:12,464 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=259, PETRI_DIFFERENCE_MINUEND_FLOW=86, PETRI_DIFFERENCE_MINUEND_PLACES=38, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=33, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=10, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=23, PETRI_DIFFERENCE_SUBTRAHEND_STATES=4, PETRI_FLOW=106, PETRI_PLACES=41, PETRI_TRANSITIONS=33} [2023-08-24 12:41:12,465 INFO L281 CegarLoopForPetriNet]: 44 programPoint places, -3 predicate places. [2023-08-24 12:41:12,465 INFO L495 AbstractCegarLoop]: Abstraction has has 41 places, 33 transitions, 106 flow [2023-08-24 12:41:12,466 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 97.0) internal successors, (485), 5 states have internal predecessors, (485), 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) [2023-08-24 12:41:12,467 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-24 12:41:12,467 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-08-24 12:41:12,467 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5 [2023-08-24 12:41:12,467 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-08-24 12:41:12,467 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-24 12:41:12,467 INFO L85 PathProgramCache]: Analyzing trace with hash 959365680, now seen corresponding path program 1 times [2023-08-24 12:41:12,467 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-24 12:41:12,468 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [346570713] [2023-08-24 12:41:12,468 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-24 12:41:12,468 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-24 12:41:12,479 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-24 12:41:12,530 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-24 12:41:12,530 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-24 12:41:12,531 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [346570713] [2023-08-24 12:41:12,531 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [346570713] provided 0 perfect and 1 imperfect interpolant sequences [2023-08-24 12:41:12,531 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1144068877] [2023-08-24 12:41:12,531 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-24 12:41:12,532 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-24 12:41:12,533 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-08-24 12:41:12,537 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) [2023-08-24 12:41:12,551 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-08-24 12:41:12,620 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-24 12:41:12,621 INFO L262 TraceCheckSpWp]: Trace formula consists of 136 conjuncts, 3 conjunts are in the unsatisfiable core [2023-08-24 12:41:12,622 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-08-24 12:41:12,662 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-24 12:41:12,662 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-08-24 12:41:12,675 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-24 12:41:12,676 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1144068877] provided 0 perfect and 2 imperfect interpolant sequences [2023-08-24 12:41:12,676 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-08-24 12:41:12,676 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [3, 3, 3] total 5 [2023-08-24 12:41:12,676 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [815548996] [2023-08-24 12:41:12,676 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-08-24 12:41:12,676 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2023-08-24 12:41:12,677 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-24 12:41:12,677 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2023-08-24 12:41:12,677 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=15, Unknown=0, NotChecked=0, Total=30 [2023-08-24 12:41:12,678 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 116 out of 259 [2023-08-24 12:41:12,679 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 41 places, 33 transitions, 106 flow. Second operand has 6 states, 6 states have (on average 118.5) internal successors, (711), 6 states have internal predecessors, (711), 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) [2023-08-24 12:41:12,679 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-24 12:41:12,679 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 116 of 259 [2023-08-24 12:41:12,679 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-24 12:41:12,746 INFO L124 PetriNetUnfolderBase]: 210/436 cut-off events. [2023-08-24 12:41:12,747 INFO L125 PetriNetUnfolderBase]: For 88/88 co-relation queries the response was YES. [2023-08-24 12:41:12,747 INFO L83 FinitePrefix]: Finished finitePrefix Result has 980 conditions, 436 events. 210/436 cut-off events. For 88/88 co-relation queries the response was YES. Maximal size of possible extension queue 21. Compared 1963 event pairs, 2 based on Foata normal form. 0/434 useless extension candidates. Maximal degree in co-relation 269. Up to 274 conditions per place. [2023-08-24 12:41:12,748 INFO L140 encePairwiseOnDemand]: 256/259 looper letters, 0 selfloop transitions, 0 changer transitions 54/54 dead transitions. [2023-08-24 12:41:12,748 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 42 places, 54 transitions, 252 flow [2023-08-24 12:41:12,748 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-08-24 12:41:12,748 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 5 states. [2023-08-24 12:41:12,750 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 625 transitions. [2023-08-24 12:41:12,750 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.4826254826254826 [2023-08-24 12:41:12,750 INFO L72 ComplementDD]: Start complementDD. Operand 5 states and 625 transitions. [2023-08-24 12:41:12,750 INFO L73 IsDeterministic]: Start isDeterministic. Operand 5 states and 625 transitions. [2023-08-24 12:41:12,751 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-24 12:41:12,751 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 5 states and 625 transitions. [2023-08-24 12:41:12,752 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 6 states, 5 states have (on average 125.0) internal successors, (625), 5 states have internal predecessors, (625), 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) [2023-08-24 12:41:12,754 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 6 states, 6 states have (on average 259.0) internal successors, (1554), 6 states have internal predecessors, (1554), 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) [2023-08-24 12:41:12,754 INFO L81 ComplementDD]: Finished complementDD. Result has 6 states, 6 states have (on average 259.0) internal successors, (1554), 6 states have internal predecessors, (1554), 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) [2023-08-24 12:41:12,754 INFO L175 Difference]: Start difference. First operand has 41 places, 33 transitions, 106 flow. Second operand 5 states and 625 transitions. [2023-08-24 12:41:12,754 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 42 places, 54 transitions, 252 flow [2023-08-24 12:41:12,755 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 40 places, 54 transitions, 235 flow, removed 0 selfloop flow, removed 2 redundant places. [2023-08-24 12:41:12,756 INFO L231 Difference]: Finished difference. Result has 40 places, 0 transitions, 0 flow [2023-08-24 12:41:12,756 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=259, PETRI_DIFFERENCE_MINUEND_FLOW=87, PETRI_DIFFERENCE_MINUEND_PLACES=36, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=30, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=0, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=30, PETRI_DIFFERENCE_SUBTRAHEND_STATES=5, PETRI_FLOW=0, PETRI_PLACES=40, PETRI_TRANSITIONS=0} [2023-08-24 12:41:12,756 INFO L281 CegarLoopForPetriNet]: 44 programPoint places, -4 predicate places. [2023-08-24 12:41:12,756 INFO L495 AbstractCegarLoop]: Abstraction has has 40 places, 0 transitions, 0 flow [2023-08-24 12:41:12,757 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 118.5) internal successors, (711), 6 states have internal predecessors, (711), 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) [2023-08-24 12:41:12,757 INFO L805 garLoopResultBuilder]: Registering result SAFE for location ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2023-08-24 12:41:12,768 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2023-08-24 12:41:12,967 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable6 [2023-08-24 12:41:12,967 INFO L445 BasicCegarLoop]: Path program histogram: [1, 1, 1] [2023-08-24 12:41:12,968 INFO L307 ceAbstractionStarter]: Result for error location AllErrorsAtOnce was SAFE (1/2) [2023-08-24 12:41:12,969 INFO L73 FinitePrefix]: Start finitePrefix. Operand has 131 places, 146 transitions, 310 flow [2023-08-24 12:41:12,986 INFO L124 PetriNetUnfolderBase]: 32/241 cut-off events. [2023-08-24 12:41:12,986 INFO L125 PetriNetUnfolderBase]: For 6/6 co-relation queries the response was YES. [2023-08-24 12:41:12,987 INFO L83 FinitePrefix]: Finished finitePrefix Result has 255 conditions, 241 events. 32/241 cut-off events. For 6/6 co-relation queries the response was YES. Maximal size of possible extension queue 11. Compared 640 event pairs, 0 based on Foata normal form. 0/202 useless extension candidates. Maximal degree in co-relation 153. Up to 8 conditions per place. [2023-08-24 12:41:12,987 INFO L82 GeneralOperation]: Start removeDead. Operand has 131 places, 146 transitions, 310 flow [2023-08-24 12:41:12,989 INFO L88 GeneralOperation]: Finished RemoveDead, result has has 131 places, 146 transitions, 310 flow [2023-08-24 12:41:12,989 INFO L124 etLargeBlockEncoding]: Petri net LBE is using variable-based independence relation. [2023-08-24 12:41:12,989 INFO L131 etLargeBlockEncoding]: Starting large block encoding on Petri net that has 131 places, 146 transitions, 310 flow [2023-08-24 12:41:12,989 INFO L113 LiptonReduction]: Starting Lipton reduction on Petri net that has 131 places, 146 transitions, 310 flow [2023-08-24 12:41:12,989 INFO L73 FinitePrefix]: Start finitePrefix. Operand has 131 places, 146 transitions, 310 flow [2023-08-24 12:41:13,021 INFO L124 PetriNetUnfolderBase]: 32/241 cut-off events. [2023-08-24 12:41:13,021 INFO L125 PetriNetUnfolderBase]: For 6/6 co-relation queries the response was YES. [2023-08-24 12:41:13,022 INFO L83 FinitePrefix]: Finished finitePrefix Result has 255 conditions, 241 events. 32/241 cut-off events. For 6/6 co-relation queries the response was YES. Maximal size of possible extension queue 11. Compared 640 event pairs, 0 based on Foata normal form. 0/202 useless extension candidates. Maximal degree in co-relation 153. Up to 8 conditions per place. [2023-08-24 12:41:13,026 INFO L119 LiptonReduction]: Number of co-enabled transitions 6776 [2023-08-24 12:41:16,390 INFO L134 LiptonReduction]: Checked pairs total: 17059 [2023-08-24 12:41:16,390 INFO L136 LiptonReduction]: Total number of compositions: 111 [2023-08-24 12:41:16,392 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == InUseError ======== [2023-08-24 12:41:16,392 INFO L357 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=false, mAutomataTypeConcurrency=PETRI_NET, 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=false, mMcrInterpolantMethod=WP, mPorIndependenceSettings=[Lde.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings;@1e6d47e7, mLbeIndependenceSettings=[IndependenceType=SYNTACTIC, AbstractionType=NONE, UseConditional=, UseSemiCommutativity=, Solver=, SolverTimeout=] [2023-08-24 12:41:16,392 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-08-24 12:41:16,397 INFO L185 PetriNetUnfolderBase]: Found word, exiting Unfolder. [2023-08-24 12:41:16,397 INFO L124 PetriNetUnfolderBase]: 12/58 cut-off events. [2023-08-24 12:41:16,397 INFO L125 PetriNetUnfolderBase]: For 3/3 co-relation queries the response was YES. [2023-08-24 12:41:16,397 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-24 12:41:16,397 INFO L208 CegarLoopForPetriNet]: trace histogram [3, 2, 2, 1, 1, 1, 1] [2023-08-24 12:41:16,398 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES === [ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES] === [2023-08-24 12:41:16,398 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-24 12:41:16,398 INFO L85 PathProgramCache]: Analyzing trace with hash -2008130984, now seen corresponding path program 1 times [2023-08-24 12:41:16,398 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-24 12:41:16,398 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1613336744] [2023-08-24 12:41:16,398 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-24 12:41:16,398 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-24 12:41:16,410 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-08-24 12:41:16,410 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2023-08-24 12:41:16,416 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-08-24 12:41:16,420 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2023-08-24 12:41:16,421 INFO L360 BasicCegarLoop]: Counterexample is feasible [2023-08-24 12:41:16,421 INFO L805 garLoopResultBuilder]: Registering result UNSAFE for location ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (0 of 1 remaining) [2023-08-24 12:41:16,421 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7 [2023-08-24 12:41:16,421 INFO L445 BasicCegarLoop]: Path program histogram: [1] [2023-08-24 12:41:16,421 INFO L307 ceAbstractionStarter]: Result for error location InUseError was UNSAFE (2/2) [2023-08-24 12:41:16,422 WARN L233 ceAbstractionStarter]: 2 thread instances were not sufficient, I will increase this number and restart the analysis [2023-08-24 12:41:16,422 INFO L515 ceAbstractionStarter]: Constructing petrified ICFG for 3 thread instances. [2023-08-24 12:41:16,436 INFO L144 ThreadInstanceAdder]: Constructed 3 joinOtherThreadTransitions. [2023-08-24 12:41:16,438 INFO L73 FinitePrefix]: Start finitePrefix. Operand has 156 places, 176 transitions, 382 flow [2023-08-24 12:41:16,469 INFO L124 PetriNetUnfolderBase]: 51/364 cut-off events. [2023-08-24 12:41:16,470 INFO L125 PetriNetUnfolderBase]: For 19/19 co-relation queries the response was YES. [2023-08-24 12:41:16,472 INFO L83 FinitePrefix]: Finished finitePrefix Result has 392 conditions, 364 events. 51/364 cut-off events. For 19/19 co-relation queries the response was YES. Maximal size of possible extension queue 12. Compared 1133 event pairs, 1 based on Foata normal form. 0/305 useless extension candidates. Maximal degree in co-relation 249. Up to 16 conditions per place. [2023-08-24 12:41:16,473 INFO L82 GeneralOperation]: Start removeDead. Operand has 156 places, 176 transitions, 382 flow [2023-08-24 12:41:16,475 INFO L88 GeneralOperation]: Finished RemoveDead, result has has 156 places, 176 transitions, 382 flow [2023-08-24 12:41:16,475 INFO L124 etLargeBlockEncoding]: Petri net LBE is using variable-based independence relation. [2023-08-24 12:41:16,475 INFO L131 etLargeBlockEncoding]: Starting large block encoding on Petri net that has 156 places, 176 transitions, 382 flow [2023-08-24 12:41:16,475 INFO L113 LiptonReduction]: Starting Lipton reduction on Petri net that has 156 places, 176 transitions, 382 flow [2023-08-24 12:41:16,476 INFO L73 FinitePrefix]: Start finitePrefix. Operand has 156 places, 176 transitions, 382 flow [2023-08-24 12:41:16,507 INFO L124 PetriNetUnfolderBase]: 51/364 cut-off events. [2023-08-24 12:41:16,507 INFO L125 PetriNetUnfolderBase]: For 19/19 co-relation queries the response was YES. [2023-08-24 12:41:16,510 INFO L83 FinitePrefix]: Finished finitePrefix Result has 392 conditions, 364 events. 51/364 cut-off events. For 19/19 co-relation queries the response was YES. Maximal size of possible extension queue 12. Compared 1133 event pairs, 1 based on Foata normal form. 0/305 useless extension candidates. Maximal degree in co-relation 249. Up to 16 conditions per place. [2023-08-24 12:41:16,519 INFO L119 LiptonReduction]: Number of co-enabled transitions 12768 [2023-08-24 12:41:19,860 INFO L134 LiptonReduction]: Checked pairs total: 36680 [2023-08-24 12:41:19,861 INFO L136 LiptonReduction]: Total number of compositions: 127 [2023-08-24 12:41:19,862 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-08-24 12:41:19,862 INFO L357 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=false, mAutomataTypeConcurrency=PETRI_NET, 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=false, mMcrInterpolantMethod=WP, mPorIndependenceSettings=[Lde.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings;@1e6d47e7, mLbeIndependenceSettings=[IndependenceType=SYNTACTIC, AbstractionType=NONE, UseConditional=, UseSemiCommutativity=, Solver=, SolverTimeout=] [2023-08-24 12:41:19,863 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-08-24 12:41:19,864 INFO L185 PetriNetUnfolderBase]: Found word, exiting Unfolder. [2023-08-24 12:41:19,864 INFO L124 PetriNetUnfolderBase]: 1/10 cut-off events. [2023-08-24 12:41:19,864 INFO L125 PetriNetUnfolderBase]: For 0/0 co-relation queries the response was YES. [2023-08-24 12:41:19,865 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-24 12:41:19,865 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1] [2023-08-24 12:41:19,865 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-08-24 12:41:19,865 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-24 12:41:19,865 INFO L85 PathProgramCache]: Analyzing trace with hash 39471899, now seen corresponding path program 1 times [2023-08-24 12:41:19,865 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-24 12:41:19,865 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1566782782] [2023-08-24 12:41:19,865 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-24 12:41:19,866 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-24 12:41:19,878 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-24 12:41:19,901 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-24 12:41:19,901 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-24 12:41:19,901 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1566782782] [2023-08-24 12:41:19,901 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1566782782] provided 1 perfect and 0 imperfect interpolant sequences [2023-08-24 12:41:19,901 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-08-24 12:41:19,901 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2023-08-24 12:41:19,902 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1891202925] [2023-08-24 12:41:19,902 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-08-24 12:41:19,902 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-08-24 12:41:19,902 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-24 12:41:19,902 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-08-24 12:41:19,902 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-08-24 12:41:19,903 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 132 out of 303 [2023-08-24 12:41:19,903 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 58 places, 74 transitions, 178 flow. Second operand has 3 states, 3 states have (on average 133.33333333333334) internal successors, (400), 3 states have internal predecessors, (400), 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) [2023-08-24 12:41:19,904 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-24 12:41:19,904 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 132 of 303 [2023-08-24 12:41:19,904 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-24 12:41:22,931 INFO L124 PetriNetUnfolderBase]: 29246/43200 cut-off events. [2023-08-24 12:41:22,931 INFO L125 PetriNetUnfolderBase]: For 1215/1215 co-relation queries the response was YES. [2023-08-24 12:41:23,014 INFO L83 FinitePrefix]: Finished finitePrefix Result has 85148 conditions, 43200 events. 29246/43200 cut-off events. For 1215/1215 co-relation queries the response was YES. Maximal size of possible extension queue 1107. Compared 290415 event pairs, 12184 based on Foata normal form. 8202/48183 useless extension candidates. Maximal degree in co-relation 48393. Up to 39840 conditions per place. [2023-08-24 12:41:23,120 INFO L140 encePairwiseOnDemand]: 278/303 looper letters, 47 selfloop transitions, 4 changer transitions 16/75 dead transitions. [2023-08-24 12:41:23,120 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 60 places, 75 transitions, 322 flow [2023-08-24 12:41:23,120 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-08-24 12:41:23,121 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3 states. [2023-08-24 12:41:23,122 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 490 transitions. [2023-08-24 12:41:23,122 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.5390539053905391 [2023-08-24 12:41:23,122 INFO L72 ComplementDD]: Start complementDD. Operand 3 states and 490 transitions. [2023-08-24 12:41:23,122 INFO L73 IsDeterministic]: Start isDeterministic. Operand 3 states and 490 transitions. [2023-08-24 12:41:23,123 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-24 12:41:23,123 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 3 states and 490 transitions. [2023-08-24 12:41:23,124 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 4 states, 3 states have (on average 163.33333333333334) internal successors, (490), 3 states have internal predecessors, (490), 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) [2023-08-24 12:41:23,125 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 4 states, 4 states have (on average 303.0) internal successors, (1212), 4 states have internal predecessors, (1212), 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) [2023-08-24 12:41:23,126 INFO L81 ComplementDD]: Finished complementDD. Result has 4 states, 4 states have (on average 303.0) internal successors, (1212), 4 states have internal predecessors, (1212), 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) [2023-08-24 12:41:23,126 INFO L175 Difference]: Start difference. First operand has 58 places, 74 transitions, 178 flow. Second operand 3 states and 490 transitions. [2023-08-24 12:41:23,126 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 60 places, 75 transitions, 322 flow [2023-08-24 12:41:23,130 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 60 places, 75 transitions, 322 flow, removed 0 selfloop flow, removed 0 redundant places. [2023-08-24 12:41:23,132 INFO L231 Difference]: Finished difference. Result has 61 places, 46 transitions, 127 flow [2023-08-24 12:41:23,132 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=303, PETRI_DIFFERENCE_MINUEND_FLOW=138, PETRI_DIFFERENCE_MINUEND_PLACES=58, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=54, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=1, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=50, PETRI_DIFFERENCE_SUBTRAHEND_STATES=3, PETRI_FLOW=127, PETRI_PLACES=61, PETRI_TRANSITIONS=46} [2023-08-24 12:41:23,133 INFO L281 CegarLoopForPetriNet]: 58 programPoint places, 3 predicate places. [2023-08-24 12:41:23,133 INFO L495 AbstractCegarLoop]: Abstraction has has 61 places, 46 transitions, 127 flow [2023-08-24 12:41:23,133 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 133.33333333333334) internal successors, (400), 3 states have internal predecessors, (400), 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) [2023-08-24 12:41:23,133 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-24 12:41:23,133 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-08-24 12:41:23,134 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8 [2023-08-24 12:41:23,134 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-08-24 12:41:23,134 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-24 12:41:23,134 INFO L85 PathProgramCache]: Analyzing trace with hash 1253656491, now seen corresponding path program 1 times [2023-08-24 12:41:23,134 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-24 12:41:23,135 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [383747299] [2023-08-24 12:41:23,135 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-24 12:41:23,135 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-24 12:41:23,156 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-24 12:41:23,297 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-24 12:41:23,298 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-24 12:41:23,298 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [383747299] [2023-08-24 12:41:23,298 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [383747299] provided 0 perfect and 1 imperfect interpolant sequences [2023-08-24 12:41:23,298 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [422596384] [2023-08-24 12:41:23,298 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-24 12:41:23,298 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-24 12:41:23,298 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-08-24 12:41:23,305 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) [2023-08-24 12:41:23,333 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-08-24 12:41:23,384 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-24 12:41:23,386 INFO L262 TraceCheckSpWp]: Trace formula consists of 142 conjuncts, 3 conjunts are in the unsatisfiable core [2023-08-24 12:41:23,387 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-08-24 12:41:23,409 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-24 12:41:23,409 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-08-24 12:41:23,422 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-24 12:41:23,422 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [422596384] provided 0 perfect and 2 imperfect interpolant sequences [2023-08-24 12:41:23,422 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-08-24 12:41:23,422 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [3, 3, 3] total 5 [2023-08-24 12:41:23,423 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [287597214] [2023-08-24 12:41:23,423 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-08-24 12:41:23,423 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2023-08-24 12:41:23,423 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-24 12:41:23,424 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2023-08-24 12:41:23,424 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=15, Unknown=0, NotChecked=0, Total=30 [2023-08-24 12:41:23,424 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 138 out of 303 [2023-08-24 12:41:23,425 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 61 places, 46 transitions, 127 flow. Second operand has 6 states, 6 states have (on average 140.5) internal successors, (843), 6 states have internal predecessors, (843), 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) [2023-08-24 12:41:23,425 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-24 12:41:23,425 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 138 of 303 [2023-08-24 12:41:23,425 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-24 12:41:23,996 INFO L124 PetriNetUnfolderBase]: 5560/8383 cut-off events. [2023-08-24 12:41:23,996 INFO L125 PetriNetUnfolderBase]: For 1009/1009 co-relation queries the response was YES. [2023-08-24 12:41:24,005 INFO L83 FinitePrefix]: Finished finitePrefix Result has 17651 conditions, 8383 events. 5560/8383 cut-off events. For 1009/1009 co-relation queries the response was YES. Maximal size of possible extension queue 271. Compared 49577 event pairs, 0 based on Foata normal form. 0/8383 useless extension candidates. Maximal degree in co-relation 11324. Up to 5346 conditions per place. [2023-08-24 12:41:24,011 INFO L140 encePairwiseOnDemand]: 300/303 looper letters, 0 selfloop transitions, 0 changer transitions 101/101 dead transitions. [2023-08-24 12:41:24,012 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 55 places, 101 transitions, 445 flow [2023-08-24 12:41:24,013 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-08-24 12:41:24,013 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 6 states. [2023-08-24 12:41:24,015 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 915 transitions. [2023-08-24 12:41:24,015 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.5033003300330033 [2023-08-24 12:41:24,015 INFO L72 ComplementDD]: Start complementDD. Operand 6 states and 915 transitions. [2023-08-24 12:41:24,015 INFO L73 IsDeterministic]: Start isDeterministic. Operand 6 states and 915 transitions. [2023-08-24 12:41:24,016 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-24 12:41:24,016 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 6 states and 915 transitions. [2023-08-24 12:41:24,018 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 7 states, 6 states have (on average 152.5) internal successors, (915), 6 states have internal predecessors, (915), 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) [2023-08-24 12:41:24,021 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 7 states, 7 states have (on average 303.0) internal successors, (2121), 7 states have internal predecessors, (2121), 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) [2023-08-24 12:41:24,021 INFO L81 ComplementDD]: Finished complementDD. Result has 7 states, 7 states have (on average 303.0) internal successors, (2121), 7 states have internal predecessors, (2121), 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) [2023-08-24 12:41:24,021 INFO L175 Difference]: Start difference. First operand has 61 places, 46 transitions, 127 flow. Second operand 6 states and 915 transitions. [2023-08-24 12:41:24,021 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 55 places, 101 transitions, 445 flow [2023-08-24 12:41:24,023 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 54 places, 101 transitions, 433 flow, removed 1 selfloop flow, removed 1 redundant places. [2023-08-24 12:41:24,024 INFO L231 Difference]: Finished difference. Result has 54 places, 0 transitions, 0 flow [2023-08-24 12:41:24,024 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=303, PETRI_DIFFERENCE_MINUEND_FLOW=113, PETRI_DIFFERENCE_MINUEND_PLACES=49, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=43, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=0, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=43, PETRI_DIFFERENCE_SUBTRAHEND_STATES=6, PETRI_FLOW=0, PETRI_PLACES=54, PETRI_TRANSITIONS=0} [2023-08-24 12:41:24,024 INFO L281 CegarLoopForPetriNet]: 58 programPoint places, -4 predicate places. [2023-08-24 12:41:24,025 INFO L495 AbstractCegarLoop]: Abstraction has has 54 places, 0 transitions, 0 flow [2023-08-24 12:41:24,025 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 140.5) internal successors, (843), 6 states have internal predecessors, (843), 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) [2023-08-24 12:41:24,025 INFO L805 garLoopResultBuilder]: Registering result SAFE for location ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2023-08-24 12:41:24,035 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2023-08-24 12:41:24,230 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-24 12:41:24,230 INFO L445 BasicCegarLoop]: Path program histogram: [1, 1] [2023-08-24 12:41:24,231 INFO L307 ceAbstractionStarter]: Result for error location AllErrorsAtOnce was SAFE (1/2) [2023-08-24 12:41:24,235 INFO L73 FinitePrefix]: Start finitePrefix. Operand has 156 places, 176 transitions, 382 flow [2023-08-24 12:41:24,272 INFO L124 PetriNetUnfolderBase]: 51/364 cut-off events. [2023-08-24 12:41:24,272 INFO L125 PetriNetUnfolderBase]: For 19/19 co-relation queries the response was YES. [2023-08-24 12:41:24,274 INFO L83 FinitePrefix]: Finished finitePrefix Result has 392 conditions, 364 events. 51/364 cut-off events. For 19/19 co-relation queries the response was YES. Maximal size of possible extension queue 12. Compared 1133 event pairs, 1 based on Foata normal form. 0/305 useless extension candidates. Maximal degree in co-relation 249. Up to 16 conditions per place. [2023-08-24 12:41:24,275 INFO L82 GeneralOperation]: Start removeDead. Operand has 156 places, 176 transitions, 382 flow [2023-08-24 12:41:24,277 INFO L88 GeneralOperation]: Finished RemoveDead, result has has 156 places, 176 transitions, 382 flow [2023-08-24 12:41:24,277 INFO L124 etLargeBlockEncoding]: Petri net LBE is using variable-based independence relation. [2023-08-24 12:41:24,277 INFO L131 etLargeBlockEncoding]: Starting large block encoding on Petri net that has 156 places, 176 transitions, 382 flow [2023-08-24 12:41:24,277 INFO L113 LiptonReduction]: Starting Lipton reduction on Petri net that has 156 places, 176 transitions, 382 flow [2023-08-24 12:41:24,277 INFO L73 FinitePrefix]: Start finitePrefix. Operand has 156 places, 176 transitions, 382 flow [2023-08-24 12:41:24,312 INFO L124 PetriNetUnfolderBase]: 51/364 cut-off events. [2023-08-24 12:41:24,312 INFO L125 PetriNetUnfolderBase]: For 19/19 co-relation queries the response was YES. [2023-08-24 12:41:24,314 INFO L83 FinitePrefix]: Finished finitePrefix Result has 392 conditions, 364 events. 51/364 cut-off events. For 19/19 co-relation queries the response was YES. Maximal size of possible extension queue 12. Compared 1133 event pairs, 1 based on Foata normal form. 0/305 useless extension candidates. Maximal degree in co-relation 249. Up to 16 conditions per place. [2023-08-24 12:41:24,323 INFO L119 LiptonReduction]: Number of co-enabled transitions 12768 [2023-08-24 12:41:27,458 INFO L134 LiptonReduction]: Checked pairs total: 36701 [2023-08-24 12:41:27,458 INFO L136 LiptonReduction]: Total number of compositions: 125 [2023-08-24 12:41:27,459 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == InUseError ======== [2023-08-24 12:41:27,460 INFO L357 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=false, mAutomataTypeConcurrency=PETRI_NET, 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=false, mMcrInterpolantMethod=WP, mPorIndependenceSettings=[Lde.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings;@1e6d47e7, mLbeIndependenceSettings=[IndependenceType=SYNTACTIC, AbstractionType=NONE, UseConditional=, UseSemiCommutativity=, Solver=, SolverTimeout=] [2023-08-24 12:41:27,460 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-08-24 12:41:27,467 INFO L185 PetriNetUnfolderBase]: Found word, exiting Unfolder. [2023-08-24 12:41:27,467 INFO L124 PetriNetUnfolderBase]: 24/99 cut-off events. [2023-08-24 12:41:27,467 INFO L125 PetriNetUnfolderBase]: For 10/10 co-relation queries the response was YES. [2023-08-24 12:41:27,467 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-24 12:41:27,467 INFO L208 CegarLoopForPetriNet]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1] [2023-08-24 12:41:27,468 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES === [ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES] === [2023-08-24 12:41:27,468 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-24 12:41:27,468 INFO L85 PathProgramCache]: Analyzing trace with hash 1539819468, now seen corresponding path program 1 times [2023-08-24 12:41:27,468 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-24 12:41:27,468 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2133325361] [2023-08-24 12:41:27,468 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-24 12:41:27,469 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-24 12:41:27,481 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-08-24 12:41:27,481 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2023-08-24 12:41:27,489 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-08-24 12:41:27,493 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2023-08-24 12:41:27,494 INFO L360 BasicCegarLoop]: Counterexample is feasible [2023-08-24 12:41:27,494 INFO L805 garLoopResultBuilder]: Registering result UNSAFE for location ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (0 of 1 remaining) [2023-08-24 12:41:27,494 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10 [2023-08-24 12:41:27,497 INFO L445 BasicCegarLoop]: Path program histogram: [1] [2023-08-24 12:41:27,498 INFO L307 ceAbstractionStarter]: Result for error location InUseError was UNSAFE (2/2) [2023-08-24 12:41:27,498 WARN L233 ceAbstractionStarter]: 3 thread instances were not sufficient, I will increase this number and restart the analysis [2023-08-24 12:41:27,499 INFO L515 ceAbstractionStarter]: Constructing petrified ICFG for 4 thread instances. [2023-08-24 12:41:27,524 INFO L144 ThreadInstanceAdder]: Constructed 4 joinOtherThreadTransitions. [2023-08-24 12:41:27,526 INFO L73 FinitePrefix]: Start finitePrefix. Operand has 181 places, 206 transitions, 456 flow [2023-08-24 12:41:27,592 INFO L124 PetriNetUnfolderBase]: 82/555 cut-off events. [2023-08-24 12:41:27,592 INFO L125 PetriNetUnfolderBase]: For 48/48 co-relation queries the response was YES. [2023-08-24 12:41:27,597 INFO L83 FinitePrefix]: Finished finitePrefix Result has 610 conditions, 555 events. 82/555 cut-off events. For 48/48 co-relation queries the response was YES. Maximal size of possible extension queue 15. Compared 2020 event pairs, 6 based on Foata normal form. 0/468 useless extension candidates. Maximal degree in co-relation 384. Up to 32 conditions per place. [2023-08-24 12:41:27,598 INFO L82 GeneralOperation]: Start removeDead. Operand has 181 places, 206 transitions, 456 flow [2023-08-24 12:41:27,601 INFO L88 GeneralOperation]: Finished RemoveDead, result has has 181 places, 206 transitions, 456 flow [2023-08-24 12:41:27,601 INFO L124 etLargeBlockEncoding]: Petri net LBE is using variable-based independence relation. [2023-08-24 12:41:27,601 INFO L131 etLargeBlockEncoding]: Starting large block encoding on Petri net that has 181 places, 206 transitions, 456 flow [2023-08-24 12:41:27,602 INFO L113 LiptonReduction]: Starting Lipton reduction on Petri net that has 181 places, 206 transitions, 456 flow [2023-08-24 12:41:27,602 INFO L73 FinitePrefix]: Start finitePrefix. Operand has 181 places, 206 transitions, 456 flow [2023-08-24 12:41:27,667 INFO L124 PetriNetUnfolderBase]: 82/555 cut-off events. [2023-08-24 12:41:27,668 INFO L125 PetriNetUnfolderBase]: For 48/48 co-relation queries the response was YES. [2023-08-24 12:41:27,673 INFO L83 FinitePrefix]: Finished finitePrefix Result has 610 conditions, 555 events. 82/555 cut-off events. For 48/48 co-relation queries the response was YES. Maximal size of possible extension queue 15. Compared 2020 event pairs, 6 based on Foata normal form. 0/468 useless extension candidates. Maximal degree in co-relation 384. Up to 32 conditions per place. [2023-08-24 12:41:27,687 INFO L119 LiptonReduction]: Number of co-enabled transitions 20496 [2023-08-24 12:41:31,132 INFO L134 LiptonReduction]: Checked pairs total: 55995 [2023-08-24 12:41:31,133 INFO L136 LiptonReduction]: Total number of compositions: 142 [2023-08-24 12:41:31,134 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-08-24 12:41:31,134 INFO L357 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=false, mAutomataTypeConcurrency=PETRI_NET, 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=false, mMcrInterpolantMethod=WP, mPorIndependenceSettings=[Lde.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings;@1e6d47e7, mLbeIndependenceSettings=[IndependenceType=SYNTACTIC, AbstractionType=NONE, UseConditional=, UseSemiCommutativity=, Solver=, SolverTimeout=] [2023-08-24 12:41:31,134 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-08-24 12:41:31,136 INFO L185 PetriNetUnfolderBase]: Found word, exiting Unfolder. [2023-08-24 12:41:31,136 INFO L124 PetriNetUnfolderBase]: 3/15 cut-off events. [2023-08-24 12:41:31,136 INFO L125 PetriNetUnfolderBase]: For 0/0 co-relation queries the response was YES. [2023-08-24 12:41:31,136 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-24 12:41:31,136 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1] [2023-08-24 12:41:31,136 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-08-24 12:41:31,137 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-24 12:41:31,137 INFO L85 PathProgramCache]: Analyzing trace with hash 54957924, now seen corresponding path program 1 times [2023-08-24 12:41:31,137 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-24 12:41:31,137 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1107382998] [2023-08-24 12:41:31,137 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-24 12:41:31,137 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-24 12:41:31,149 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-24 12:41:31,171 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-24 12:41:31,171 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-24 12:41:31,171 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1107382998] [2023-08-24 12:41:31,171 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1107382998] provided 1 perfect and 0 imperfect interpolant sequences [2023-08-24 12:41:31,171 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-08-24 12:41:31,171 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2023-08-24 12:41:31,171 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1566667969] [2023-08-24 12:41:31,172 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-08-24 12:41:31,172 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-08-24 12:41:31,172 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-24 12:41:31,172 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-08-24 12:41:31,172 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-08-24 12:41:31,173 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 150 out of 348 [2023-08-24 12:41:31,175 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 73 places, 95 transitions, 234 flow. Second operand has 3 states, 3 states have (on average 151.33333333333334) internal successors, (454), 3 states have internal predecessors, (454), 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) [2023-08-24 12:41:31,175 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-24 12:41:31,175 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 150 of 348 [2023-08-24 12:41:31,175 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-24 12:42:10,649 INFO L124 PetriNetUnfolderBase]: 501939/671464 cut-off events. [2023-08-24 12:42:10,649 INFO L125 PetriNetUnfolderBase]: For 24372/24372 co-relation queries the response was YES. [2023-08-24 12:42:12,037 INFO L83 FinitePrefix]: Finished finitePrefix Result has 1335973 conditions, 671464 events. 501939/671464 cut-off events. For 24372/24372 co-relation queries the response was YES. Maximal size of possible extension queue 12093. Compared 4856944 event pairs, 241195 based on Foata normal form. 99336/729982 useless extension candidates. Maximal degree in co-relation 576890. Up to 644905 conditions per place. [2023-08-24 12:42:13,300 INFO L140 encePairwiseOnDemand]: 315/348 looper letters, 63 selfloop transitions, 5 changer transitions 17/93 dead transitions. [2023-08-24 12:42:13,300 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 74 places, 93 transitions, 417 flow [2023-08-24 12:42:13,301 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-08-24 12:42:13,301 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3 states. [2023-08-24 12:42:13,302 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 572 transitions. [2023-08-24 12:42:13,304 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.5478927203065134 [2023-08-24 12:42:13,304 INFO L72 ComplementDD]: Start complementDD. Operand 3 states and 572 transitions. [2023-08-24 12:42:13,304 INFO L73 IsDeterministic]: Start isDeterministic. Operand 3 states and 572 transitions. [2023-08-24 12:42:13,304 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-24 12:42:13,305 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 3 states and 572 transitions. [2023-08-24 12:42:13,306 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 4 states, 3 states have (on average 190.66666666666666) internal successors, (572), 3 states have internal predecessors, (572), 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) [2023-08-24 12:42:13,307 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 4 states, 4 states have (on average 348.0) internal successors, (1392), 4 states have internal predecessors, (1392), 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) [2023-08-24 12:42:13,308 INFO L81 ComplementDD]: Finished complementDD. Result has 4 states, 4 states have (on average 348.0) internal successors, (1392), 4 states have internal predecessors, (1392), 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) [2023-08-24 12:42:13,308 INFO L175 Difference]: Start difference. First operand has 73 places, 95 transitions, 234 flow. Second operand 3 states and 572 transitions. [2023-08-24 12:42:13,308 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 74 places, 93 transitions, 417 flow [2023-08-24 12:42:13,374 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 74 places, 93 transitions, 417 flow, removed 0 selfloop flow, removed 0 redundant places. [2023-08-24 12:42:13,376 INFO L231 Difference]: Finished difference. Result has 75 places, 59 transitions, 167 flow [2023-08-24 12:42:13,376 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=348, PETRI_DIFFERENCE_MINUEND_FLOW=178, PETRI_DIFFERENCE_MINUEND_PLACES=72, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=67, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=1, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=62, PETRI_DIFFERENCE_SUBTRAHEND_STATES=3, PETRI_FLOW=167, PETRI_PLACES=75, PETRI_TRANSITIONS=59} [2023-08-24 12:42:13,376 INFO L281 CegarLoopForPetriNet]: 73 programPoint places, 2 predicate places. [2023-08-24 12:42:13,377 INFO L495 AbstractCegarLoop]: Abstraction has has 75 places, 59 transitions, 167 flow [2023-08-24 12:42:13,377 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 151.33333333333334) internal successors, (454), 3 states have internal predecessors, (454), 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) [2023-08-24 12:42:13,377 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-24 12:42:13,377 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-08-24 12:42:13,377 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11 [2023-08-24 12:42:13,377 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-08-24 12:42:13,377 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-24 12:42:13,378 INFO L85 PathProgramCache]: Analyzing trace with hash -1664689848, now seen corresponding path program 1 times [2023-08-24 12:42:13,378 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-24 12:42:13,378 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [897443285] [2023-08-24 12:42:13,378 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-24 12:42:13,378 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-24 12:42:13,386 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-24 12:42:13,414 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-24 12:42:13,414 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-24 12:42:13,414 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [897443285] [2023-08-24 12:42:13,414 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [897443285] provided 0 perfect and 1 imperfect interpolant sequences [2023-08-24 12:42:13,414 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [521213959] [2023-08-24 12:42:13,414 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-24 12:42:13,415 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-24 12:42:13,415 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-08-24 12:42:13,416 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) [2023-08-24 12:42:13,444 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-08-24 12:42:13,501 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-24 12:42:13,503 INFO L262 TraceCheckSpWp]: Trace formula consists of 130 conjuncts, 3 conjunts are in the unsatisfiable core [2023-08-24 12:42:13,505 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-08-24 12:42:13,547 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-24 12:42:13,547 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-08-24 12:42:13,564 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-24 12:42:13,564 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [521213959] provided 0 perfect and 2 imperfect interpolant sequences [2023-08-24 12:42:13,564 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-08-24 12:42:13,564 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [3, 3, 3] total 5 [2023-08-24 12:42:13,567 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [876142165] [2023-08-24 12:42:13,567 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-08-24 12:42:13,567 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2023-08-24 12:42:13,567 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-24 12:42:13,568 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2023-08-24 12:42:13,568 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=15, Unknown=0, NotChecked=0, Total=30 [2023-08-24 12:42:13,569 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 160 out of 348 [2023-08-24 12:42:13,570 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 75 places, 59 transitions, 167 flow. Second operand has 6 states, 6 states have (on average 162.5) internal successors, (975), 6 states have internal predecessors, (975), 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) [2023-08-24 12:42:13,570 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-24 12:42:13,570 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 160 of 348 [2023-08-24 12:42:13,570 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-24 12:42:21,858 INFO L124 PetriNetUnfolderBase]: 107478/144055 cut-off events. [2023-08-24 12:42:21,858 INFO L125 PetriNetUnfolderBase]: For 13381/13381 co-relation queries the response was YES. [2023-08-24 12:42:22,189 INFO L83 FinitePrefix]: Finished finitePrefix Result has 305485 conditions, 144055 events. 107478/144055 cut-off events. For 13381/13381 co-relation queries the response was YES. Maximal size of possible extension queue 3834. Compared 998994 event pairs, 8636 based on Foata normal form. 0/137966 useless extension candidates. Maximal degree in co-relation 183872. Up to 91786 conditions per place. [2023-08-24 12:42:23,006 INFO L140 encePairwiseOnDemand]: 344/348 looper letters, 120 selfloop transitions, 6 changer transitions 0/143 dead transitions. [2023-08-24 12:42:23,006 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 72 places, 143 transitions, 620 flow [2023-08-24 12:42:23,006 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-08-24 12:42:23,007 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 6 states. [2023-08-24 12:42:23,009 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 1081 transitions. [2023-08-24 12:42:23,009 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.51772030651341 [2023-08-24 12:42:23,009 INFO L72 ComplementDD]: Start complementDD. Operand 6 states and 1081 transitions. [2023-08-24 12:42:23,010 INFO L73 IsDeterministic]: Start isDeterministic. Operand 6 states and 1081 transitions. [2023-08-24 12:42:23,010 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-24 12:42:23,010 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 6 states and 1081 transitions. [2023-08-24 12:42:23,013 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 7 states, 6 states have (on average 180.16666666666666) internal successors, (1081), 6 states have internal predecessors, (1081), 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) [2023-08-24 12:42:23,016 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 7 states, 7 states have (on average 348.0) internal successors, (2436), 7 states have internal predecessors, (2436), 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) [2023-08-24 12:42:23,017 INFO L81 ComplementDD]: Finished complementDD. Result has 7 states, 7 states have (on average 348.0) internal successors, (2436), 7 states have internal predecessors, (2436), 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) [2023-08-24 12:42:23,017 INFO L175 Difference]: Start difference. First operand has 75 places, 59 transitions, 167 flow. Second operand 6 states and 1081 transitions. [2023-08-24 12:42:23,017 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 72 places, 143 transitions, 620 flow [2023-08-24 12:42:23,021 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 71 places, 143 transitions, 602 flow, removed 3 selfloop flow, removed 1 redundant places. [2023-08-24 12:42:23,023 INFO L231 Difference]: Finished difference. Result has 76 places, 63 transitions, 198 flow [2023-08-24 12:42:23,023 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=348, PETRI_DIFFERENCE_MINUEND_FLOW=156, PETRI_DIFFERENCE_MINUEND_PLACES=66, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=59, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=2, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=56, PETRI_DIFFERENCE_SUBTRAHEND_STATES=6, PETRI_FLOW=198, PETRI_PLACES=76, PETRI_TRANSITIONS=63} [2023-08-24 12:42:23,023 INFO L281 CegarLoopForPetriNet]: 73 programPoint places, 3 predicate places. [2023-08-24 12:42:23,023 INFO L495 AbstractCegarLoop]: Abstraction has has 76 places, 63 transitions, 198 flow [2023-08-24 12:42:23,024 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 162.5) internal successors, (975), 6 states have internal predecessors, (975), 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) [2023-08-24 12:42:23,024 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-24 12:42:23,024 INFO L208 CegarLoopForPetriNet]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-08-24 12:42:23,033 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2023-08-24 12:42:23,233 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable12,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-24 12:42:23,233 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-08-24 12:42:23,233 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-24 12:42:23,234 INFO L85 PathProgramCache]: Analyzing trace with hash -1786367278, now seen corresponding path program 1 times [2023-08-24 12:42:23,234 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-24 12:42:23,234 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [593345010] [2023-08-24 12:42:23,234 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-24 12:42:23,234 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-24 12:42:23,246 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-24 12:42:23,306 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-24 12:42:23,307 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-24 12:42:23,307 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [593345010] [2023-08-24 12:42:23,307 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [593345010] provided 0 perfect and 1 imperfect interpolant sequences [2023-08-24 12:42:23,307 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [784428277] [2023-08-24 12:42:23,307 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-24 12:42:23,307 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-24 12:42:23,307 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-08-24 12:42:23,308 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) [2023-08-24 12:42:23,334 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-08-24 12:42:23,406 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-24 12:42:23,407 INFO L262 TraceCheckSpWp]: Trace formula consists of 184 conjuncts, 6 conjunts are in the unsatisfiable core [2023-08-24 12:42:23,410 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-08-24 12:42:23,465 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-24 12:42:23,465 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-08-24 12:42:23,522 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-24 12:42:23,523 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [784428277] provided 0 perfect and 2 imperfect interpolant sequences [2023-08-24 12:42:23,523 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-08-24 12:42:23,523 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 6] total 11 [2023-08-24 12:42:23,523 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1849391684] [2023-08-24 12:42:23,523 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-08-24 12:42:23,523 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2023-08-24 12:42:23,524 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-24 12:42:23,524 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2023-08-24 12:42:23,524 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=66, Invalid=66, Unknown=0, NotChecked=0, Total=132 [2023-08-24 12:42:23,526 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 160 out of 348 [2023-08-24 12:42:23,527 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 76 places, 63 transitions, 198 flow. Second operand has 12 states, 12 states have (on average 163.0) internal successors, (1956), 12 states have internal predecessors, (1956), 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) [2023-08-24 12:42:23,527 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-24 12:42:23,527 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 160 of 348 [2023-08-24 12:42:23,528 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-24 12:42:28,085 INFO L124 PetriNetUnfolderBase]: 53863/73568 cut-off events. [2023-08-24 12:42:28,085 INFO L125 PetriNetUnfolderBase]: For 41673/41673 co-relation queries the response was YES. [2023-08-24 12:42:28,311 INFO L83 FinitePrefix]: Finished finitePrefix Result has 175594 conditions, 73568 events. 53863/73568 cut-off events. For 41673/41673 co-relation queries the response was YES. Maximal size of possible extension queue 2029. Compared 490495 event pairs, 2312 based on Foata normal form. 5157/78370 useless extension candidates. Maximal degree in co-relation 61392. Up to 46485 conditions per place. [2023-08-24 12:42:28,359 INFO L140 encePairwiseOnDemand]: 345/348 looper letters, 0 selfloop transitions, 0 changer transitions 140/140 dead transitions. [2023-08-24 12:42:28,359 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 79 places, 140 transitions, 620 flow [2023-08-24 12:42:28,360 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2023-08-24 12:42:28,360 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 7 states. [2023-08-24 12:42:28,361 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 1235 transitions. [2023-08-24 12:42:28,362 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.5069786535303776 [2023-08-24 12:42:28,362 INFO L72 ComplementDD]: Start complementDD. Operand 7 states and 1235 transitions. [2023-08-24 12:42:28,362 INFO L73 IsDeterministic]: Start isDeterministic. Operand 7 states and 1235 transitions. [2023-08-24 12:42:28,363 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-24 12:42:28,363 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 7 states and 1235 transitions. [2023-08-24 12:42:28,366 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 8 states, 7 states have (on average 176.42857142857142) internal successors, (1235), 7 states have internal predecessors, (1235), 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) [2023-08-24 12:42:28,369 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 8 states, 8 states have (on average 348.0) internal successors, (2784), 8 states have internal predecessors, (2784), 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) [2023-08-24 12:42:28,370 INFO L81 ComplementDD]: Finished complementDD. Result has 8 states, 8 states have (on average 348.0) internal successors, (2784), 8 states have internal predecessors, (2784), 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) [2023-08-24 12:42:28,370 INFO L175 Difference]: Start difference. First operand has 76 places, 63 transitions, 198 flow. Second operand 7 states and 1235 transitions. [2023-08-24 12:42:28,370 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 79 places, 140 transitions, 620 flow [2023-08-24 12:42:28,408 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 75 places, 140 transitions, 611 flow, removed 0 selfloop flow, removed 4 redundant places. [2023-08-24 12:42:28,409 INFO L231 Difference]: Finished difference. Result has 75 places, 0 transitions, 0 flow [2023-08-24 12:42:28,410 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=348, PETRI_DIFFERENCE_MINUEND_FLOW=173, PETRI_DIFFERENCE_MINUEND_PLACES=69, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=60, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=0, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=60, PETRI_DIFFERENCE_SUBTRAHEND_STATES=7, PETRI_FLOW=0, PETRI_PLACES=75, PETRI_TRANSITIONS=0} [2023-08-24 12:42:28,410 INFO L281 CegarLoopForPetriNet]: 73 programPoint places, 2 predicate places. [2023-08-24 12:42:28,410 INFO L495 AbstractCegarLoop]: Abstraction has has 75 places, 0 transitions, 0 flow [2023-08-24 12:42:28,411 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 163.0) internal successors, (1956), 12 states have internal predecessors, (1956), 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) [2023-08-24 12:42:28,411 INFO L805 garLoopResultBuilder]: Registering result SAFE for location ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2023-08-24 12:42:28,419 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2023-08-24 12:42:28,616 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2023-08-24 12:42:28,616 INFO L445 BasicCegarLoop]: Path program histogram: [1, 1, 1] [2023-08-24 12:42:28,616 INFO L307 ceAbstractionStarter]: Result for error location AllErrorsAtOnce was SAFE (1/2) [2023-08-24 12:42:28,618 INFO L73 FinitePrefix]: Start finitePrefix. Operand has 181 places, 206 transitions, 456 flow [2023-08-24 12:42:28,650 INFO L124 PetriNetUnfolderBase]: 82/555 cut-off events. [2023-08-24 12:42:28,650 INFO L125 PetriNetUnfolderBase]: For 48/48 co-relation queries the response was YES. [2023-08-24 12:42:28,654 INFO L83 FinitePrefix]: Finished finitePrefix Result has 610 conditions, 555 events. 82/555 cut-off events. For 48/48 co-relation queries the response was YES. Maximal size of possible extension queue 15. Compared 2020 event pairs, 6 based on Foata normal form. 0/468 useless extension candidates. Maximal degree in co-relation 384. Up to 32 conditions per place. [2023-08-24 12:42:28,654 INFO L82 GeneralOperation]: Start removeDead. Operand has 181 places, 206 transitions, 456 flow [2023-08-24 12:42:28,655 INFO L88 GeneralOperation]: Finished RemoveDead, result has has 181 places, 206 transitions, 456 flow [2023-08-24 12:42:28,655 INFO L124 etLargeBlockEncoding]: Petri net LBE is using variable-based independence relation. [2023-08-24 12:42:28,656 INFO L131 etLargeBlockEncoding]: Starting large block encoding on Petri net that has 181 places, 206 transitions, 456 flow [2023-08-24 12:42:28,656 INFO L113 LiptonReduction]: Starting Lipton reduction on Petri net that has 181 places, 206 transitions, 456 flow [2023-08-24 12:42:28,656 INFO L73 FinitePrefix]: Start finitePrefix. Operand has 181 places, 206 transitions, 456 flow [2023-08-24 12:42:28,689 INFO L124 PetriNetUnfolderBase]: 82/555 cut-off events. [2023-08-24 12:42:28,689 INFO L125 PetriNetUnfolderBase]: For 48/48 co-relation queries the response was YES. [2023-08-24 12:42:28,692 INFO L83 FinitePrefix]: Finished finitePrefix Result has 610 conditions, 555 events. 82/555 cut-off events. For 48/48 co-relation queries the response was YES. Maximal size of possible extension queue 15. Compared 2020 event pairs, 6 based on Foata normal form. 0/468 useless extension candidates. Maximal degree in co-relation 384. Up to 32 conditions per place. [2023-08-24 12:42:28,702 INFO L119 LiptonReduction]: Number of co-enabled transitions 20496 [2023-08-24 12:42:33,240 INFO L134 LiptonReduction]: Checked pairs total: 62161 [2023-08-24 12:42:33,240 INFO L136 LiptonReduction]: Total number of compositions: 144 [2023-08-24 12:42:33,241 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == InUseError ======== [2023-08-24 12:42:33,242 INFO L357 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=false, mAutomataTypeConcurrency=PETRI_NET, 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=false, mMcrInterpolantMethod=WP, mPorIndependenceSettings=[Lde.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings;@1e6d47e7, mLbeIndependenceSettings=[IndependenceType=SYNTACTIC, AbstractionType=NONE, UseConditional=, UseSemiCommutativity=, Solver=, SolverTimeout=] [2023-08-24 12:42:33,242 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-08-24 12:42:33,248 INFO L185 PetriNetUnfolderBase]: Found word, exiting Unfolder. [2023-08-24 12:42:33,248 INFO L124 PetriNetUnfolderBase]: 33/136 cut-off events. [2023-08-24 12:42:33,248 INFO L125 PetriNetUnfolderBase]: For 23/23 co-relation queries the response was YES. [2023-08-24 12:42:33,248 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-24 12:42:33,248 INFO L208 CegarLoopForPetriNet]: trace histogram [5, 4, 4, 1, 1, 1, 1, 1, 1] [2023-08-24 12:42:33,248 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES === [ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES] === [2023-08-24 12:42:33,248 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-24 12:42:33,249 INFO L85 PathProgramCache]: Analyzing trace with hash -170163372, now seen corresponding path program 1 times [2023-08-24 12:42:33,249 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-24 12:42:33,249 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1363714400] [2023-08-24 12:42:33,249 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-24 12:42:33,249 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-24 12:42:33,271 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-08-24 12:42:33,272 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2023-08-24 12:42:33,284 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-08-24 12:42:33,301 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2023-08-24 12:42:33,301 INFO L360 BasicCegarLoop]: Counterexample is feasible [2023-08-24 12:42:33,301 INFO L805 garLoopResultBuilder]: Registering result UNSAFE for location ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (0 of 1 remaining) [2023-08-24 12:42:33,301 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable14 [2023-08-24 12:42:33,301 INFO L445 BasicCegarLoop]: Path program histogram: [1] [2023-08-24 12:42:33,303 INFO L307 ceAbstractionStarter]: Result for error location InUseError was UNSAFE (2/2) [2023-08-24 12:42:33,303 WARN L233 ceAbstractionStarter]: 4 thread instances were not sufficient, I will increase this number and restart the analysis [2023-08-24 12:42:33,303 INFO L515 ceAbstractionStarter]: Constructing petrified ICFG for 5 thread instances. [2023-08-24 12:42:33,320 INFO L144 ThreadInstanceAdder]: Constructed 5 joinOtherThreadTransitions. [2023-08-24 12:42:33,322 INFO L73 FinitePrefix]: Start finitePrefix. Operand has 206 places, 236 transitions, 532 flow [2023-08-24 12:42:33,416 INFO L124 PetriNetUnfolderBase]: 141/886 cut-off events. [2023-08-24 12:42:33,417 INFO L125 PetriNetUnfolderBase]: For 110/110 co-relation queries the response was YES. [2023-08-24 12:42:33,427 INFO L83 FinitePrefix]: Finished finitePrefix Result has 997 conditions, 886 events. 141/886 cut-off events. For 110/110 co-relation queries the response was YES. Maximal size of possible extension queue 18. Compared 3883 event pairs, 23 based on Foata normal form. 0/755 useless extension candidates. Maximal degree in co-relation 600. Up to 80 conditions per place. [2023-08-24 12:42:33,427 INFO L82 GeneralOperation]: Start removeDead. Operand has 206 places, 236 transitions, 532 flow [2023-08-24 12:42:33,431 INFO L88 GeneralOperation]: Finished RemoveDead, result has has 206 places, 236 transitions, 532 flow [2023-08-24 12:42:33,431 INFO L124 etLargeBlockEncoding]: Petri net LBE is using variable-based independence relation. [2023-08-24 12:42:33,431 INFO L131 etLargeBlockEncoding]: Starting large block encoding on Petri net that has 206 places, 236 transitions, 532 flow [2023-08-24 12:42:33,432 INFO L113 LiptonReduction]: Starting Lipton reduction on Petri net that has 206 places, 236 transitions, 532 flow [2023-08-24 12:42:33,432 INFO L73 FinitePrefix]: Start finitePrefix. Operand has 206 places, 236 transitions, 532 flow [2023-08-24 12:42:33,498 INFO L124 PetriNetUnfolderBase]: 141/886 cut-off events. [2023-08-24 12:42:33,498 INFO L125 PetriNetUnfolderBase]: For 110/110 co-relation queries the response was YES. [2023-08-24 12:42:33,506 INFO L83 FinitePrefix]: Finished finitePrefix Result has 997 conditions, 886 events. 141/886 cut-off events. For 110/110 co-relation queries the response was YES. Maximal size of possible extension queue 18. Compared 3883 event pairs, 23 based on Foata normal form. 0/755 useless extension candidates. Maximal degree in co-relation 600. Up to 80 conditions per place. [2023-08-24 12:42:33,530 INFO L119 LiptonReduction]: Number of co-enabled transitions 29960 [2023-08-24 12:42:37,033 INFO L134 LiptonReduction]: Checked pairs total: 84821 [2023-08-24 12:42:37,033 INFO L136 LiptonReduction]: Total number of compositions: 155 [2023-08-24 12:42:37,034 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-08-24 12:42:37,034 INFO L357 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=false, mAutomataTypeConcurrency=PETRI_NET, 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=false, mMcrInterpolantMethod=WP, mPorIndependenceSettings=[Lde.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings;@1e6d47e7, mLbeIndependenceSettings=[IndependenceType=SYNTACTIC, AbstractionType=NONE, UseConditional=, UseSemiCommutativity=, Solver=, SolverTimeout=] [2023-08-24 12:42:37,034 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-08-24 12:42:37,036 INFO L185 PetriNetUnfolderBase]: Found word, exiting Unfolder. [2023-08-24 12:42:37,036 INFO L124 PetriNetUnfolderBase]: 3/14 cut-off events. [2023-08-24 12:42:37,036 INFO L125 PetriNetUnfolderBase]: For 0/0 co-relation queries the response was YES. [2023-08-24 12:42:37,036 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-24 12:42:37,036 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1] [2023-08-24 12:42:37,036 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-08-24 12:42:37,037 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-24 12:42:37,037 INFO L85 PathProgramCache]: Analyzing trace with hash 72350388, now seen corresponding path program 1 times [2023-08-24 12:42:37,037 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-24 12:42:37,037 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1479144392] [2023-08-24 12:42:37,037 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-24 12:42:37,037 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-24 12:42:37,052 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-24 12:42:37,072 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-24 12:42:37,072 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-24 12:42:37,072 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1479144392] [2023-08-24 12:42:37,072 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1479144392] provided 1 perfect and 0 imperfect interpolant sequences [2023-08-24 12:42:37,072 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-08-24 12:42:37,072 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2023-08-24 12:42:37,073 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [927644254] [2023-08-24 12:42:37,073 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-08-24 12:42:37,073 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-08-24 12:42:37,073 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-24 12:42:37,073 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-08-24 12:42:37,074 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-08-24 12:42:37,074 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 168 out of 391 [2023-08-24 12:42:37,075 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 87 places, 114 transitions, 288 flow. Second operand has 3 states, 3 states have (on average 169.33333333333334) internal successors, (508), 3 states have internal predecessors, (508), 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) [2023-08-24 12:42:37,075 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-24 12:42:37,075 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 168 of 391 [2023-08-24 12:42:37,075 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand