./Ultimate.py --spec ../../../trunk/examples/svcomp/properties/unreach-call.prp --file ../../../trunk/examples/svcomp/pthread/queue_ok.i --full-output --witness-type correctness_witness --witnessparser.only.consider.loop.invariants false --cacsl2boogietranslator.check.unreachability.of.reach_error.function false --validate ./goblint.2024-05-21_14-57-05.files/mutex-meet/queue_ok.yml/witness.yml --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 76401ed0 Calling Ultimate with: /root/.sdkman/candidates/java/current/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReachWitnessValidation.xml -i ../../../trunk/examples/svcomp/pthread/queue_ok.i ./goblint.2024-05-21_14-57-05.files/mutex-meet/queue_ok.yml/witness.yml -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --traceabstraction.compute.hoare.annotation.of.negated.interpolant.automaton,.abstraction.and.cfg false --witnessparser.only.consider.loop.invariants false --cacsl2boogietranslator.check.unreachability.of.reach_error.function false --- Real Ultimate output --- This is Ultimate 0.2.4-tmp.fs.goblint-validation-76401ed-m [2024-06-20 17:44:44,730 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-06-20 17:44:44,800 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-06-20 17:44:44,803 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-06-20 17:44:44,803 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-06-20 17:44:44,819 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-06-20 17:44:44,820 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-06-20 17:44:44,820 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-06-20 17:44:44,821 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-06-20 17:44:44,821 INFO L153 SettingsManager]: * Use memory slicer=true [2024-06-20 17:44:44,821 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-06-20 17:44:44,821 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-06-20 17:44:44,822 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-06-20 17:44:44,822 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-06-20 17:44:44,823 INFO L153 SettingsManager]: * Use SBE=true [2024-06-20 17:44:44,823 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-06-20 17:44:44,824 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-06-20 17:44:44,829 INFO L153 SettingsManager]: * sizeof long=4 [2024-06-20 17:44:44,829 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-06-20 17:44:44,829 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-06-20 17:44:44,830 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-06-20 17:44:44,831 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-06-20 17:44:44,831 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-06-20 17:44:44,832 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-06-20 17:44:44,832 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-06-20 17:44:44,832 INFO L153 SettingsManager]: * sizeof long double=12 [2024-06-20 17:44:44,832 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-06-20 17:44:44,833 INFO L153 SettingsManager]: * Use constant arrays=true [2024-06-20 17:44:44,833 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-06-20 17:44:44,833 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-06-20 17:44:44,833 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-06-20 17:44:44,833 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-06-20 17:44:44,834 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-06-20 17:44:44,834 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-06-20 17:44:44,834 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-06-20 17:44:44,834 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-06-20 17:44:44,835 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-06-20 17:44:44,835 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-06-20 17:44:44,835 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-06-20 17:44:44,835 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-06-20 17:44:44,835 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2024-06-20 17:44:44,836 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-06-20 17:44:44,836 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-06-20 17:44:44,836 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC 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.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessparser: Only consider loop invariants -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Check unreachability of reach_error function -> false [2024-06-20 17:44:45,025 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-06-20 17:44:45,040 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-06-20 17:44:45,042 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-06-20 17:44:45,043 INFO L270 PluginConnector]: Initializing CDTParser... [2024-06-20 17:44:45,044 INFO L274 PluginConnector]: CDTParser initialized [2024-06-20 17:44:45,044 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/pthread/queue_ok.i [2024-06-20 17:44:46,107 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-06-20 17:44:46,291 INFO L384 CDTParser]: Found 1 translation units. [2024-06-20 17:44:46,291 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/pthread/queue_ok.i [2024-06-20 17:44:46,304 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/675595166/ea3d45a737534cc68876a89618ca6322/FLAGe34fffbda [2024-06-20 17:44:46,314 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/675595166/ea3d45a737534cc68876a89618ca6322 [2024-06-20 17:44:46,315 INFO L270 PluginConnector]: Initializing Witness Parser... [2024-06-20 17:44:46,316 INFO L274 PluginConnector]: Witness Parser initialized [2024-06-20 17:44:46,316 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/./goblint.2024-05-21_14-57-05.files/mutex-meet/queue_ok.yml/witness.yml [2024-06-20 17:44:46,408 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-06-20 17:44:46,410 INFO L133 ToolchainWalker]: Walking toolchain with 5 elements. [2024-06-20 17:44:46,411 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-06-20 17:44:46,411 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-06-20 17:44:46,414 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-06-20 17:44:46,415 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.06 05:44:46" (1/2) ... [2024-06-20 17:44:46,416 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@22e729c0 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.06 05:44:46, skipping insertion in model container [2024-06-20 17:44:46,416 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.06 05:44:46" (1/2) ... [2024-06-20 17:44:46,417 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.CACSL2BoogieTranslatorObserver@221cc6aa and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.06 05:44:46, skipping insertion in model container [2024-06-20 17:44:46,419 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "witness.yml de.uni_freiburg.informatik.ultimate.witnessparser CORRECTNESS_WITNESS 20.06 05:44:46" (2/2) ... [2024-06-20 17:44:46,420 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@22e729c0 and model type witness.yml de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator CORRECTNESS_WITNESS 20.06 05:44:46, skipping insertion in model container [2024-06-20 17:44:46,420 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "witness.yml de.uni_freiburg.informatik.ultimate.witnessparser CORRECTNESS_WITNESS 20.06 05:44:46" (2/2) ... [2024-06-20 17:44:46,420 INFO L83 nessWitnessExtractor]: Extracting all invariants from correctness witness [2024-06-20 17:44:46,458 INFO L95 edCorrectnessWitness]: Found the following entries in the witness: [2024-06-20 17:44:46,459 INFO L97 edCorrectnessWitness]: Location invariant before [L1053-L1053] ((! multithreaded || (m_locked || ((((-1LL + (long long )dequeue_flag) + (long long )enqueue_flag >= 0LL && (1LL - (long long )dequeue_flag) + (long long )enqueue_flag >= 0LL) && (1LL + (long long )dequeue_flag) - (long long )enqueue_flag >= 0LL) && (1LL - (long long )dequeue_flag) - (long long )enqueue_flag >= 0LL))) && (! multithreaded || 0 <= queue.head)) && (! multithreaded || (m_locked || (-2147483645 <= queue.tail && 0 <= queue.head))) [2024-06-20 17:44:46,459 INFO L97 edCorrectnessWitness]: Location invariant before [L1054-L1054] ((! multithreaded || (m_locked || ((((-1LL + (long long )dequeue_flag) + (long long )enqueue_flag >= 0LL && (1LL - (long long )dequeue_flag) + (long long )enqueue_flag >= 0LL) && (1LL + (long long )dequeue_flag) - (long long )enqueue_flag >= 0LL) && (1LL - (long long )dequeue_flag) - (long long )enqueue_flag >= 0LL))) && (! multithreaded || 0 <= queue.head)) && (! multithreaded || (m_locked || (-2147483645 <= queue.tail && 0 <= queue.head))) [2024-06-20 17:44:46,459 INFO L103 edCorrectnessWitness]: ghost_variable multithreaded = 0 [2024-06-20 17:44:46,459 INFO L103 edCorrectnessWitness]: ghost_variable m_locked = 0 [2024-06-20 17:44:46,460 INFO L106 edCorrectnessWitness]: ghost_update [L1039-L1039] m_locked = 0; [2024-06-20 17:44:46,460 INFO L106 edCorrectnessWitness]: ghost_update [L1008-L1008] m_locked = 1; [2024-06-20 17:44:46,460 INFO L106 edCorrectnessWitness]: ghost_update [L1026-L1026] m_locked = 1; [2024-06-20 17:44:46,461 INFO L106 edCorrectnessWitness]: ghost_update [L1052-L1052] multithreaded = 1; [2024-06-20 17:44:46,461 INFO L106 edCorrectnessWitness]: ghost_update [L1020-L1020] m_locked = 0; [2024-06-20 17:44:46,518 INFO L177 MainTranslator]: Built tables and reachable declarations [2024-06-20 17:44:46,931 INFO L207 PostProcessor]: Analyzing one entry point: main [2024-06-20 17:44:46,941 INFO L202 MainTranslator]: Completed pre-run Start Parsing Local Start Parsing Local Start Parsing Local Start Parsing Local Start Parsing Local Start Parsing Local Start Parsing Local Start Parsing Local Start Parsing Local [2024-06-20 17:44:47,077 INFO L207 PostProcessor]: Analyzing one entry point: main [2024-06-20 17:44:47,135 INFO L206 MainTranslator]: Completed translation [2024-06-20 17:44:47,135 INFO L201 PluginConnector]: Adding new model witness.yml de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator CORRECTNESS_WITNESS 20.06 05:44:47 WrapperNode [2024-06-20 17:44:47,135 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-06-20 17:44:47,136 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-06-20 17:44:47,136 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-06-20 17:44:47,137 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-06-20 17:44:47,142 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "witness.yml de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator CORRECTNESS_WITNESS 20.06 05:44:47" (1/1) ... [2024-06-20 17:44:47,161 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "witness.yml de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator CORRECTNESS_WITNESS 20.06 05:44:47" (1/1) ... [2024-06-20 17:44:47,203 INFO L138 Inliner]: procedures = 274, calls = 189, calls flagged for inlining = 9, calls inlined = 9, statements flattened = 758 [2024-06-20 17:44:47,204 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-06-20 17:44:47,205 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-06-20 17:44:47,205 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-06-20 17:44:47,205 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-06-20 17:44:47,214 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "witness.yml de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator CORRECTNESS_WITNESS 20.06 05:44:47" (1/1) ... [2024-06-20 17:44:47,215 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "witness.yml de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator CORRECTNESS_WITNESS 20.06 05:44:47" (1/1) ... [2024-06-20 17:44:47,222 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "witness.yml de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator CORRECTNESS_WITNESS 20.06 05:44:47" (1/1) ... [2024-06-20 17:44:47,288 INFO L175 MemorySlicer]: Split 172 memory accesses to 4 slices as follows [2, 162, 5, 3]. 94 percent of accesses are in the largest equivalence class. The 7 initializations are split as follows [2, 0, 5, 0]. The 13 writes are split as follows [0, 11, 0, 2]. [2024-06-20 17:44:47,288 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "witness.yml de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator CORRECTNESS_WITNESS 20.06 05:44:47" (1/1) ... [2024-06-20 17:44:47,288 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "witness.yml de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator CORRECTNESS_WITNESS 20.06 05:44:47" (1/1) ... [2024-06-20 17:44:47,305 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "witness.yml de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator CORRECTNESS_WITNESS 20.06 05:44:47" (1/1) ... [2024-06-20 17:44:47,310 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "witness.yml de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator CORRECTNESS_WITNESS 20.06 05:44:47" (1/1) ... [2024-06-20 17:44:47,313 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "witness.yml de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator CORRECTNESS_WITNESS 20.06 05:44:47" (1/1) ... [2024-06-20 17:44:47,315 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "witness.yml de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator CORRECTNESS_WITNESS 20.06 05:44:47" (1/1) ... [2024-06-20 17:44:47,319 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-06-20 17:44:47,320 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-06-20 17:44:47,320 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-06-20 17:44:47,320 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-06-20 17:44:47,345 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "witness.yml de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator CORRECTNESS_WITNESS 20.06 05:44:47" (1/1) ... [2024-06-20 17:44:47,356 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-06-20 17:44:47,362 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-06-20 17:44:47,380 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-06-20 17:44:47,398 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-06-20 17:44:47,409 INFO L130 BoogieDeclarations]: Found specification of procedure t1 [2024-06-20 17:44:47,409 INFO L138 BoogieDeclarations]: Found implementation of procedure t1 [2024-06-20 17:44:47,409 INFO L130 BoogieDeclarations]: Found specification of procedure t2 [2024-06-20 17:44:47,410 INFO L138 BoogieDeclarations]: Found implementation of procedure t2 [2024-06-20 17:44:47,410 INFO L130 BoogieDeclarations]: Found specification of procedure #PthreadsMutexUnlock [2024-06-20 17:44:47,410 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2024-06-20 17:44:47,410 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2024-06-20 17:44:47,410 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#2 [2024-06-20 17:44:47,410 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#3 [2024-06-20 17:44:47,410 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2024-06-20 17:44:47,410 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2024-06-20 17:44:47,411 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#2 [2024-06-20 17:44:47,411 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#3 [2024-06-20 17:44:47,411 INFO L130 BoogieDeclarations]: Found specification of procedure #PthreadsMutexLock [2024-06-20 17:44:47,411 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-06-20 17:44:47,411 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-06-20 17:44:47,411 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2024-06-20 17:44:47,411 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2024-06-20 17:44:47,411 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#3 [2024-06-20 17:44:47,412 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-06-20 17:44:47,412 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-06-20 17:44:47,413 WARN L214 CfgBuilder]: User set CodeBlockSize to SequenceOfStatements but program contains fork statements. Overwriting the user preferences and setting CodeBlockSize to OneNontrivialStatement [2024-06-20 17:44:47,549 INFO L244 CfgBuilder]: Building ICFG [2024-06-20 17:44:47,551 INFO L270 CfgBuilder]: Building CFG for each procedure with an implementation [2024-06-20 17:44:48,185 INFO L289 CfgBuilder]: Ommited future-live optimization because the input is a concurrent program. [2024-06-20 17:44:48,185 INFO L293 CfgBuilder]: Performing block encoding [2024-06-20 17:44:49,287 INFO L315 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-06-20 17:44:49,287 INFO L320 CfgBuilder]: Removed 2 assume(true) statements. [2024-06-20 17:44:49,289 INFO L201 PluginConnector]: Adding new model witness.yml de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.06 05:44:49 BoogieIcfgContainer [2024-06-20 17:44:49,289 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-06-20 17:44:49,291 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-06-20 17:44:49,292 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-06-20 17:44:49,294 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-06-20 17:44:49,294 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 20.06 05:44:46" (1/4) ... [2024-06-20 17:44:49,295 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@319a3fb and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.06 05:44:49, skipping insertion in model container [2024-06-20 17:44:49,296 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "witness.yml de.uni_freiburg.informatik.ultimate.witnessparser CORRECTNESS_WITNESS 20.06 05:44:46" (2/4) ... [2024-06-20 17:44:49,296 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@319a3fb and model type witness.yml de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CORRECTNESS_WITNESS 20.06 05:44:49, skipping insertion in model container [2024-06-20 17:44:49,296 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "witness.yml de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator CORRECTNESS_WITNESS 20.06 05:44:47" (3/4) ... [2024-06-20 17:44:49,296 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@319a3fb and model type witness.yml de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CORRECTNESS_WITNESS 20.06 05:44:49, skipping insertion in model container [2024-06-20 17:44:49,297 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "witness.yml de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.06 05:44:49" (4/4) ... [2024-06-20 17:44:49,298 INFO L112 eAbstractionObserver]: Analyzing ICFG queue_ok.i [2024-06-20 17:44:49,312 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-06-20 17:44:49,312 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 2 error locations. [2024-06-20 17:44:49,313 INFO L522 ceAbstractionStarter]: Constructing petrified ICFG for 1 thread instances. [2024-06-20 17:44:49,359 INFO L144 ThreadInstanceAdder]: Constructed 2 joinOtherThreadTransitions. [2024-06-20 17:44:49,390 INFO L73 FinitePrefix]: Start finitePrefix. Operand has 38 places, 35 transitions, 84 flow [2024-06-20 17:44:49,489 INFO L124 PetriNetUnfolderBase]: 4/33 cut-off events. [2024-06-20 17:44:49,489 INFO L125 PetriNetUnfolderBase]: For 2/2 co-relation queries the response was YES. [2024-06-20 17:44:49,492 INFO L83 FinitePrefix]: Finished finitePrefix Result has 42 conditions, 33 events. 4/33 cut-off events. For 2/2 co-relation queries the response was YES. Maximal size of possible extension queue 4. Compared 42 event pairs, 0 based on Foata normal form. 0/27 useless extension candidates. Maximal degree in co-relation 28. Up to 2 conditions per place. [2024-06-20 17:44:49,492 INFO L82 GeneralOperation]: Start removeDead. Operand has 38 places, 35 transitions, 84 flow [2024-06-20 17:44:49,495 INFO L88 GeneralOperation]: Finished RemoveDead, result has has 34 places, 31 transitions, 71 flow [2024-06-20 17:44:49,517 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-06-20 17:44:49,527 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=LoopHeads, 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;@7248f291, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-06-20 17:44:49,527 INFO L358 AbstractCegarLoop]: Starting to check reachability of 4 error locations. [2024-06-20 17:44:49,532 INFO L185 PetriNetUnfolderBase]: Found word, exiting Unfolder. [2024-06-20 17:44:49,548 INFO L124 PetriNetUnfolderBase]: 0/5 cut-off events. [2024-06-20 17:44:49,548 INFO L125 PetriNetUnfolderBase]: For 0/0 co-relation queries the response was YES. [2024-06-20 17:44:49,548 INFO L200 CegarLoopForPetriNet]: Found error trace [2024-06-20 17:44:49,549 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1, 1] [2024-06-20 17:44:49,549 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONWITNESS_INVARIANT === [ULTIMATE.startErr0ASSERT_VIOLATIONWITNESS_INVARIANT, ULTIMATE.startErr1ASSERT_VIOLATIONWITNESS_INVARIANT, ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (and 1 more)] === [2024-06-20 17:44:49,553 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-06-20 17:44:49,553 INFO L85 PathProgramCache]: Analyzing trace with hash 1586888836, now seen corresponding path program 1 times [2024-06-20 17:44:49,559 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-06-20 17:44:49,559 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1420466155] [2024-06-20 17:44:49,560 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-06-20 17:44:49,560 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-06-20 17:44:49,868 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-06-20 17:44:50,401 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-06-20 17:44:50,402 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-06-20 17:44:50,402 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1420466155] [2024-06-20 17:44:50,403 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1420466155] provided 1 perfect and 0 imperfect interpolant sequences [2024-06-20 17:44:50,403 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-06-20 17:44:50,403 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2024-06-20 17:44:50,404 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1887561460] [2024-06-20 17:44:50,405 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-06-20 17:44:50,411 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-06-20 17:44:50,415 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-06-20 17:44:50,437 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-06-20 17:44:50,438 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-06-20 17:44:50,444 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 6 out of 35 [2024-06-20 17:44:50,446 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 34 places, 31 transitions, 71 flow. Second operand has 3 states, 3 states have (on average 7.333333333333333) internal successors, (22), 3 states have internal predecessors, (22), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-06-20 17:44:50,446 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-06-20 17:44:50,446 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 6 of 35 [2024-06-20 17:44:50,447 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-06-20 17:44:50,793 INFO L124 PetriNetUnfolderBase]: 372/622 cut-off events. [2024-06-20 17:44:50,793 INFO L125 PetriNetUnfolderBase]: For 16/16 co-relation queries the response was YES. [2024-06-20 17:44:50,797 INFO L83 FinitePrefix]: Finished finitePrefix Result has 1246 conditions, 622 events. 372/622 cut-off events. For 16/16 co-relation queries the response was YES. Maximal size of possible extension queue 36. Compared 2427 event pairs, 126 based on Foata normal form. 12/520 useless extension candidates. Maximal degree in co-relation 1168. Up to 433 conditions per place. [2024-06-20 17:44:50,822 INFO L140 encePairwiseOnDemand]: 28/35 looper letters, 31 selfloop transitions, 3 changer transitions 4/42 dead transitions. [2024-06-20 17:44:50,823 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 36 places, 42 transitions, 172 flow [2024-06-20 17:44:50,824 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-06-20 17:44:50,825 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3 states. [2024-06-20 17:44:50,830 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 60 transitions. [2024-06-20 17:44:50,831 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.5714285714285714 [2024-06-20 17:44:50,832 INFO L175 Difference]: Start difference. First operand has 34 places, 31 transitions, 71 flow. Second operand 3 states and 60 transitions. [2024-06-20 17:44:50,833 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 36 places, 42 transitions, 172 flow [2024-06-20 17:44:50,835 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 33 places, 42 transitions, 166 flow, removed 0 selfloop flow, removed 3 redundant places. [2024-06-20 17:44:50,836 INFO L231 Difference]: Finished difference. Result has 34 places, 29 transitions, 80 flow [2024-06-20 17:44:50,837 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=35, PETRI_DIFFERENCE_MINUEND_FLOW=64, PETRI_DIFFERENCE_MINUEND_PLACES=31, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=30, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=1, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=27, PETRI_DIFFERENCE_SUBTRAHEND_STATES=3, PETRI_FLOW=80, PETRI_PLACES=34, PETRI_TRANSITIONS=29} [2024-06-20 17:44:50,840 INFO L281 CegarLoopForPetriNet]: 34 programPoint places, 0 predicate places. [2024-06-20 17:44:50,840 INFO L495 AbstractCegarLoop]: Abstraction has has 34 places, 29 transitions, 80 flow [2024-06-20 17:44:50,840 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 7.333333333333333) internal successors, (22), 3 states have internal predecessors, (22), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-06-20 17:44:50,840 INFO L200 CegarLoopForPetriNet]: Found error trace [2024-06-20 17:44:50,840 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-06-20 17:44:50,841 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-06-20 17:44:50,841 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONWITNESS_INVARIANT === [ULTIMATE.startErr0ASSERT_VIOLATIONWITNESS_INVARIANT, ULTIMATE.startErr1ASSERT_VIOLATIONWITNESS_INVARIANT, ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (and 1 more)] === [2024-06-20 17:44:50,841 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-06-20 17:44:50,841 INFO L85 PathProgramCache]: Analyzing trace with hash 2036169351, now seen corresponding path program 1 times [2024-06-20 17:44:50,841 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-06-20 17:44:50,842 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1776337220] [2024-06-20 17:44:50,842 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-06-20 17:44:50,842 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-06-20 17:44:50,882 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-06-20 17:44:50,906 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-06-20 17:44:50,907 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-06-20 17:44:50,907 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1776337220] [2024-06-20 17:44:50,907 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1776337220] provided 1 perfect and 0 imperfect interpolant sequences [2024-06-20 17:44:50,907 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-06-20 17:44:50,907 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-06-20 17:44:50,908 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [409202045] [2024-06-20 17:44:50,908 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-06-20 17:44:50,909 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-06-20 17:44:50,909 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-06-20 17:44:50,909 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-06-20 17:44:50,909 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-06-20 17:44:50,909 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 7 out of 35 [2024-06-20 17:44:50,910 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 34 places, 29 transitions, 80 flow. Second operand has 3 states, 3 states have (on average 9.666666666666666) internal successors, (29), 3 states have internal predecessors, (29), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-06-20 17:44:50,910 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-06-20 17:44:50,910 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 7 of 35 [2024-06-20 17:44:50,910 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-06-20 17:44:51,058 INFO L124 PetriNetUnfolderBase]: 231/411 cut-off events. [2024-06-20 17:44:51,059 INFO L125 PetriNetUnfolderBase]: For 44/44 co-relation queries the response was YES. [2024-06-20 17:44:51,059 INFO L83 FinitePrefix]: Finished finitePrefix Result has 939 conditions, 411 events. 231/411 cut-off events. For 44/44 co-relation queries the response was YES. Maximal size of possible extension queue 22. Compared 1426 event pairs, 166 based on Foata normal form. 0/365 useless extension candidates. Maximal degree in co-relation 612. Up to 358 conditions per place. [2024-06-20 17:44:51,061 INFO L140 encePairwiseOnDemand]: 32/35 looper letters, 31 selfloop transitions, 2 changer transitions 0/37 dead transitions. [2024-06-20 17:44:51,062 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 33 places, 37 transitions, 161 flow [2024-06-20 17:44:51,063 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-06-20 17:44:51,063 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3 states. [2024-06-20 17:44:51,064 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 55 transitions. [2024-06-20 17:44:51,064 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.5238095238095238 [2024-06-20 17:44:51,064 INFO L175 Difference]: Start difference. First operand has 34 places, 29 transitions, 80 flow. Second operand 3 states and 55 transitions. [2024-06-20 17:44:51,064 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 33 places, 37 transitions, 161 flow [2024-06-20 17:44:51,065 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 32 places, 37 transitions, 159 flow, removed 0 selfloop flow, removed 1 redundant places. [2024-06-20 17:44:51,066 INFO L231 Difference]: Finished difference. Result has 32 places, 28 transitions, 77 flow [2024-06-20 17:44:51,066 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=35, PETRI_DIFFERENCE_MINUEND_FLOW=73, PETRI_DIFFERENCE_MINUEND_PLACES=30, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=28, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=2, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=26, PETRI_DIFFERENCE_SUBTRAHEND_STATES=3, PETRI_FLOW=77, PETRI_PLACES=32, PETRI_TRANSITIONS=28} [2024-06-20 17:44:51,067 INFO L281 CegarLoopForPetriNet]: 34 programPoint places, -2 predicate places. [2024-06-20 17:44:51,067 INFO L495 AbstractCegarLoop]: Abstraction has has 32 places, 28 transitions, 77 flow [2024-06-20 17:44:51,067 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 9.666666666666666) internal successors, (29), 3 states have internal predecessors, (29), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-06-20 17:44:51,067 INFO L200 CegarLoopForPetriNet]: Found error trace [2024-06-20 17:44:51,067 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-06-20 17:44:51,068 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-06-20 17:44:51,068 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONWITNESS_INVARIANT === [ULTIMATE.startErr0ASSERT_VIOLATIONWITNESS_INVARIANT, ULTIMATE.startErr1ASSERT_VIOLATIONWITNESS_INVARIANT, ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (and 1 more)] === [2024-06-20 17:44:51,068 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-06-20 17:44:51,068 INFO L85 PathProgramCache]: Analyzing trace with hash 2036169382, now seen corresponding path program 1 times [2024-06-20 17:44:51,068 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-06-20 17:44:51,069 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1275305091] [2024-06-20 17:44:51,069 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-06-20 17:44:51,069 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-06-20 17:44:51,130 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-06-20 17:44:51,474 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-06-20 17:44:51,475 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-06-20 17:44:51,475 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1275305091] [2024-06-20 17:44:51,475 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1275305091] provided 1 perfect and 0 imperfect interpolant sequences [2024-06-20 17:44:51,475 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-06-20 17:44:51,475 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-06-20 17:44:51,476 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1990055102] [2024-06-20 17:44:51,476 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-06-20 17:44:51,476 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-06-20 17:44:51,476 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-06-20 17:44:51,477 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-06-20 17:44:51,477 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2024-06-20 17:44:51,477 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 7 out of 35 [2024-06-20 17:44:51,477 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 32 places, 28 transitions, 77 flow. Second operand has 5 states, 5 states have (on average 8.6) internal successors, (43), 5 states have internal predecessors, (43), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-06-20 17:44:51,478 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-06-20 17:44:51,478 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 7 of 35 [2024-06-20 17:44:51,478 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-06-20 17:44:51,689 INFO L124 PetriNetUnfolderBase]: 321/555 cut-off events. [2024-06-20 17:44:51,690 INFO L125 PetriNetUnfolderBase]: For 73/75 co-relation queries the response was YES. [2024-06-20 17:44:51,691 INFO L83 FinitePrefix]: Finished finitePrefix Result has 1297 conditions, 555 events. 321/555 cut-off events. For 73/75 co-relation queries the response was YES. Maximal size of possible extension queue 33. Compared 2168 event pairs, 42 based on Foata normal form. 18/511 useless extension candidates. Maximal degree in co-relation 994. Up to 329 conditions per place. [2024-06-20 17:44:51,693 INFO L140 encePairwiseOnDemand]: 26/35 looper letters, 50 selfloop transitions, 10 changer transitions 0/64 dead transitions. [2024-06-20 17:44:51,693 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 36 places, 64 transitions, 287 flow [2024-06-20 17:44:51,693 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-06-20 17:44:51,694 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 5 states. [2024-06-20 17:44:51,694 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 97 transitions. [2024-06-20 17:44:51,695 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.5542857142857143 [2024-06-20 17:44:51,695 INFO L175 Difference]: Start difference. First operand has 32 places, 28 transitions, 77 flow. Second operand 5 states and 97 transitions. [2024-06-20 17:44:51,695 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 36 places, 64 transitions, 287 flow [2024-06-20 17:44:51,696 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 34 places, 64 transitions, 276 flow, removed 2 selfloop flow, removed 2 redundant places. [2024-06-20 17:44:51,697 INFO L231 Difference]: Finished difference. Result has 36 places, 36 transitions, 135 flow [2024-06-20 17:44:51,697 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=35, PETRI_DIFFERENCE_MINUEND_FLOW=71, PETRI_DIFFERENCE_MINUEND_PLACES=30, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=28, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=3, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=20, PETRI_DIFFERENCE_SUBTRAHEND_STATES=5, PETRI_FLOW=135, PETRI_PLACES=36, PETRI_TRANSITIONS=36} [2024-06-20 17:44:51,698 INFO L281 CegarLoopForPetriNet]: 34 programPoint places, 2 predicate places. [2024-06-20 17:44:51,698 INFO L495 AbstractCegarLoop]: Abstraction has has 36 places, 36 transitions, 135 flow [2024-06-20 17:44:51,698 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 8.6) internal successors, (43), 5 states have internal predecessors, (43), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-06-20 17:44:51,698 INFO L200 CegarLoopForPetriNet]: Found error trace [2024-06-20 17:44:51,698 INFO L208 CegarLoopForPetriNet]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-06-20 17:44:51,698 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2024-06-20 17:44:51,699 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONWITNESS_INVARIANT === [ULTIMATE.startErr0ASSERT_VIOLATIONWITNESS_INVARIANT, ULTIMATE.startErr1ASSERT_VIOLATIONWITNESS_INVARIANT, ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (and 1 more)] === [2024-06-20 17:44:51,699 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-06-20 17:44:51,699 INFO L85 PathProgramCache]: Analyzing trace with hash -1303256197, now seen corresponding path program 2 times [2024-06-20 17:44:51,699 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-06-20 17:44:51,699 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1723772126] [2024-06-20 17:44:51,700 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-06-20 17:44:51,700 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-06-20 17:44:51,767 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-06-20 17:44:52,140 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-06-20 17:44:52,140 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-06-20 17:44:52,140 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1723772126] [2024-06-20 17:44:52,141 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1723772126] provided 0 perfect and 1 imperfect interpolant sequences [2024-06-20 17:44:52,141 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [148986952] [2024-06-20 17:44:52,141 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-06-20 17:44:52,141 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-06-20 17:44:52,141 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-06-20 17:44:52,145 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) [2024-06-20 17:44:52,151 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-06-20 17:44:52,374 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-06-20 17:44:52,374 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-06-20 17:44:52,378 INFO L262 TraceCheckSpWp]: Trace formula consists of 426 conjuncts, 17 conjunts are in the unsatisfiable core [2024-06-20 17:44:52,384 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-06-20 17:44:52,420 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 21 [2024-06-20 17:44:52,501 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 222 treesize of output 198 [2024-06-20 17:44:52,574 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 141 treesize of output 131 [2024-06-20 17:44:52,590 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2024-06-20 17:44:52,618 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-06-20 17:44:52,619 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-06-20 17:44:52,712 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2024-06-20 17:45:17,696 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-06-20 17:45:17,697 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [148986952] provided 0 perfect and 2 imperfect interpolant sequences [2024-06-20 17:45:17,697 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-06-20 17:45:17,697 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4, 5] total 13 [2024-06-20 17:45:17,698 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [383486408] [2024-06-20 17:45:17,698 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-06-20 17:45:17,699 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-06-20 17:45:17,699 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-06-20 17:45:17,700 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-06-20 17:45:17,701 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=58, Invalid=147, Unknown=5, NotChecked=0, Total=210 [2024-06-20 17:45:17,701 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 7 out of 35 [2024-06-20 17:45:17,702 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 36 places, 36 transitions, 135 flow. Second operand has 15 states, 15 states have (on average 8.8) internal successors, (132), 15 states have internal predecessors, (132), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-06-20 17:45:17,702 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-06-20 17:45:17,702 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 7 of 35 [2024-06-20 17:45:17,702 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-06-20 17:45:22,394 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2024-06-20 17:45:26,412 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2024-06-20 17:45:30,536 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.02s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2024-06-20 17:45:34,590 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2024-06-20 17:45:38,647 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2024-06-20 17:45:42,664 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2024-06-20 17:45:46,777 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.02s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2024-06-20 17:45:50,799 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.02s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2024-06-20 17:45:54,808 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2024-06-20 17:45:58,852 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.04s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2024-06-20 17:46:02,873 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.02s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2024-06-20 17:46:06,883 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2024-06-20 17:46:10,896 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2024-06-20 17:46:14,921 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.02s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2024-06-20 17:46:18,948 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.03s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2024-06-20 17:46:22,957 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2024-06-20 17:46:26,980 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.02s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2024-06-20 17:46:31,011 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2024-06-20 17:46:35,017 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2024-06-20 17:46:39,036 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.02s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2024-06-20 17:46:43,633 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2024-06-20 17:46:47,651 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2024-06-20 17:46:51,713 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2024-06-20 17:46:55,778 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2024-06-20 17:46:56,036 INFO L124 PetriNetUnfolderBase]: 723/1185 cut-off events. [2024-06-20 17:46:56,038 INFO L125 PetriNetUnfolderBase]: For 420/438 co-relation queries the response was YES. [2024-06-20 17:46:56,040 INFO L83 FinitePrefix]: Finished finitePrefix Result has 3319 conditions, 1185 events. 723/1185 cut-off events. For 420/438 co-relation queries the response was YES. Maximal size of possible extension queue 75. Compared 5320 event pairs, 49 based on Foata normal form. 78/1261 useless extension candidates. Maximal degree in co-relation 2756. Up to 373 conditions per place. [2024-06-20 17:46:56,044 INFO L140 encePairwiseOnDemand]: 26/35 looper letters, 121 selfloop transitions, 37 changer transitions 0/162 dead transitions. [2024-06-20 17:46:56,044 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 49 places, 162 transitions, 856 flow [2024-06-20 17:46:56,045 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-06-20 17:46:56,045 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 14 states. [2024-06-20 17:46:56,046 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 14 states to 14 states and 266 transitions. [2024-06-20 17:46:56,046 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.5428571428571428 [2024-06-20 17:46:56,046 INFO L175 Difference]: Start difference. First operand has 36 places, 36 transitions, 135 flow. Second operand 14 states and 266 transitions. [2024-06-20 17:46:56,046 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 49 places, 162 transitions, 856 flow [2024-06-20 17:46:56,048 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 49 places, 162 transitions, 856 flow, removed 0 selfloop flow, removed 0 redundant places. [2024-06-20 17:46:56,050 INFO L231 Difference]: Finished difference. Result has 57 places, 65 transitions, 425 flow [2024-06-20 17:46:56,050 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=35, PETRI_DIFFERENCE_MINUEND_FLOW=135, PETRI_DIFFERENCE_MINUEND_PLACES=36, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=36, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=13, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=21, PETRI_DIFFERENCE_SUBTRAHEND_STATES=14, PETRI_FLOW=425, PETRI_PLACES=57, PETRI_TRANSITIONS=65} [2024-06-20 17:46:56,050 INFO L281 CegarLoopForPetriNet]: 34 programPoint places, 23 predicate places. [2024-06-20 17:46:56,051 INFO L495 AbstractCegarLoop]: Abstraction has has 57 places, 65 transitions, 425 flow [2024-06-20 17:46:56,051 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 8.8) internal successors, (132), 15 states have internal predecessors, (132), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-06-20 17:46:56,051 INFO L200 CegarLoopForPetriNet]: Found error trace [2024-06-20 17:46:56,051 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-06-20 17:46:56,065 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2024-06-20 17:46:56,264 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-06-20 17:46:56,264 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONWITNESS_INVARIANT === [ULTIMATE.startErr0ASSERT_VIOLATIONWITNESS_INVARIANT, ULTIMATE.startErr1ASSERT_VIOLATIONWITNESS_INVARIANT, ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (and 1 more)] === [2024-06-20 17:46:56,265 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-06-20 17:46:56,265 INFO L85 PathProgramCache]: Analyzing trace with hash -1746235065, now seen corresponding path program 1 times [2024-06-20 17:46:56,265 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-06-20 17:46:56,265 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [337065500] [2024-06-20 17:46:56,265 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-06-20 17:46:56,265 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-06-20 17:46:56,302 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-06-20 17:46:56,341 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-06-20 17:46:56,341 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-06-20 17:46:56,341 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [337065500] [2024-06-20 17:46:56,341 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [337065500] provided 0 perfect and 1 imperfect interpolant sequences [2024-06-20 17:46:56,341 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1938242529] [2024-06-20 17:46:56,341 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-06-20 17:46:56,342 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-06-20 17:46:56,342 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-06-20 17:46:56,343 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) [2024-06-20 17:46:56,347 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-06-20 17:46:56,532 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-06-20 17:46:56,533 INFO L262 TraceCheckSpWp]: Trace formula consists of 415 conjuncts, 3 conjunts are in the unsatisfiable core [2024-06-20 17:46:56,534 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-06-20 17:46:56,548 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-06-20 17:46:56,548 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-06-20 17:46:56,570 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-06-20 17:46:56,570 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1938242529] provided 0 perfect and 2 imperfect interpolant sequences [2024-06-20 17:46:56,570 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-06-20 17:46:56,570 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4, 4] total 7 [2024-06-20 17:46:56,570 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1435120325] [2024-06-20 17:46:56,570 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-06-20 17:46:56,571 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-06-20 17:46:56,571 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-06-20 17:46:56,571 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-06-20 17:46:56,571 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=21, Unknown=0, NotChecked=0, Total=42 [2024-06-20 17:46:56,572 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 7 out of 35 [2024-06-20 17:46:56,572 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 57 places, 65 transitions, 425 flow. Second operand has 7 states, 7 states have (on average 9.142857142857142) internal successors, (64), 7 states have internal predecessors, (64), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-06-20 17:46:56,572 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-06-20 17:46:56,572 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 7 of 35 [2024-06-20 17:46:56,572 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-06-20 17:46:56,935 INFO L124 PetriNetUnfolderBase]: 469/791 cut-off events. [2024-06-20 17:46:56,935 INFO L125 PetriNetUnfolderBase]: For 2164/2170 co-relation queries the response was YES. [2024-06-20 17:46:56,939 INFO L83 FinitePrefix]: Finished finitePrefix Result has 3067 conditions, 791 events. 469/791 cut-off events. For 2164/2170 co-relation queries the response was YES. Maximal size of possible extension queue 43. Compared 3211 event pairs, 186 based on Foata normal form. 90/878 useless extension candidates. Maximal degree in co-relation 2334. Up to 519 conditions per place. [2024-06-20 17:46:56,942 INFO L140 encePairwiseOnDemand]: 32/35 looper letters, 86 selfloop transitions, 13 changer transitions 0/103 dead transitions. [2024-06-20 17:46:56,942 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 61 places, 103 transitions, 779 flow [2024-06-20 17:46:56,943 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-06-20 17:46:56,943 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 6 states. [2024-06-20 17:46:56,945 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 120 transitions. [2024-06-20 17:46:56,946 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.5714285714285714 [2024-06-20 17:46:56,946 INFO L175 Difference]: Start difference. First operand has 57 places, 65 transitions, 425 flow. Second operand 6 states and 120 transitions. [2024-06-20 17:46:56,946 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 61 places, 103 transitions, 779 flow [2024-06-20 17:46:56,955 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 56 places, 103 transitions, 690 flow, removed 31 selfloop flow, removed 5 redundant places. [2024-06-20 17:46:56,957 INFO L231 Difference]: Finished difference. Result has 59 places, 58 transitions, 352 flow [2024-06-20 17:46:56,957 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=35, PETRI_DIFFERENCE_MINUEND_FLOW=277, PETRI_DIFFERENCE_MINUEND_PLACES=51, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=55, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=11, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=44, PETRI_DIFFERENCE_SUBTRAHEND_STATES=6, PETRI_FLOW=352, PETRI_PLACES=59, PETRI_TRANSITIONS=58} [2024-06-20 17:46:56,959 INFO L281 CegarLoopForPetriNet]: 34 programPoint places, 25 predicate places. [2024-06-20 17:46:56,959 INFO L495 AbstractCegarLoop]: Abstraction has has 59 places, 58 transitions, 352 flow [2024-06-20 17:46:56,960 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 9.142857142857142) internal successors, (64), 7 states have internal predecessors, (64), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-06-20 17:46:56,960 INFO L200 CegarLoopForPetriNet]: Found error trace [2024-06-20 17:46:56,960 INFO L208 CegarLoopForPetriNet]: trace histogram [5, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-06-20 17:46:56,972 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2024-06-20 17:46:57,171 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-06-20 17:46:57,172 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONWITNESS_INVARIANT === [ULTIMATE.startErr0ASSERT_VIOLATIONWITNESS_INVARIANT, ULTIMATE.startErr1ASSERT_VIOLATIONWITNESS_INVARIANT, ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (and 1 more)] === [2024-06-20 17:46:57,172 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-06-20 17:46:57,173 INFO L85 PathProgramCache]: Analyzing trace with hash 1201375206, now seen corresponding path program 3 times [2024-06-20 17:46:57,173 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-06-20 17:46:57,173 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [267832703] [2024-06-20 17:46:57,173 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-06-20 17:46:57,173 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-06-20 17:46:57,275 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-06-20 17:46:58,378 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-06-20 17:46:58,378 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-06-20 17:46:58,378 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [267832703] [2024-06-20 17:46:58,378 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [267832703] provided 0 perfect and 1 imperfect interpolant sequences [2024-06-20 17:46:58,378 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1700349982] [2024-06-20 17:46:58,378 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-06-20 17:46:58,378 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-06-20 17:46:58,379 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-06-20 17:46:58,392 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) [2024-06-20 17:46:58,406 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-06-20 17:46:58,804 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2024-06-20 17:46:58,804 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-06-20 17:46:58,807 INFO L262 TraceCheckSpWp]: Trace formula consists of 498 conjuncts, 41 conjunts are in the unsatisfiable core [2024-06-20 17:46:58,813 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-06-20 17:46:58,824 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 15 [2024-06-20 17:46:58,951 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 153 treesize of output 133 [2024-06-20 17:46:58,963 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 61 treesize of output 47 [2024-06-20 17:46:59,025 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 113 treesize of output 103 [2024-06-20 17:46:59,094 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 120 treesize of output 108 [2024-06-20 17:46:59,113 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2024-06-20 17:46:59,165 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 159 treesize of output 137 [2024-06-20 17:46:59,187 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 103 treesize of output 79 [2024-06-20 17:46:59,198 WARN L214 Elim1Store]: Array PQE input equivalent to false [2024-06-20 17:46:59,257 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 119 treesize of output 107 [2024-06-20 17:46:59,272 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2024-06-20 17:46:59,289 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2024-06-20 17:46:59,338 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-06-20 17:46:59,338 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-06-20 17:46:59,582 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 9 treesize of output 5 [2024-06-20 17:47:08,737 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-06-20 17:47:08,738 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 469 treesize of output 297 [2024-06-20 17:47:09,347 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-06-20 17:47:09,347 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 333 treesize of output 201 [2024-06-20 17:47:15,059 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-06-20 17:47:15,059 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1700349982] provided 0 perfect and 2 imperfect interpolant sequences [2024-06-20 17:47:15,059 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-06-20 17:47:15,059 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 21 [2024-06-20 17:47:15,060 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1709527641] [2024-06-20 17:47:15,060 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-06-20 17:47:15,061 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2024-06-20 17:47:15,062 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-06-20 17:47:15,062 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-06-20 17:47:15,062 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=150, Invalid=354, Unknown=2, NotChecked=0, Total=506 [2024-06-20 17:47:15,064 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 7 out of 35 [2024-06-20 17:47:15,064 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 59 places, 58 transitions, 352 flow. Second operand has 23 states, 23 states have (on average 8.565217391304348) internal successors, (197), 23 states have internal predecessors, (197), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-06-20 17:47:15,064 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-06-20 17:47:15,065 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 7 of 35 [2024-06-20 17:47:15,065 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-06-20 17:47:23,220 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2024-06-20 17:47:30,946 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2024-06-20 17:47:34,952 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2024-06-20 17:47:38,959 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2024-06-20 17:47:42,999 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2024-06-20 17:47:43,714 INFO L124 PetriNetUnfolderBase]: 1246/1986 cut-off events. [2024-06-20 17:47:43,714 INFO L125 PetriNetUnfolderBase]: For 8229/8243 co-relation queries the response was YES. [2024-06-20 17:47:43,719 INFO L83 FinitePrefix]: Finished finitePrefix Result has 7938 conditions, 1986 events. 1246/1986 cut-off events. For 8229/8243 co-relation queries the response was YES. Maximal size of possible extension queue 106. Compared 9091 event pairs, 49 based on Foata normal form. 138/2124 useless extension candidates. Maximal degree in co-relation 6870. Up to 635 conditions per place. [2024-06-20 17:47:43,726 INFO L140 encePairwiseOnDemand]: 26/35 looper letters, 190 selfloop transitions, 94 changer transitions 0/288 dead transitions. [2024-06-20 17:47:43,726 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 79 places, 288 transitions, 1991 flow [2024-06-20 17:47:43,726 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2024-06-20 17:47:43,726 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 21 states. [2024-06-20 17:47:43,728 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 416 transitions. [2024-06-20 17:47:43,728 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.5659863945578232 [2024-06-20 17:47:43,728 INFO L175 Difference]: Start difference. First operand has 59 places, 58 transitions, 352 flow. Second operand 21 states and 416 transitions. [2024-06-20 17:47:43,729 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 79 places, 288 transitions, 1991 flow [2024-06-20 17:47:43,739 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 78 places, 288 transitions, 1981 flow, removed 3 selfloop flow, removed 1 redundant places. [2024-06-20 17:47:43,742 INFO L231 Difference]: Finished difference. Result has 91 places, 125 transitions, 1203 flow [2024-06-20 17:47:43,742 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=35, PETRI_DIFFERENCE_MINUEND_FLOW=345, PETRI_DIFFERENCE_MINUEND_PLACES=58, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=58, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=32, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=22, PETRI_DIFFERENCE_SUBTRAHEND_STATES=21, PETRI_FLOW=1203, PETRI_PLACES=91, PETRI_TRANSITIONS=125} [2024-06-20 17:47:43,745 INFO L281 CegarLoopForPetriNet]: 34 programPoint places, 57 predicate places. [2024-06-20 17:47:43,745 INFO L495 AbstractCegarLoop]: Abstraction has has 91 places, 125 transitions, 1203 flow [2024-06-20 17:47:43,746 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 8.565217391304348) internal successors, (197), 23 states have internal predecessors, (197), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-06-20 17:47:43,746 INFO L200 CegarLoopForPetriNet]: Found error trace [2024-06-20 17:47:43,746 INFO L208 CegarLoopForPetriNet]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-06-20 17:47:43,761 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2024-06-20 17:47:43,959 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-06-20 17:47:43,959 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONWITNESS_INVARIANT === [ULTIMATE.startErr0ASSERT_VIOLATIONWITNESS_INVARIANT, ULTIMATE.startErr1ASSERT_VIOLATIONWITNESS_INVARIANT, ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (and 1 more)] === [2024-06-20 17:47:43,959 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-06-20 17:47:43,959 INFO L85 PathProgramCache]: Analyzing trace with hash -1412072900, now seen corresponding path program 2 times [2024-06-20 17:47:43,959 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-06-20 17:47:43,959 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1607420069] [2024-06-20 17:47:43,959 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-06-20 17:47:43,960 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-06-20 17:47:44,005 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-06-20 17:47:44,100 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-06-20 17:47:44,100 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-06-20 17:47:44,100 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1607420069] [2024-06-20 17:47:44,100 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1607420069] provided 0 perfect and 1 imperfect interpolant sequences [2024-06-20 17:47:44,100 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1073506017] [2024-06-20 17:47:44,100 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-06-20 17:47:44,100 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-06-20 17:47:44,101 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-06-20 17:47:44,108 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) [2024-06-20 17:47:44,109 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-06-20 17:47:44,335 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-06-20 17:47:44,335 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-06-20 17:47:44,338 INFO L262 TraceCheckSpWp]: Trace formula consists of 487 conjuncts, 6 conjunts are in the unsatisfiable core [2024-06-20 17:47:44,339 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-06-20 17:47:44,362 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-06-20 17:47:44,363 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-06-20 17:47:44,455 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-06-20 17:47:44,456 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1073506017] provided 0 perfect and 2 imperfect interpolant sequences [2024-06-20 17:47:44,456 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-06-20 17:47:44,456 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 13 [2024-06-20 17:47:44,456 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [803551822] [2024-06-20 17:47:44,456 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-06-20 17:47:44,456 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2024-06-20 17:47:44,456 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-06-20 17:47:44,457 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2024-06-20 17:47:44,457 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=78, Invalid=78, Unknown=0, NotChecked=0, Total=156 [2024-06-20 17:47:44,457 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 7 out of 35 [2024-06-20 17:47:44,457 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 91 places, 125 transitions, 1203 flow. Second operand has 13 states, 13 states have (on average 8.615384615384615) internal successors, (112), 13 states have internal predecessors, (112), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-06-20 17:47:44,457 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-06-20 17:47:44,457 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 7 of 35 [2024-06-20 17:47:44,457 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-06-20 17:47:45,340 INFO L124 PetriNetUnfolderBase]: 977/1603 cut-off events. [2024-06-20 17:47:45,340 INFO L125 PetriNetUnfolderBase]: For 20725/20743 co-relation queries the response was YES. [2024-06-20 17:47:45,344 INFO L83 FinitePrefix]: Finished finitePrefix Result has 9153 conditions, 1603 events. 977/1603 cut-off events. For 20725/20743 co-relation queries the response was YES. Maximal size of possible extension queue 63. Compared 7044 event pairs, 193 based on Foata normal form. 280/1880 useless extension candidates. Maximal degree in co-relation 6559. Up to 613 conditions per place. [2024-06-20 17:47:45,352 INFO L140 encePairwiseOnDemand]: 32/35 looper letters, 207 selfloop transitions, 57 changer transitions 0/268 dead transitions. [2024-06-20 17:47:45,352 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 102 places, 268 transitions, 2926 flow [2024-06-20 17:47:45,353 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-06-20 17:47:45,353 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 12 states. [2024-06-20 17:47:45,354 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 12 states to 12 states and 249 transitions. [2024-06-20 17:47:45,355 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.5928571428571429 [2024-06-20 17:47:45,355 INFO L175 Difference]: Start difference. First operand has 91 places, 125 transitions, 1203 flow. Second operand 12 states and 249 transitions. [2024-06-20 17:47:45,355 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 102 places, 268 transitions, 2926 flow [2024-06-20 17:47:45,384 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 95 places, 268 transitions, 2552 flow, removed 172 selfloop flow, removed 7 redundant places. [2024-06-20 17:47:45,388 INFO L231 Difference]: Finished difference. Result has 101 places, 128 transitions, 1238 flow [2024-06-20 17:47:45,388 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=35, PETRI_DIFFERENCE_MINUEND_FLOW=820, PETRI_DIFFERENCE_MINUEND_PLACES=84, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=106, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=37, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=69, PETRI_DIFFERENCE_SUBTRAHEND_STATES=12, PETRI_FLOW=1238, PETRI_PLACES=101, PETRI_TRANSITIONS=128} [2024-06-20 17:47:45,389 INFO L281 CegarLoopForPetriNet]: 34 programPoint places, 67 predicate places. [2024-06-20 17:47:45,389 INFO L495 AbstractCegarLoop]: Abstraction has has 101 places, 128 transitions, 1238 flow [2024-06-20 17:47:45,389 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 8.615384615384615) internal successors, (112), 13 states have internal predecessors, (112), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-06-20 17:47:45,389 INFO L200 CegarLoopForPetriNet]: Found error trace [2024-06-20 17:47:45,389 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-06-20 17:47:45,417 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2024-06-20 17:47:45,601 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-06-20 17:47:45,602 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr1ASSERT_VIOLATIONWITNESS_INVARIANT === [ULTIMATE.startErr0ASSERT_VIOLATIONWITNESS_INVARIANT, ULTIMATE.startErr1ASSERT_VIOLATIONWITNESS_INVARIANT, ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (and 1 more)] === [2024-06-20 17:47:45,602 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-06-20 17:47:45,602 INFO L85 PathProgramCache]: Analyzing trace with hash 1247827382, now seen corresponding path program 1 times [2024-06-20 17:47:45,602 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-06-20 17:47:45,603 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2140452591] [2024-06-20 17:47:45,603 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-06-20 17:47:45,603 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-06-20 17:47:45,642 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-06-20 17:47:45,693 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-06-20 17:47:45,693 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-06-20 17:47:45,693 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2140452591] [2024-06-20 17:47:45,693 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2140452591] provided 1 perfect and 0 imperfect interpolant sequences [2024-06-20 17:47:45,693 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-06-20 17:47:45,693 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-06-20 17:47:45,694 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [988775602] [2024-06-20 17:47:45,694 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-06-20 17:47:45,694 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-06-20 17:47:45,694 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-06-20 17:47:45,695 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-06-20 17:47:45,695 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-06-20 17:47:45,695 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 7 out of 35 [2024-06-20 17:47:45,696 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 101 places, 128 transitions, 1238 flow. Second operand has 3 states, 3 states have (on average 12.0) internal successors, (36), 3 states have internal predecessors, (36), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-06-20 17:47:45,696 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-06-20 17:47:45,696 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 7 of 35 [2024-06-20 17:47:45,696 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-06-20 17:47:45,872 INFO L124 PetriNetUnfolderBase]: 310/606 cut-off events. [2024-06-20 17:47:45,872 INFO L125 PetriNetUnfolderBase]: For 5834/5834 co-relation queries the response was YES. [2024-06-20 17:47:45,874 INFO L83 FinitePrefix]: Finished finitePrefix Result has 2877 conditions, 606 events. 310/606 cut-off events. For 5834/5834 co-relation queries the response was YES. Maximal size of possible extension queue 17. Compared 2196 event pairs, 57 based on Foata normal form. 34/638 useless extension candidates. Maximal degree in co-relation 2840. Up to 443 conditions per place. [2024-06-20 17:47:45,876 INFO L140 encePairwiseOnDemand]: 31/35 looper letters, 41 selfloop transitions, 7 changer transitions 0/52 dead transitions. [2024-06-20 17:47:45,877 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 91 places, 52 transitions, 508 flow [2024-06-20 17:47:45,877 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-06-20 17:47:45,878 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3 states. [2024-06-20 17:47:45,878 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 57 transitions. [2024-06-20 17:47:45,878 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.5428571428571428 [2024-06-20 17:47:45,878 INFO L175 Difference]: Start difference. First operand has 101 places, 128 transitions, 1238 flow. Second operand 3 states and 57 transitions. [2024-06-20 17:47:45,878 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 91 places, 52 transitions, 508 flow [2024-06-20 17:47:45,883 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 66 places, 52 transitions, 410 flow, removed 33 selfloop flow, removed 25 redundant places. [2024-06-20 17:47:45,884 INFO L231 Difference]: Finished difference. Result has 66 places, 41 transitions, 260 flow [2024-06-20 17:47:45,884 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=35, PETRI_DIFFERENCE_MINUEND_FLOW=246, PETRI_DIFFERENCE_MINUEND_PLACES=64, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=41, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=7, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=34, PETRI_DIFFERENCE_SUBTRAHEND_STATES=3, PETRI_FLOW=260, PETRI_PLACES=66, PETRI_TRANSITIONS=41} [2024-06-20 17:47:45,885 INFO L281 CegarLoopForPetriNet]: 34 programPoint places, 32 predicate places. [2024-06-20 17:47:45,885 INFO L495 AbstractCegarLoop]: Abstraction has has 66 places, 41 transitions, 260 flow [2024-06-20 17:47:45,885 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 12.0) internal successors, (36), 3 states have internal predecessors, (36), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-06-20 17:47:45,885 INFO L200 CegarLoopForPetriNet]: Found error trace [2024-06-20 17:47:45,885 INFO L208 CegarLoopForPetriNet]: trace histogram [11, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-06-20 17:47:45,885 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7 [2024-06-20 17:47:45,885 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONWITNESS_INVARIANT === [ULTIMATE.startErr0ASSERT_VIOLATIONWITNESS_INVARIANT, ULTIMATE.startErr1ASSERT_VIOLATIONWITNESS_INVARIANT, ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (and 1 more)] === [2024-06-20 17:47:45,886 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-06-20 17:47:45,886 INFO L85 PathProgramCache]: Analyzing trace with hash 1630105542, now seen corresponding path program 4 times [2024-06-20 17:47:45,886 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-06-20 17:47:45,886 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1737153806] [2024-06-20 17:47:45,886 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-06-20 17:47:45,886 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-06-20 17:47:46,122 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-06-20 17:47:48,975 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 0 proven. 55 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-06-20 17:47:48,975 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-06-20 17:47:48,975 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1737153806] [2024-06-20 17:47:48,975 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1737153806] provided 0 perfect and 1 imperfect interpolant sequences [2024-06-20 17:47:48,975 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1597216816] [2024-06-20 17:47:48,975 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-06-20 17:47:48,976 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-06-20 17:47:48,976 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-06-20 17:47:48,977 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) [2024-06-20 17:47:49,003 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-06-20 17:47:49,290 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-06-20 17:47:49,290 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-06-20 17:47:49,294 INFO L262 TraceCheckSpWp]: Trace formula consists of 642 conjuncts, 64 conjunts are in the unsatisfiable core [2024-06-20 17:47:49,303 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-06-20 17:47:49,307 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 21 [2024-06-20 17:47:49,407 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 207 treesize of output 187 [2024-06-20 17:47:49,414 WARN L214 Elim1Store]: Array PQE input equivalent to false [2024-06-20 17:47:49,428 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 43 treesize of output 32 [2024-06-20 17:47:49,477 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 193 treesize of output 175 [2024-06-20 17:47:49,501 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 99 treesize of output 83 [2024-06-20 17:47:49,597 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 204 treesize of output 184 [2024-06-20 17:47:49,711 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 215 treesize of output 193 [2024-06-20 17:47:49,822 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 226 treesize of output 202 [2024-06-20 17:47:49,973 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 237 treesize of output 211 [2024-06-20 17:47:50,002 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 187 treesize of output 159 [2024-06-20 17:47:50,033 WARN L214 Elim1Store]: Array PQE input equivalent to false [2024-06-20 17:47:50,229 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 248 treesize of output 220 [2024-06-20 17:47:50,552 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 213 treesize of output 191 [2024-06-20 17:47:50,976 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 224 treesize of output 200 [2024-06-20 17:47:51,560 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 235 treesize of output 209 [2024-06-20 17:47:51,636 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2024-06-20 17:47:52,317 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 225 treesize of output 201 [2024-06-20 17:47:52,420 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2024-06-20 17:47:53,118 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 0 proven. 55 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-06-20 17:47:53,118 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-06-20 17:47:53,570 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 9 treesize of output 5 [2024-06-20 17:47:54,231 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 30 treesize of output 18 [2024-06-20 17:47:55,030 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 62 treesize of output 34 [2024-06-20 17:47:55,076 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 20 [2024-06-20 17:47:55,104 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 4 [2024-06-20 17:47:55,200 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 71 treesize of output 39 [2024-06-20 17:47:55,279 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 25 [2024-06-20 17:47:55,352 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 58 treesize of output 34 [2024-06-20 17:47:55,374 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 10 [2024-06-20 17:47:55,469 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 27 treesize of output 23 [2024-06-20 17:47:55,534 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 30 treesize of output 18 [2024-06-20 17:47:56,618 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 27 treesize of output 23 [2024-06-20 17:50:21,866 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 0 proven. 54 refuted. 1 times theorem prover too weak. 0 trivial. 0 not checked. [2024-06-20 17:50:21,866 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1597216816] provided 0 perfect and 2 imperfect interpolant sequences [2024-06-20 17:50:21,866 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-06-20 17:50:21,866 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13, 14] total 40 [2024-06-20 17:50:21,867 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [758887288] [2024-06-20 17:50:21,867 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-06-20 17:50:21,867 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 42 states [2024-06-20 17:50:21,867 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-06-20 17:50:21,868 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 42 interpolants. [2024-06-20 17:50:21,868 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=547, Invalid=1171, Unknown=4, NotChecked=0, Total=1722 [2024-06-20 17:50:21,869 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 7 out of 35 [2024-06-20 17:50:21,869 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 66 places, 41 transitions, 260 flow. Second operand has 42 states, 42 states have (on average 8.285714285714286) internal successors, (348), 42 states have internal predecessors, (348), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-06-20 17:50:21,869 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-06-20 17:50:21,869 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 7 of 35 [2024-06-20 17:50:21,869 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-06-20 17:50:35,825 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.76s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2024-06-20 17:50:37,086 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.24s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2024-06-20 17:50:42,210 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.03s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2024-06-20 17:50:47,047 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.10s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2024-06-20 17:51:00,964 WARN L293 SmtUtils]: Spent 8.68s on a formula simplification. DAG size of input: 1610 DAG size of output: 1182 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-06-20 17:52:03,000 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2024-06-20 17:52:09,510 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.14s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2024-06-20 17:52:33,191 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2024-06-20 17:52:33,280 INFO L124 PetriNetUnfolderBase]: 669/1207 cut-off events. [2024-06-20 17:52:33,280 INFO L125 PetriNetUnfolderBase]: For 12800/12800 co-relation queries the response was YES. [2024-06-20 17:52:33,283 INFO L83 FinitePrefix]: Finished finitePrefix Result has 5521 conditions, 1207 events. 669/1207 cut-off events. For 12800/12800 co-relation queries the response was YES. Maximal size of possible extension queue 35. Compared 4644 event pairs, 37 based on Foata normal form. 100/1307 useless extension candidates. Maximal degree in co-relation 5495. Up to 341 conditions per place. [2024-06-20 17:52:33,286 INFO L140 encePairwiseOnDemand]: 27/35 looper letters, 187 selfloop transitions, 36 changer transitions 0/227 dead transitions. [2024-06-20 17:52:33,287 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 89 places, 227 transitions, 1462 flow [2024-06-20 17:52:33,287 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2024-06-20 17:52:33,287 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 24 states. [2024-06-20 17:52:33,288 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 411 transitions. [2024-06-20 17:52:33,288 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.48928571428571427 [2024-06-20 17:52:33,289 INFO L175 Difference]: Start difference. First operand has 66 places, 41 transitions, 260 flow. Second operand 24 states and 411 transitions. [2024-06-20 17:52:33,289 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 89 places, 227 transitions, 1462 flow [2024-06-20 17:52:33,295 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 88 places, 227 transitions, 1445 flow, removed 0 selfloop flow, removed 1 redundant places. [2024-06-20 17:52:33,298 INFO L231 Difference]: Finished difference. Result has 98 places, 61 transitions, 549 flow [2024-06-20 17:52:33,299 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=35, PETRI_DIFFERENCE_MINUEND_FLOW=253, PETRI_DIFFERENCE_MINUEND_PLACES=65, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=41, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=18, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=23, PETRI_DIFFERENCE_SUBTRAHEND_STATES=24, PETRI_FLOW=549, PETRI_PLACES=98, PETRI_TRANSITIONS=61} [2024-06-20 17:52:33,299 INFO L281 CegarLoopForPetriNet]: 34 programPoint places, 64 predicate places. [2024-06-20 17:52:33,299 INFO L495 AbstractCegarLoop]: Abstraction has has 98 places, 61 transitions, 549 flow [2024-06-20 17:52:33,300 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 42 states, 42 states have (on average 8.285714285714286) internal successors, (348), 42 states have internal predecessors, (348), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-06-20 17:52:33,300 INFO L200 CegarLoopForPetriNet]: Found error trace [2024-06-20 17:52:33,300 INFO L208 CegarLoopForPetriNet]: trace histogram [10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-06-20 17:52:33,312 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-06-20 17:52:33,512 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-06-20 17:52:33,512 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONWITNESS_INVARIANT === [ULTIMATE.startErr0ASSERT_VIOLATIONWITNESS_INVARIANT, ULTIMATE.startErr1ASSERT_VIOLATIONWITNESS_INVARIANT, ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (and 1 more)] === [2024-06-20 17:52:33,513 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-06-20 17:52:33,513 INFO L85 PathProgramCache]: Analyzing trace with hash -1006334372, now seen corresponding path program 3 times [2024-06-20 17:52:33,513 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-06-20 17:52:33,513 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1836339328] [2024-06-20 17:52:33,513 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-06-20 17:52:33,513 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-06-20 17:52:33,564 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-06-20 17:52:33,850 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 0 proven. 55 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-06-20 17:52:33,850 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-06-20 17:52:33,850 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1836339328] [2024-06-20 17:52:33,850 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1836339328] provided 0 perfect and 1 imperfect interpolant sequences [2024-06-20 17:52:33,850 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [981566109] [2024-06-20 17:52:33,850 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-06-20 17:52:33,850 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-06-20 17:52:33,850 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-06-20 17:52:33,851 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-06-20 17:52:33,852 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-06-20 17:52:35,542 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2024-06-20 17:52:35,542 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-06-20 17:52:35,547 INFO L262 TraceCheckSpWp]: Trace formula consists of 631 conjuncts, 12 conjunts are in the unsatisfiable core [2024-06-20 17:52:35,549 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-06-20 17:52:35,576 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 0 proven. 55 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-06-20 17:52:35,576 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-06-20 17:52:35,846 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 0 proven. 55 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-06-20 17:52:35,846 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [981566109] provided 0 perfect and 2 imperfect interpolant sequences [2024-06-20 17:52:35,847 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-06-20 17:52:35,847 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13, 13] total 23 [2024-06-20 17:52:35,847 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1062269883] [2024-06-20 17:52:35,847 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-06-20 17:52:35,847 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2024-06-20 17:52:35,848 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-06-20 17:52:35,848 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-06-20 17:52:35,848 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=253, Invalid=253, Unknown=0, NotChecked=0, Total=506 [2024-06-20 17:52:35,848 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 7 out of 35 [2024-06-20 17:52:35,849 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 98 places, 61 transitions, 549 flow. Second operand has 23 states, 23 states have (on average 8.391304347826088) internal successors, (193), 23 states have internal predecessors, (193), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-06-20 17:52:35,849 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-06-20 17:52:35,849 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 7 of 35 [2024-06-20 17:52:35,849 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-06-20 17:52:36,436 INFO L124 PetriNetUnfolderBase]: 429/839 cut-off events. [2024-06-20 17:52:36,437 INFO L125 PetriNetUnfolderBase]: For 11348/11348 co-relation queries the response was YES. [2024-06-20 17:52:36,439 INFO L83 FinitePrefix]: Finished finitePrefix Result has 3893 conditions, 839 events. 429/839 cut-off events. For 11348/11348 co-relation queries the response was YES. Maximal size of possible extension queue 17. Compared 3023 event pairs, 137 based on Foata normal form. 120/958 useless extension candidates. Maximal degree in co-relation 3856. Up to 335 conditions per place. [2024-06-20 17:52:36,442 INFO L140 encePairwiseOnDemand]: 32/35 looper letters, 166 selfloop transitions, 21 changer transitions 0/191 dead transitions. [2024-06-20 17:52:36,442 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 119 places, 191 transitions, 1145 flow [2024-06-20 17:52:36,442 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2024-06-20 17:52:36,443 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 22 states. [2024-06-20 17:52:36,443 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 22 states to 22 states and 347 transitions. [2024-06-20 17:52:36,444 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.45064935064935063 [2024-06-20 17:52:36,444 INFO L175 Difference]: Start difference. First operand has 98 places, 61 transitions, 549 flow. Second operand 22 states and 347 transitions. [2024-06-20 17:52:36,444 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 119 places, 191 transitions, 1145 flow [2024-06-20 17:52:36,454 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 107 places, 191 transitions, 1031 flow, removed 43 selfloop flow, removed 12 redundant places. [2024-06-20 17:52:36,456 INFO L231 Difference]: Finished difference. Result has 117 places, 51 transitions, 419 flow [2024-06-20 17:52:36,456 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=35, PETRI_DIFFERENCE_MINUEND_FLOW=337, PETRI_DIFFERENCE_MINUEND_PLACES=86, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=51, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=21, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=30, PETRI_DIFFERENCE_SUBTRAHEND_STATES=22, PETRI_FLOW=419, PETRI_PLACES=117, PETRI_TRANSITIONS=51} [2024-06-20 17:52:36,456 INFO L281 CegarLoopForPetriNet]: 34 programPoint places, 83 predicate places. [2024-06-20 17:52:36,456 INFO L495 AbstractCegarLoop]: Abstraction has has 117 places, 51 transitions, 419 flow [2024-06-20 17:52:36,457 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 8.391304347826088) internal successors, (193), 23 states have internal predecessors, (193), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-06-20 17:52:36,457 INFO L200 CegarLoopForPetriNet]: Found error trace [2024-06-20 17:52:36,457 INFO L208 CegarLoopForPetriNet]: trace histogram [21, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-06-20 17:52:36,471 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2024-06-20 17:52:36,671 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-06-20 17:52:36,671 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONWITNESS_INVARIANT === [ULTIMATE.startErr0ASSERT_VIOLATIONWITNESS_INVARIANT, ULTIMATE.startErr1ASSERT_VIOLATIONWITNESS_INVARIANT, ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (and 1 more)] === [2024-06-20 17:52:36,672 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-06-20 17:52:36,672 INFO L85 PathProgramCache]: Analyzing trace with hash -1025671962, now seen corresponding path program 5 times [2024-06-20 17:52:36,672 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-06-20 17:52:36,672 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1664479197] [2024-06-20 17:52:36,672 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-06-20 17:52:36,672 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-06-20 17:52:36,736 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-06-20 17:52:37,538 INFO L134 CoverageAnalysis]: Checked inductivity of 210 backedges. 190 proven. 20 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-06-20 17:52:37,539 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-06-20 17:52:37,539 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1664479197] [2024-06-20 17:52:37,539 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1664479197] provided 0 perfect and 1 imperfect interpolant sequences [2024-06-20 17:52:37,539 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [847473921] [2024-06-20 17:52:37,539 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-06-20 17:52:37,539 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-06-20 17:52:37,539 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-06-20 17:52:37,541 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-06-20 17:52:37,543 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process Killed by 15