./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/pthread/stack_longer-2.i --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 3061b6dc Calling Ultimate with: /root/.sdkman/candidates/java/11.0.12-open/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/AutomizerReach.xml -i ../sv-benchmarks/c/pthread/stack_longer-2.i -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 402cb3c5f3290109e83e598d96446a87fac59fa4aaa0b6234366e7da005f5688 --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.dk.eval-assert-order-craig-3061b6d-m [2024-11-19 01:27:40,079 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-19 01:27:40,154 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-19 01:27:40,164 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-19 01:27:40,165 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-19 01:27:40,194 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-19 01:27:40,195 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-19 01:27:40,195 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-19 01:27:40,196 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-19 01:27:40,196 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-19 01:27:40,197 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-19 01:27:40,197 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-19 01:27:40,198 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-19 01:27:40,198 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-19 01:27:40,200 INFO L153 SettingsManager]: * Use SBE=true [2024-11-19 01:27:40,201 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-19 01:27:40,201 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-19 01:27:40,201 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-19 01:27:40,201 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-19 01:27:40,202 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-19 01:27:40,202 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-19 01:27:40,206 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-19 01:27:40,206 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-19 01:27:40,207 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-19 01:27:40,207 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-19 01:27:40,207 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-19 01:27:40,207 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-19 01:27:40,208 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-19 01:27:40,208 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-19 01:27:40,208 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-19 01:27:40,209 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-19 01:27:40,209 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-19 01:27:40,209 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-19 01:27:40,209 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-19 01:27:40,209 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-19 01:27:40,210 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-19 01:27:40,210 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-19 01:27:40,210 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-19 01:27:40,210 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-19 01:27:40,211 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-19 01:27:40,211 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-19 01:27:40,211 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-19 01:27:40,212 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.witnessprinter: Witness directory -> /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 402cb3c5f3290109e83e598d96446a87fac59fa4aaa0b6234366e7da005f5688 [2024-11-19 01:27:40,506 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-19 01:27:40,533 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-19 01:27:40,536 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-19 01:27:40,537 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-19 01:27:40,538 INFO L274 PluginConnector]: CDTParser initialized [2024-11-19 01:27:40,540 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/pthread/stack_longer-2.i [2024-11-19 01:27:41,956 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-19 01:27:42,228 INFO L384 CDTParser]: Found 1 translation units. [2024-11-19 01:27:42,230 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/pthread/stack_longer-2.i [2024-11-19 01:27:42,255 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/9ec1b9fa4/163afd697cee4839bfaebe2846fb9f26/FLAG04739ac1b [2024-11-19 01:27:42,529 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/9ec1b9fa4/163afd697cee4839bfaebe2846fb9f26 [2024-11-19 01:27:42,531 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-19 01:27:42,533 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-19 01:27:42,534 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-19 01:27:42,534 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-19 01:27:42,538 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-19 01:27:42,539 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.11 01:27:42" (1/1) ... [2024-11-19 01:27:42,539 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@abf1fb and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 01:27:42, skipping insertion in model container [2024-11-19 01:27:42,540 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.11 01:27:42" (1/1) ... [2024-11-19 01:27:42,595 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-19 01:27:43,096 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/pthread/stack_longer-2.i[41529,41542] [2024-11-19 01:27:43,134 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-19 01:27:43,171 INFO L200 MainTranslator]: Completed pre-run [2024-11-19 01:27:43,214 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/pthread/stack_longer-2.i[41529,41542] [2024-11-19 01:27:43,220 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-19 01:27:43,303 INFO L204 MainTranslator]: Completed translation [2024-11-19 01:27:43,304 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 01:27:43 WrapperNode [2024-11-19 01:27:43,304 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-19 01:27:43,305 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-19 01:27:43,305 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-19 01:27:43,305 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-19 01:27:43,312 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 01:27:43" (1/1) ... [2024-11-19 01:27:43,349 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 01:27:43" (1/1) ... [2024-11-19 01:27:43,412 INFO L138 Inliner]: procedures = 277, calls = 430, calls flagged for inlining = 11, calls inlined = 11, statements flattened = 545 [2024-11-19 01:27:43,413 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-19 01:27:43,418 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-19 01:27:43,418 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-19 01:27:43,418 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-19 01:27:43,430 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 01:27:43" (1/1) ... [2024-11-19 01:27:43,431 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 01:27:43" (1/1) ... [2024-11-19 01:27:43,442 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 01:27:43" (1/1) ... [2024-11-19 01:27:43,484 INFO L175 MemorySlicer]: Split 409 memory accesses to 3 slices as follows [2, 5, 402]. 98 percent of accesses are in the largest equivalence class. The 407 initializations are split as follows [2, 5, 400]. The 1 writes are split as follows [0, 0, 1]. [2024-11-19 01:27:43,485 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 01:27:43" (1/1) ... [2024-11-19 01:27:43,485 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 01:27:43" (1/1) ... [2024-11-19 01:27:43,507 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 01:27:43" (1/1) ... [2024-11-19 01:27:43,512 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 01:27:43" (1/1) ... [2024-11-19 01:27:43,516 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 01:27:43" (1/1) ... [2024-11-19 01:27:43,519 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 01:27:43" (1/1) ... [2024-11-19 01:27:43,525 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-19 01:27:43,526 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-19 01:27:43,526 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-19 01:27:43,527 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-19 01:27:43,527 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 01:27:43" (1/1) ... [2024-11-19 01:27:43,533 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-19 01:27:43,551 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 01:27:43,580 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-11-19 01:27:43,583 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-11-19 01:27:43,627 INFO L130 BoogieDeclarations]: Found specification of procedure t1 [2024-11-19 01:27:43,627 INFO L138 BoogieDeclarations]: Found implementation of procedure t1 [2024-11-19 01:27:43,627 INFO L130 BoogieDeclarations]: Found specification of procedure t2 [2024-11-19 01:27:43,627 INFO L138 BoogieDeclarations]: Found implementation of procedure t2 [2024-11-19 01:27:43,628 INFO L130 BoogieDeclarations]: Found specification of procedure #PthreadsMutexUnlock [2024-11-19 01:27:43,628 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2024-11-19 01:27:43,628 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2024-11-19 01:27:43,628 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#2 [2024-11-19 01:27:43,628 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2024-11-19 01:27:43,628 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2024-11-19 01:27:43,629 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#2 [2024-11-19 01:27:43,629 INFO L130 BoogieDeclarations]: Found specification of procedure #PthreadsMutexLock [2024-11-19 01:27:43,629 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-19 01:27:43,629 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-19 01:27:43,629 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2024-11-19 01:27:43,629 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2024-11-19 01:27:43,630 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-19 01:27:43,630 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-19 01:27:43,632 WARN L207 CfgBuilder]: User set CodeBlockSize to SequenceOfStatements but program contains fork statements. Overwriting the user preferences and setting CodeBlockSize to OneNontrivialStatement. [2024-11-19 01:27:43,763 INFO L238 CfgBuilder]: Building ICFG [2024-11-19 01:27:43,766 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-19 01:27:44,470 INFO L283 CfgBuilder]: Omitted future-live optimization because the input is a concurrent program. [2024-11-19 01:27:44,471 INFO L287 CfgBuilder]: Performing block encoding [2024-11-19 01:27:49,159 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-19 01:27:49,161 INFO L316 CfgBuilder]: Removed 2 assume(true) statements. [2024-11-19 01:27:49,162 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.11 01:27:49 BoogieIcfgContainer [2024-11-19 01:27:49,162 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-19 01:27:49,164 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-19 01:27:49,164 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-19 01:27:49,168 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-19 01:27:49,168 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 19.11 01:27:42" (1/3) ... [2024-11-19 01:27:49,169 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6a5a3c3d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.11 01:27:49, skipping insertion in model container [2024-11-19 01:27:49,169 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 01:27:43" (2/3) ... [2024-11-19 01:27:49,169 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6a5a3c3d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.11 01:27:49, skipping insertion in model container [2024-11-19 01:27:49,170 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.11 01:27:49" (3/3) ... [2024-11-19 01:27:49,171 INFO L112 eAbstractionObserver]: Analyzing ICFG stack_longer-2.i [2024-11-19 01:27:49,189 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-19 01:27:49,189 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 2 error locations. [2024-11-19 01:27:49,189 INFO L489 ceAbstractionStarter]: Constructing petrified ICFG for 1 thread instances. [2024-11-19 01:27:49,370 INFO L143 ThreadInstanceAdder]: Constructed 2 joinOtherThreadTransitions. [2024-11-19 01:27:49,408 INFO L73 FinitePrefix]: Start finitePrefix. Operand has 36 places, 34 transitions, 82 flow [2024-11-19 01:27:49,457 INFO L124 PetriNetUnfolderBase]: 5/32 cut-off events. [2024-11-19 01:27:49,458 INFO L125 PetriNetUnfolderBase]: For 2/2 co-relation queries the response was YES. [2024-11-19 01:27:49,462 INFO L83 FinitePrefix]: Finished finitePrefix Result has 41 conditions, 32 events. 5/32 cut-off events. For 2/2 co-relation queries the response was YES. Maximal size of possible extension queue 5. Compared 61 event pairs, 0 based on Foata normal form. 0/25 useless extension candidates. Maximal degree in co-relation 29. Up to 3 conditions per place. [2024-11-19 01:27:49,463 INFO L82 GeneralOperation]: Start removeDead. Operand has 36 places, 34 transitions, 82 flow [2024-11-19 01:27:49,467 INFO L88 GeneralOperation]: Finished RemoveDead, result has has 32 places, 30 transitions, 69 flow [2024-11-19 01:27:49,479 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-19 01:27:49,488 INFO L333 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, 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;@31a09087, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-19 01:27:49,488 INFO L334 AbstractCegarLoop]: Starting to check reachability of 6 error locations. [2024-11-19 01:27:49,514 INFO L185 PetriNetUnfolderBase]: Found word, exiting Unfolder. [2024-11-19 01:27:49,515 INFO L124 PetriNetUnfolderBase]: 1/18 cut-off events. [2024-11-19 01:27:49,515 INFO L125 PetriNetUnfolderBase]: For 1/1 co-relation queries the response was YES. [2024-11-19 01:27:49,515 INFO L196 CegarLoopForPetriNet]: Found error trace [2024-11-19 01:27:49,516 INFO L204 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 01:27:49,516 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting t1Err0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES, ULTIMATE.startErr1INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (and 4 more)] === [2024-11-19 01:27:49,521 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 01:27:49,521 INFO L85 PathProgramCache]: Analyzing trace with hash -998558077, now seen corresponding path program 1 times [2024-11-19 01:27:49,529 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 01:27:49,530 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [853579321] [2024-11-19 01:27:49,530 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 01:27:49,531 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 01:27:49,787 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 01:27:50,215 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-19 01:27:50,215 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 01:27:50,215 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [853579321] [2024-11-19 01:27:50,216 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [853579321] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-19 01:27:50,216 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-19 01:27:50,216 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-19 01:27:50,219 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2113929303] [2024-11-19 01:27:50,220 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-19 01:27:50,229 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-19 01:27:50,235 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 01:27:50,266 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-19 01:27:50,267 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-19 01:27:50,274 INFO L467 CegarLoopForPetriNet]: Number of universal loopers: 8 out of 34 [2024-11-19 01:27:50,277 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 32 places, 30 transitions, 69 flow. Second operand has 4 states, 4 states have (on average 9.5) internal successors, (38), 4 states have internal predecessors, (38), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-19 01:27:50,277 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-11-19 01:27:50,277 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 8 of 34 [2024-11-19 01:27:50,278 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-11-19 01:27:50,528 INFO L124 PetriNetUnfolderBase]: 307/576 cut-off events. [2024-11-19 01:27:50,529 INFO L125 PetriNetUnfolderBase]: For 30/30 co-relation queries the response was YES. [2024-11-19 01:27:50,531 INFO L83 FinitePrefix]: Finished finitePrefix Result has 1132 conditions, 576 events. 307/576 cut-off events. For 30/30 co-relation queries the response was YES. Maximal size of possible extension queue 34. Compared 2564 event pairs, 53 based on Foata normal form. 43/582 useless extension candidates. Maximal degree in co-relation 1055. Up to 358 conditions per place. [2024-11-19 01:27:50,536 INFO L140 encePairwiseOnDemand]: 27/34 looper letters, 41 selfloop transitions, 3 changer transitions 2/52 dead transitions. [2024-11-19 01:27:50,536 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 35 places, 52 transitions, 214 flow [2024-11-19 01:27:50,538 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-19 01:27:50,540 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 4 states. [2024-11-19 01:27:50,546 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 83 transitions. [2024-11-19 01:27:50,548 INFO L512 CegarLoopForPetriNet]: DFA transition density 0.6102941176470589 [2024-11-19 01:27:50,550 INFO L175 Difference]: Start difference. First operand has 32 places, 30 transitions, 69 flow. Second operand 4 states and 83 transitions. [2024-11-19 01:27:50,551 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 35 places, 52 transitions, 214 flow [2024-11-19 01:27:50,554 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 32 places, 52 transitions, 205 flow, removed 0 selfloop flow, removed 3 redundant places. [2024-11-19 01:27:50,557 INFO L231 Difference]: Finished difference. Result has 34 places, 30 transitions, 82 flow [2024-11-19 01:27:50,558 INFO L260 CegarLoopForPetriNet]: {PETRI_ALPHABET=34, PETRI_DIFFERENCE_MINUEND_FLOW=60, PETRI_DIFFERENCE_MINUEND_PLACES=29, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=28, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=1, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=25, PETRI_DIFFERENCE_SUBTRAHEND_STATES=4, PETRI_FLOW=82, PETRI_PLACES=34, PETRI_TRANSITIONS=30} [2024-11-19 01:27:50,562 INFO L277 CegarLoopForPetriNet]: 32 programPoint places, 2 predicate places. [2024-11-19 01:27:50,562 INFO L471 AbstractCegarLoop]: Abstraction has has 34 places, 30 transitions, 82 flow [2024-11-19 01:27:50,562 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 9.5) internal successors, (38), 4 states have internal predecessors, (38), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-19 01:27:50,563 INFO L196 CegarLoopForPetriNet]: Found error trace [2024-11-19 01:27:50,563 INFO L204 CegarLoopForPetriNet]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 01:27:50,563 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-19 01:27:50,564 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting t1Err0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES, ULTIMATE.startErr1INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (and 4 more)] === [2024-11-19 01:27:50,564 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 01:27:50,565 INFO L85 PathProgramCache]: Analyzing trace with hash -739082850, now seen corresponding path program 1 times [2024-11-19 01:27:50,565 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 01:27:50,565 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2133533939] [2024-11-19 01:27:50,565 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 01:27:50,566 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 01:27:50,609 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 01:27:50,999 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-19 01:27:51,000 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 01:27:51,000 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2133533939] [2024-11-19 01:27:51,000 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2133533939] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-19 01:27:51,001 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [295084840] [2024-11-19 01:27:51,001 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 01:27:51,001 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 01:27:51,001 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 01:27:51,005 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-11-19 01:27:51,006 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-11-19 01:27:51,282 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 01:27:51,287 INFO L255 TraceCheckSpWp]: Trace formula consists of 919 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-19 01:27:51,295 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 01:27:51,369 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-11-19 01:27:51,456 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-19 01:27:51,456 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 01:27:51,544 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-19 01:27:51,545 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [295084840] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 01:27:51,545 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-19 01:27:51,545 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4, 4] total 7 [2024-11-19 01:27:51,546 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [994007463] [2024-11-19 01:27:51,546 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-19 01:27:51,547 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-19 01:27:51,547 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 01:27:51,548 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-19 01:27:51,549 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=35, Unknown=0, NotChecked=0, Total=56 [2024-11-19 01:27:51,552 INFO L467 CegarLoopForPetriNet]: Number of universal loopers: 7 out of 34 [2024-11-19 01:27:51,552 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 34 places, 30 transitions, 82 flow. Second operand has 8 states, 8 states have (on average 10.25) internal successors, (82), 8 states have internal predecessors, (82), 0 states have call successors, (0), 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-11-19 01:27:51,553 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-11-19 01:27:51,553 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 7 of 34 [2024-11-19 01:27:51,553 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-11-19 01:27:52,289 INFO L124 PetriNetUnfolderBase]: 1257/2340 cut-off events. [2024-11-19 01:27:52,289 INFO L125 PetriNetUnfolderBase]: For 301/303 co-relation queries the response was YES. [2024-11-19 01:27:52,295 INFO L83 FinitePrefix]: Finished finitePrefix Result has 4928 conditions, 2340 events. 1257/2340 cut-off events. For 301/303 co-relation queries the response was YES. Maximal size of possible extension queue 76. Compared 12471 event pairs, 153 based on Foata normal form. 49/2288 useless extension candidates. Maximal degree in co-relation 4364. Up to 365 conditions per place. [2024-11-19 01:27:52,306 INFO L140 encePairwiseOnDemand]: 28/34 looper letters, 163 selfloop transitions, 32 changer transitions 4/204 dead transitions. [2024-11-19 01:27:52,306 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 48 places, 204 transitions, 900 flow [2024-11-19 01:27:52,307 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2024-11-19 01:27:52,307 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 15 states. [2024-11-19 01:27:52,308 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 313 transitions. [2024-11-19 01:27:52,309 INFO L512 CegarLoopForPetriNet]: DFA transition density 0.6137254901960785 [2024-11-19 01:27:52,310 INFO L175 Difference]: Start difference. First operand has 34 places, 30 transitions, 82 flow. Second operand 15 states and 313 transitions. [2024-11-19 01:27:52,310 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 48 places, 204 transitions, 900 flow [2024-11-19 01:27:52,313 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 47 places, 204 transitions, 896 flow, removed 0 selfloop flow, removed 1 redundant places. [2024-11-19 01:27:52,315 INFO L231 Difference]: Finished difference. Result has 54 places, 66 transitions, 329 flow [2024-11-19 01:27:52,315 INFO L260 CegarLoopForPetriNet]: {PETRI_ALPHABET=34, PETRI_DIFFERENCE_MINUEND_FLOW=80, PETRI_DIFFERENCE_MINUEND_PLACES=33, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=30, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=7, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=23, PETRI_DIFFERENCE_SUBTRAHEND_STATES=15, PETRI_FLOW=329, PETRI_PLACES=54, PETRI_TRANSITIONS=66} [2024-11-19 01:27:52,316 INFO L277 CegarLoopForPetriNet]: 32 programPoint places, 22 predicate places. [2024-11-19 01:27:52,316 INFO L471 AbstractCegarLoop]: Abstraction has has 54 places, 66 transitions, 329 flow [2024-11-19 01:27:52,317 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 10.25) internal successors, (82), 8 states have internal predecessors, (82), 0 states have call successors, (0), 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-11-19 01:27:52,317 INFO L196 CegarLoopForPetriNet]: Found error trace [2024-11-19 01:27:52,317 INFO L204 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 01:27:52,338 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-19 01:27:52,518 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 01:27:52,519 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting t2Err0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES, ULTIMATE.startErr1INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (and 4 more)] === [2024-11-19 01:27:52,519 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 01:27:52,519 INFO L85 PathProgramCache]: Analyzing trace with hash -1416957971, now seen corresponding path program 1 times [2024-11-19 01:27:52,519 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 01:27:52,520 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [24261774] [2024-11-19 01:27:52,520 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 01:27:52,520 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 01:27:52,558 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 01:27:52,763 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-19 01:27:52,763 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 01:27:52,763 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [24261774] [2024-11-19 01:27:52,763 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [24261774] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-19 01:27:52,764 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-19 01:27:52,764 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-19 01:27:52,765 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1039865323] [2024-11-19 01:27:52,765 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-19 01:27:52,766 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-19 01:27:52,766 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 01:27:52,767 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-19 01:27:52,767 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-19 01:27:52,768 INFO L467 CegarLoopForPetriNet]: Number of universal loopers: 8 out of 34 [2024-11-19 01:27:52,768 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 54 places, 66 transitions, 329 flow. Second operand has 3 states, 3 states have (on average 11.666666666666666) internal successors, (35), 3 states have internal predecessors, (35), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-19 01:27:52,768 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-11-19 01:27:52,768 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 8 of 34 [2024-11-19 01:27:52,768 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-11-19 01:27:52,964 INFO L124 PetriNetUnfolderBase]: 669/1355 cut-off events. [2024-11-19 01:27:52,964 INFO L125 PetriNetUnfolderBase]: For 603/603 co-relation queries the response was YES. [2024-11-19 01:27:52,968 INFO L83 FinitePrefix]: Finished finitePrefix Result has 3066 conditions, 1355 events. 669/1355 cut-off events. For 603/603 co-relation queries the response was YES. Maximal size of possible extension queue 49. Compared 6877 event pairs, 231 based on Foata normal form. 66/1406 useless extension candidates. Maximal degree in co-relation 2918. Up to 634 conditions per place. [2024-11-19 01:27:52,974 INFO L140 encePairwiseOnDemand]: 30/34 looper letters, 43 selfloop transitions, 4 changer transitions 0/59 dead transitions. [2024-11-19 01:27:52,974 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 53 places, 59 transitions, 339 flow [2024-11-19 01:27:52,975 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-19 01:27:52,975 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3 states. [2024-11-19 01:27:52,975 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 58 transitions. [2024-11-19 01:27:52,976 INFO L512 CegarLoopForPetriNet]: DFA transition density 0.5686274509803921 [2024-11-19 01:27:52,976 INFO L175 Difference]: Start difference. First operand has 54 places, 66 transitions, 329 flow. Second operand 3 states and 58 transitions. [2024-11-19 01:27:52,976 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 53 places, 59 transitions, 339 flow [2024-11-19 01:27:52,986 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 50 places, 59 transitions, 307 flow, removed 16 selfloop flow, removed 3 redundant places. [2024-11-19 01:27:52,988 INFO L231 Difference]: Finished difference. Result has 50 places, 49 transitions, 198 flow [2024-11-19 01:27:52,989 INFO L260 CegarLoopForPetriNet]: {PETRI_ALPHABET=34, PETRI_DIFFERENCE_MINUEND_FLOW=190, PETRI_DIFFERENCE_MINUEND_PLACES=48, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=49, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=4, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=45, PETRI_DIFFERENCE_SUBTRAHEND_STATES=3, PETRI_FLOW=198, PETRI_PLACES=50, PETRI_TRANSITIONS=49} [2024-11-19 01:27:52,990 INFO L277 CegarLoopForPetriNet]: 32 programPoint places, 18 predicate places. [2024-11-19 01:27:52,991 INFO L471 AbstractCegarLoop]: Abstraction has has 50 places, 49 transitions, 198 flow [2024-11-19 01:27:52,991 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 11.666666666666666) internal successors, (35), 3 states have internal predecessors, (35), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-19 01:27:52,991 INFO L196 CegarLoopForPetriNet]: Found error trace [2024-11-19 01:27:52,992 INFO L204 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 01:27:52,992 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2024-11-19 01:27:52,992 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting t2Err0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES, ULTIMATE.startErr1INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (and 4 more)] === [2024-11-19 01:27:52,993 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 01:27:52,993 INFO L85 PathProgramCache]: Analyzing trace with hash -791385794, now seen corresponding path program 1 times [2024-11-19 01:27:52,993 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 01:27:52,993 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1364465251] [2024-11-19 01:27:52,993 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 01:27:52,994 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 01:27:53,068 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 01:27:54,135 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-19 01:27:54,136 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 01:27:54,136 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1364465251] [2024-11-19 01:27:54,136 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1364465251] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-19 01:27:54,136 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-19 01:27:54,137 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-19 01:27:54,137 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [250559146] [2024-11-19 01:27:54,137 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-19 01:27:54,137 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-19 01:27:54,138 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 01:27:54,138 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-19 01:27:54,138 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2024-11-19 01:27:54,143 INFO L467 CegarLoopForPetriNet]: Number of universal loopers: 8 out of 34 [2024-11-19 01:27:54,143 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 50 places, 49 transitions, 198 flow. Second operand has 5 states, 5 states have (on average 10.6) internal successors, (53), 5 states have internal predecessors, (53), 0 states have call successors, (0), 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-11-19 01:27:54,143 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-11-19 01:27:54,143 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 8 of 34 [2024-11-19 01:27:54,144 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-11-19 01:27:54,401 INFO L124 PetriNetUnfolderBase]: 840/1700 cut-off events. [2024-11-19 01:27:54,401 INFO L125 PetriNetUnfolderBase]: For 579/579 co-relation queries the response was YES. [2024-11-19 01:27:54,405 INFO L83 FinitePrefix]: Finished finitePrefix Result has 3884 conditions, 1700 events. 840/1700 cut-off events. For 579/579 co-relation queries the response was YES. Maximal size of possible extension queue 62. Compared 8915 event pairs, 260 based on Foata normal form. 0/1681 useless extension candidates. Maximal degree in co-relation 3504. Up to 971 conditions per place. [2024-11-19 01:27:54,412 INFO L140 encePairwiseOnDemand]: 29/34 looper letters, 61 selfloop transitions, 7 changer transitions 4/84 dead transitions. [2024-11-19 01:27:54,413 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 54 places, 84 transitions, 451 flow [2024-11-19 01:27:54,413 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-19 01:27:54,413 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 5 states. [2024-11-19 01:27:54,414 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 97 transitions. [2024-11-19 01:27:54,414 INFO L512 CegarLoopForPetriNet]: DFA transition density 0.5705882352941176 [2024-11-19 01:27:54,414 INFO L175 Difference]: Start difference. First operand has 50 places, 49 transitions, 198 flow. Second operand 5 states and 97 transitions. [2024-11-19 01:27:54,415 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 54 places, 84 transitions, 451 flow [2024-11-19 01:27:54,419 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 53 places, 84 transitions, 440 flow, removed 0 selfloop flow, removed 1 redundant places. [2024-11-19 01:27:54,421 INFO L231 Difference]: Finished difference. Result has 56 places, 54 transitions, 254 flow [2024-11-19 01:27:54,421 INFO L260 CegarLoopForPetriNet]: {PETRI_ALPHABET=34, PETRI_DIFFERENCE_MINUEND_FLOW=194, PETRI_DIFFERENCE_MINUEND_PLACES=49, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=49, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=2, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=42, PETRI_DIFFERENCE_SUBTRAHEND_STATES=5, PETRI_FLOW=254, PETRI_PLACES=56, PETRI_TRANSITIONS=54} [2024-11-19 01:27:54,422 INFO L277 CegarLoopForPetriNet]: 32 programPoint places, 24 predicate places. [2024-11-19 01:27:54,422 INFO L471 AbstractCegarLoop]: Abstraction has has 56 places, 54 transitions, 254 flow [2024-11-19 01:27:54,422 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 10.6) internal successors, (53), 5 states have internal predecessors, (53), 0 states have call successors, (0), 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-11-19 01:27:54,422 INFO L196 CegarLoopForPetriNet]: Found error trace [2024-11-19 01:27:54,422 INFO L204 CegarLoopForPetriNet]: trace histogram [2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 01:27:54,423 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2024-11-19 01:27:54,423 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting t2Err0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES, ULTIMATE.startErr1INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (and 4 more)] === [2024-11-19 01:27:54,423 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 01:27:54,424 INFO L85 PathProgramCache]: Analyzing trace with hash 803150271, now seen corresponding path program 1 times [2024-11-19 01:27:54,424 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 01:27:54,424 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [245942627] [2024-11-19 01:27:54,424 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 01:27:54,424 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 01:27:54,478 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 01:27:55,356 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-19 01:27:55,357 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 01:27:55,357 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [245942627] [2024-11-19 01:27:55,357 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [245942627] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-19 01:27:55,357 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [119659840] [2024-11-19 01:27:55,358 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 01:27:55,358 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 01:27:55,358 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 01:27:55,360 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-11-19 01:27:55,362 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-11-19 01:27:55,610 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 01:27:55,616 INFO L255 TraceCheckSpWp]: Trace formula consists of 964 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-11-19 01:27:55,621 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 01:27:55,673 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-11-19 01:27:55,772 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 25 treesize of output 1 [2024-11-19 01:27:55,878 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 80 treesize of output 32 [2024-11-19 01:27:55,937 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-19 01:27:55,938 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 01:27:56,364 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 9 treesize of output 1 [2024-11-19 01:27:56,422 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-19 01:27:56,423 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [119659840] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 01:27:56,423 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-19 01:27:56,423 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5, 5] total 13 [2024-11-19 01:27:56,424 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1167694592] [2024-11-19 01:27:56,424 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-19 01:27:56,425 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-11-19 01:27:56,425 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 01:27:56,426 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-11-19 01:27:56,426 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=47, Invalid=135, Unknown=0, NotChecked=0, Total=182 [2024-11-19 01:27:56,429 INFO L467 CegarLoopForPetriNet]: Number of universal loopers: 7 out of 34 [2024-11-19 01:27:56,429 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 56 places, 54 transitions, 254 flow. Second operand has 14 states, 14 states have (on average 10.857142857142858) internal successors, (152), 14 states have internal predecessors, (152), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-19 01:27:56,430 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-11-19 01:27:56,430 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 7 of 34 [2024-11-19 01:27:56,430 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-11-19 01:27:57,830 INFO L124 PetriNetUnfolderBase]: 1747/3464 cut-off events. [2024-11-19 01:27:57,830 INFO L125 PetriNetUnfolderBase]: For 1581/1581 co-relation queries the response was YES. [2024-11-19 01:27:57,841 INFO L83 FinitePrefix]: Finished finitePrefix Result has 7901 conditions, 3464 events. 1747/3464 cut-off events. For 1581/1581 co-relation queries the response was YES. Maximal size of possible extension queue 78. Compared 18903 event pairs, 341 based on Foata normal form. 14/3413 useless extension candidates. Maximal degree in co-relation 6810. Up to 566 conditions per place. [2024-11-19 01:27:57,858 INFO L140 encePairwiseOnDemand]: 28/34 looper letters, 201 selfloop transitions, 52 changer transitions 18/276 dead transitions. [2024-11-19 01:27:57,858 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 77 places, 276 transitions, 1488 flow [2024-11-19 01:27:57,859 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2024-11-19 01:27:57,859 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 22 states. [2024-11-19 01:27:57,861 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 22 states to 22 states and 413 transitions. [2024-11-19 01:27:57,861 INFO L512 CegarLoopForPetriNet]: DFA transition density 0.5521390374331551 [2024-11-19 01:27:57,861 INFO L175 Difference]: Start difference. First operand has 56 places, 54 transitions, 254 flow. Second operand 22 states and 413 transitions. [2024-11-19 01:27:57,862 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 77 places, 276 transitions, 1488 flow [2024-11-19 01:27:57,871 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 76 places, 276 transitions, 1480 flow, removed 3 selfloop flow, removed 1 redundant places. [2024-11-19 01:27:57,874 INFO L231 Difference]: Finished difference. Result has 81 places, 89 transitions, 542 flow [2024-11-19 01:27:57,875 INFO L260 CegarLoopForPetriNet]: {PETRI_ALPHABET=34, PETRI_DIFFERENCE_MINUEND_FLOW=240, PETRI_DIFFERENCE_MINUEND_PLACES=55, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=53, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=22, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=31, PETRI_DIFFERENCE_SUBTRAHEND_STATES=22, PETRI_FLOW=542, PETRI_PLACES=81, PETRI_TRANSITIONS=89} [2024-11-19 01:27:57,875 INFO L277 CegarLoopForPetriNet]: 32 programPoint places, 49 predicate places. [2024-11-19 01:27:57,876 INFO L471 AbstractCegarLoop]: Abstraction has has 81 places, 89 transitions, 542 flow [2024-11-19 01:27:57,876 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 10.857142857142858) internal successors, (152), 14 states have internal predecessors, (152), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-19 01:27:57,876 INFO L196 CegarLoopForPetriNet]: Found error trace [2024-11-19 01:27:57,876 INFO L204 CegarLoopForPetriNet]: trace histogram [3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 01:27:57,896 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-11-19 01:27:58,080 WARN L453 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-11-19 01:27:58,081 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting t1Err0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES, ULTIMATE.startErr1INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (and 4 more)] === [2024-11-19 01:27:58,081 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 01:27:58,081 INFO L85 PathProgramCache]: Analyzing trace with hash 1837970026, now seen corresponding path program 1 times [2024-11-19 01:27:58,082 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 01:27:58,082 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1508502808] [2024-11-19 01:27:58,082 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 01:27:58,082 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 01:27:58,131 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 01:27:58,535 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 0 proven. 11 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2024-11-19 01:27:58,535 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 01:27:58,535 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1508502808] [2024-11-19 01:27:58,536 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1508502808] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-19 01:27:58,536 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [884086120] [2024-11-19 01:27:58,536 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 01:27:58,536 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 01:27:58,536 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 01:27:58,540 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-11-19 01:27:58,541 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-11-19 01:27:58,758 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 01:27:58,763 INFO L255 TraceCheckSpWp]: Trace formula consists of 991 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-19 01:27:58,769 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 01:27:58,794 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-11-19 01:27:58,847 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-11-19 01:27:59,017 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 0 proven. 14 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-19 01:27:59,017 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 01:27:59,061 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 10 proven. 1 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2024-11-19 01:27:59,062 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [884086120] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 01:27:59,062 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-19 01:27:59,062 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 6, 5] total 12 [2024-11-19 01:27:59,062 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1147426376] [2024-11-19 01:27:59,062 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-19 01:27:59,063 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-11-19 01:27:59,063 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 01:27:59,064 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-11-19 01:27:59,064 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=46, Invalid=86, Unknown=0, NotChecked=0, Total=132 [2024-11-19 01:27:59,070 INFO L467 CegarLoopForPetriNet]: Number of universal loopers: 7 out of 34 [2024-11-19 01:27:59,070 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 81 places, 89 transitions, 542 flow. Second operand has 12 states, 12 states have (on average 12.416666666666666) internal successors, (149), 12 states have internal predecessors, (149), 0 states have call successors, (0), 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-11-19 01:27:59,070 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-11-19 01:27:59,071 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 7 of 34 [2024-11-19 01:27:59,071 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-11-19 01:28:00,188 INFO L124 PetriNetUnfolderBase]: 2797/5529 cut-off events. [2024-11-19 01:28:00,189 INFO L125 PetriNetUnfolderBase]: For 4758/4758 co-relation queries the response was YES. [2024-11-19 01:28:00,212 INFO L83 FinitePrefix]: Finished finitePrefix Result has 13169 conditions, 5529 events. 2797/5529 cut-off events. For 4758/4758 co-relation queries the response was YES. Maximal size of possible extension queue 97. Compared 31240 event pairs, 415 based on Foata normal form. 66/5537 useless extension candidates. Maximal degree in co-relation 12319. Up to 908 conditions per place. [2024-11-19 01:28:00,239 INFO L140 encePairwiseOnDemand]: 28/34 looper letters, 189 selfloop transitions, 90 changer transitions 8/292 dead transitions. [2024-11-19 01:28:00,240 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 99 places, 292 transitions, 1850 flow [2024-11-19 01:28:00,240 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-11-19 01:28:00,240 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 19 states. [2024-11-19 01:28:00,241 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 19 states to 19 states and 352 transitions. [2024-11-19 01:28:00,242 INFO L512 CegarLoopForPetriNet]: DFA transition density 0.544891640866873 [2024-11-19 01:28:00,242 INFO L175 Difference]: Start difference. First operand has 81 places, 89 transitions, 542 flow. Second operand 19 states and 352 transitions. [2024-11-19 01:28:00,242 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 99 places, 292 transitions, 1850 flow [2024-11-19 01:28:00,262 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 99 places, 292 transitions, 1820 flow, removed 15 selfloop flow, removed 0 redundant places. [2024-11-19 01:28:00,265 INFO L231 Difference]: Finished difference. Result has 105 places, 131 transitions, 1056 flow [2024-11-19 01:28:00,266 INFO L260 CegarLoopForPetriNet]: {PETRI_ALPHABET=34, PETRI_DIFFERENCE_MINUEND_FLOW=518, PETRI_DIFFERENCE_MINUEND_PLACES=81, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=89, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=53, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=34, PETRI_DIFFERENCE_SUBTRAHEND_STATES=19, PETRI_FLOW=1056, PETRI_PLACES=105, PETRI_TRANSITIONS=131} [2024-11-19 01:28:00,267 INFO L277 CegarLoopForPetriNet]: 32 programPoint places, 73 predicate places. [2024-11-19 01:28:00,268 INFO L471 AbstractCegarLoop]: Abstraction has has 105 places, 131 transitions, 1056 flow [2024-11-19 01:28:00,269 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 12.416666666666666) internal successors, (149), 12 states have internal predecessors, (149), 0 states have call successors, (0), 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-11-19 01:28:00,269 INFO L196 CegarLoopForPetriNet]: Found error trace [2024-11-19 01:28:00,269 INFO L204 CegarLoopForPetriNet]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 01:28:00,287 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-11-19 01:28:00,469 WARN L453 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-11-19 01:28:00,470 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting t2Err0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES, ULTIMATE.startErr1INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (and 4 more)] === [2024-11-19 01:28:00,471 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 01:28:00,471 INFO L85 PathProgramCache]: Analyzing trace with hash 1293758780, now seen corresponding path program 1 times [2024-11-19 01:28:00,471 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 01:28:00,471 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [127643335] [2024-11-19 01:28:00,471 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 01:28:00,471 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 01:28:00,647 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 01:28:01,637 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 4 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-19 01:28:01,638 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 01:28:01,638 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [127643335] [2024-11-19 01:28:01,638 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [127643335] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-19 01:28:01,639 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [640813332] [2024-11-19 01:28:01,639 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 01:28:01,639 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 01:28:01,639 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 01:28:01,641 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-11-19 01:28:01,642 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-11-19 01:28:01,865 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 01:28:01,868 INFO L255 TraceCheckSpWp]: Trace formula consists of 989 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-11-19 01:28:01,873 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 01:28:01,914 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 23 treesize of output 1 [2024-11-19 01:28:02,007 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 50 treesize of output 19 [2024-11-19 01:28:02,182 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 56 treesize of output 32 [2024-11-19 01:28:02,218 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-19 01:28:02,218 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 01:28:02,837 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-19 01:28:02,837 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 1 case distinctions, treesize of input 18 treesize of output 14 [2024-11-19 01:28:02,870 INFO L349 Elim1Store]: treesize reduction 17, result has 37.0 percent of original size [2024-11-19 01:28:02,871 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 78 treesize of output 65 [2024-11-19 01:28:02,944 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-19 01:28:02,944 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [640813332] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 01:28:02,944 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-19 01:28:02,945 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 6] total 16 [2024-11-19 01:28:02,945 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [771184482] [2024-11-19 01:28:02,945 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-19 01:28:02,945 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-11-19 01:28:02,946 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 01:28:02,946 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-11-19 01:28:02,947 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=67, Invalid=205, Unknown=0, NotChecked=0, Total=272 [2024-11-19 01:28:02,950 INFO L467 CegarLoopForPetriNet]: Number of universal loopers: 7 out of 34 [2024-11-19 01:28:02,951 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 105 places, 131 transitions, 1056 flow. Second operand has 17 states, 17 states have (on average 11.058823529411764) internal successors, (188), 17 states have internal predecessors, (188), 0 states have call successors, (0), 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-11-19 01:28:02,951 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-11-19 01:28:02,951 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 7 of 34 [2024-11-19 01:28:02,952 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-11-19 01:28:05,311 INFO L124 PetriNetUnfolderBase]: 4067/8026 cut-off events. [2024-11-19 01:28:05,311 INFO L125 PetriNetUnfolderBase]: For 10593/10593 co-relation queries the response was YES. [2024-11-19 01:28:05,345 INFO L83 FinitePrefix]: Finished finitePrefix Result has 20269 conditions, 8026 events. 4067/8026 cut-off events. For 10593/10593 co-relation queries the response was YES. Maximal size of possible extension queue 112. Compared 48084 event pairs, 990 based on Foata normal form. 56/8010 useless extension candidates. Maximal degree in co-relation 19060. Up to 1340 conditions per place. [2024-11-19 01:28:05,380 INFO L140 encePairwiseOnDemand]: 28/34 looper letters, 214 selfloop transitions, 127 changer transitions 36/382 dead transitions. [2024-11-19 01:28:05,380 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 129 places, 382 transitions, 2822 flow [2024-11-19 01:28:05,381 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2024-11-19 01:28:05,381 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 25 states. [2024-11-19 01:28:05,383 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 25 states to 25 states and 444 transitions. [2024-11-19 01:28:05,383 INFO L512 CegarLoopForPetriNet]: DFA transition density 0.5223529411764706 [2024-11-19 01:28:05,383 INFO L175 Difference]: Start difference. First operand has 105 places, 131 transitions, 1056 flow. Second operand 25 states and 444 transitions. [2024-11-19 01:28:05,383 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 129 places, 382 transitions, 2822 flow [2024-11-19 01:28:05,427 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 125 places, 382 transitions, 2749 flow, removed 27 selfloop flow, removed 4 redundant places. [2024-11-19 01:28:05,431 INFO L231 Difference]: Finished difference. Result has 131 places, 175 transitions, 1702 flow [2024-11-19 01:28:05,432 INFO L260 CegarLoopForPetriNet]: {PETRI_ALPHABET=34, PETRI_DIFFERENCE_MINUEND_FLOW=1013, PETRI_DIFFERENCE_MINUEND_PLACES=101, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=131, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=85, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=45, PETRI_DIFFERENCE_SUBTRAHEND_STATES=25, PETRI_FLOW=1702, PETRI_PLACES=131, PETRI_TRANSITIONS=175} [2024-11-19 01:28:05,432 INFO L277 CegarLoopForPetriNet]: 32 programPoint places, 99 predicate places. [2024-11-19 01:28:05,433 INFO L471 AbstractCegarLoop]: Abstraction has has 131 places, 175 transitions, 1702 flow [2024-11-19 01:28:05,433 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 11.058823529411764) internal successors, (188), 17 states have internal predecessors, (188), 0 states have call successors, (0), 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-11-19 01:28:05,433 INFO L196 CegarLoopForPetriNet]: Found error trace [2024-11-19 01:28:05,433 INFO L204 CegarLoopForPetriNet]: trace histogram [5, 5, 5, 4, 4, 4, 1, 1, 1, 1, 1] [2024-11-19 01:28:05,447 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-11-19 01:28:05,633 WARN L453 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-11-19 01:28:05,634 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting t1Err0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES, ULTIMATE.startErr1INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (and 4 more)] === [2024-11-19 01:28:05,634 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 01:28:05,634 INFO L85 PathProgramCache]: Analyzing trace with hash 1648562543, now seen corresponding path program 2 times [2024-11-19 01:28:05,634 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 01:28:05,635 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1405593393] [2024-11-19 01:28:05,635 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-19 01:28:05,635 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 01:28:05,704 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-19 01:28:05,704 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 01:28:06,300 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 0 proven. 52 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-19 01:28:06,301 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 01:28:06,301 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1405593393] [2024-11-19 01:28:06,301 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1405593393] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-19 01:28:06,302 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [283787522] [2024-11-19 01:28:06,302 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-19 01:28:06,302 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 01:28:06,302 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 01:28:06,304 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-11-19 01:28:06,305 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-11-19 01:28:06,570 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-19 01:28:06,570 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 01:28:06,575 INFO L255 TraceCheckSpWp]: Trace formula consists of 1000 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-19 01:28:06,581 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 01:28:06,604 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-11-19 01:28:06,672 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-11-19 01:28:06,725 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-11-19 01:28:06,777 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-11-19 01:28:06,841 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 0 proven. 52 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-19 01:28:06,841 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 01:28:06,961 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 0 proven. 52 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-19 01:28:06,961 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [283787522] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 01:28:06,962 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-19 01:28:06,962 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 9, 9] total 22 [2024-11-19 01:28:06,962 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1771402120] [2024-11-19 01:28:06,962 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-19 01:28:06,962 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2024-11-19 01:28:06,963 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 01:28:06,963 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-11-19 01:28:06,964 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=177, Invalid=329, Unknown=0, NotChecked=0, Total=506 [2024-11-19 01:28:06,970 INFO L467 CegarLoopForPetriNet]: Number of universal loopers: 7 out of 34 [2024-11-19 01:28:06,971 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 131 places, 175 transitions, 1702 flow. Second operand has 23 states, 23 states have (on average 10.304347826086957) internal successors, (237), 23 states have internal predecessors, (237), 0 states have call successors, (0), 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-11-19 01:28:06,971 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-11-19 01:28:06,971 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 7 of 34 [2024-11-19 01:28:06,971 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-11-19 01:28:10,685 INFO L124 PetriNetUnfolderBase]: 10853/21198 cut-off events. [2024-11-19 01:28:10,685 INFO L125 PetriNetUnfolderBase]: For 43990/43990 co-relation queries the response was YES. [2024-11-19 01:28:10,862 INFO L83 FinitePrefix]: Finished finitePrefix Result has 57788 conditions, 21198 events. 10853/21198 cut-off events. For 43990/43990 co-relation queries the response was YES. Maximal size of possible extension queue 318. Compared 154518 event pairs, 1967 based on Foata normal form. 230/21293 useless extension candidates. Maximal degree in co-relation 55775. Up to 3519 conditions per place. [2024-11-19 01:28:10,946 INFO L140 encePairwiseOnDemand]: 28/34 looper letters, 563 selfloop transitions, 385 changer transitions 20/973 dead transitions. [2024-11-19 01:28:10,946 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 190 places, 973 transitions, 8175 flow [2024-11-19 01:28:10,947 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 60 states. [2024-11-19 01:28:10,947 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 60 states. [2024-11-19 01:28:10,950 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 60 states to 60 states and 1074 transitions. [2024-11-19 01:28:10,952 INFO L512 CegarLoopForPetriNet]: DFA transition density 0.5264705882352941 [2024-11-19 01:28:10,953 INFO L175 Difference]: Start difference. First operand has 131 places, 175 transitions, 1702 flow. Second operand 60 states and 1074 transitions. [2024-11-19 01:28:10,953 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 190 places, 973 transitions, 8175 flow [2024-11-19 01:28:11,272 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 187 places, 973 transitions, 8008 flow, removed 54 selfloop flow, removed 3 redundant places. [2024-11-19 01:28:11,283 INFO L231 Difference]: Finished difference. Result has 203 places, 458 transitions, 5290 flow [2024-11-19 01:28:11,283 INFO L260 CegarLoopForPetriNet]: {PETRI_ALPHABET=34, PETRI_DIFFERENCE_MINUEND_FLOW=1636, PETRI_DIFFERENCE_MINUEND_PLACES=128, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=175, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=129, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=45, PETRI_DIFFERENCE_SUBTRAHEND_STATES=60, PETRI_FLOW=5290, PETRI_PLACES=203, PETRI_TRANSITIONS=458} [2024-11-19 01:28:11,284 INFO L277 CegarLoopForPetriNet]: 32 programPoint places, 171 predicate places. [2024-11-19 01:28:11,284 INFO L471 AbstractCegarLoop]: Abstraction has has 203 places, 458 transitions, 5290 flow [2024-11-19 01:28:11,285 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 10.304347826086957) internal successors, (237), 23 states have internal predecessors, (237), 0 states have call successors, (0), 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-11-19 01:28:11,285 INFO L196 CegarLoopForPetriNet]: Found error trace [2024-11-19 01:28:11,285 INFO L204 CegarLoopForPetriNet]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 01:28:11,305 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2024-11-19 01:28:11,485 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 01:28:11,486 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting t2Err0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES, ULTIMATE.startErr1INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (and 4 more)] === [2024-11-19 01:28:11,486 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 01:28:11,486 INFO L85 PathProgramCache]: Analyzing trace with hash 1329187578, now seen corresponding path program 2 times [2024-11-19 01:28:11,487 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 01:28:11,487 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [317942534] [2024-11-19 01:28:11,487 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-19 01:28:11,487 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 01:28:11,629 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-19 01:28:11,630 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 01:28:13,232 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 15 proven. 18 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-19 01:28:13,233 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 01:28:13,233 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [317942534] [2024-11-19 01:28:13,233 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [317942534] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-19 01:28:13,233 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [552521738] [2024-11-19 01:28:13,233 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-19 01:28:13,233 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 01:28:13,234 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 01:28:13,236 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-11-19 01:28:13,238 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-11-19 01:28:13,545 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-19 01:28:13,545 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 01:28:13,552 INFO L255 TraceCheckSpWp]: Trace formula consists of 1041 conjuncts, 27 conjuncts are in the unsatisfiable core [2024-11-19 01:28:13,559 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 01:28:13,598 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 15 treesize of output 1 [2024-11-19 01:28:13,659 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 34 treesize of output 14 [2024-11-19 01:28:13,731 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 34 treesize of output 14 [2024-11-19 01:28:13,954 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 56 treesize of output 32 [2024-11-19 01:28:14,001 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 0 proven. 33 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-19 01:28:14,002 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 01:28:14,727 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 6 proven. 27 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-19 01:28:14,728 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [552521738] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 01:28:14,728 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-19 01:28:14,728 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 10, 10] total 26 [2024-11-19 01:28:14,728 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [232041829] [2024-11-19 01:28:14,729 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-19 01:28:14,729 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2024-11-19 01:28:14,730 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 01:28:14,730 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2024-11-19 01:28:14,731 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=155, Invalid=495, Unknown=0, NotChecked=0, Total=650 [2024-11-19 01:28:14,732 INFO L467 CegarLoopForPetriNet]: Number of universal loopers: 7 out of 34 [2024-11-19 01:28:14,733 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 203 places, 458 transitions, 5290 flow. Second operand has 26 states, 26 states have (on average 10.807692307692308) internal successors, (281), 26 states have internal predecessors, (281), 0 states have call successors, (0), 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-11-19 01:28:14,733 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-11-19 01:28:14,733 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 7 of 34 [2024-11-19 01:28:14,734 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-11-19 01:28:21,838 INFO L124 PetriNetUnfolderBase]: 17135/33471 cut-off events. [2024-11-19 01:28:21,838 INFO L125 PetriNetUnfolderBase]: For 123243/123243 co-relation queries the response was YES. [2024-11-19 01:28:22,177 INFO L83 FinitePrefix]: Finished finitePrefix Result has 98614 conditions, 33471 events. 17135/33471 cut-off events. For 123243/123243 co-relation queries the response was YES. Maximal size of possible extension queue 451. Compared 263245 event pairs, 3530 based on Foata normal form. 413/33532 useless extension candidates. Maximal degree in co-relation 96396. Up to 5616 conditions per place. [2024-11-19 01:28:22,300 INFO L140 encePairwiseOnDemand]: 26/34 looper letters, 392 selfloop transitions, 598 changer transitions 28/1023 dead transitions. [2024-11-19 01:28:22,300 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 237 places, 1023 transitions, 11832 flow [2024-11-19 01:28:22,301 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 35 states. [2024-11-19 01:28:22,301 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 35 states. [2024-11-19 01:28:22,302 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 600 transitions. [2024-11-19 01:28:22,303 INFO L512 CegarLoopForPetriNet]: DFA transition density 0.5042016806722689 [2024-11-19 01:28:22,303 INFO L175 Difference]: Start difference. First operand has 203 places, 458 transitions, 5290 flow. Second operand 35 states and 600 transitions. [2024-11-19 01:28:22,303 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 237 places, 1023 transitions, 11832 flow [2024-11-19 01:28:23,393 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 235 places, 1023 transitions, 10944 flow, removed 398 selfloop flow, removed 2 redundant places. [2024-11-19 01:28:23,404 INFO L231 Difference]: Finished difference. Result has 254 places, 721 transitions, 9427 flow [2024-11-19 01:28:23,405 INFO L260 CegarLoopForPetriNet]: {PETRI_ALPHABET=34, PETRI_DIFFERENCE_MINUEND_FLOW=4876, PETRI_DIFFERENCE_MINUEND_PLACES=201, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=458, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=346, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=80, PETRI_DIFFERENCE_SUBTRAHEND_STATES=35, PETRI_FLOW=9427, PETRI_PLACES=254, PETRI_TRANSITIONS=721} [2024-11-19 01:28:23,405 INFO L277 CegarLoopForPetriNet]: 32 programPoint places, 222 predicate places. [2024-11-19 01:28:23,406 INFO L471 AbstractCegarLoop]: Abstraction has has 254 places, 721 transitions, 9427 flow [2024-11-19 01:28:23,406 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 26 states have (on average 10.807692307692308) internal successors, (281), 26 states have internal predecessors, (281), 0 states have call successors, (0), 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-11-19 01:28:23,406 INFO L196 CegarLoopForPetriNet]: Found error trace [2024-11-19 01:28:23,406 INFO L204 CegarLoopForPetriNet]: trace histogram [6, 6, 6, 5, 5, 5, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 01:28:23,421 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-11-19 01:28:23,606 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 01:28:23,607 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting t1Err0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES, ULTIMATE.startErr1INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (and 4 more)] === [2024-11-19 01:28:23,607 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 01:28:23,607 INFO L85 PathProgramCache]: Analyzing trace with hash 1371966826, now seen corresponding path program 1 times [2024-11-19 01:28:23,608 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 01:28:23,608 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [721118873] [2024-11-19 01:28:23,608 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 01:28:23,608 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 01:28:23,686 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 01:28:24,510 INFO L134 CoverageAnalysis]: Checked inductivity of 86 backedges. 9 proven. 74 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2024-11-19 01:28:24,510 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 01:28:24,510 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [721118873] [2024-11-19 01:28:24,511 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [721118873] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-19 01:28:24,511 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1544154793] [2024-11-19 01:28:24,511 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 01:28:24,511 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 01:28:24,512 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 01:28:24,513 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-11-19 01:28:24,515 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-19 01:28:24,777 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 01:28:24,780 INFO L255 TraceCheckSpWp]: Trace formula consists of 1097 conjuncts, 15 conjuncts are in the unsatisfiable core [2024-11-19 01:28:24,788 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 01:28:24,813 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-11-19 01:28:24,858 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-11-19 01:28:24,905 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-11-19 01:28:24,957 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-11-19 01:28:25,008 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-11-19 01:28:25,244 INFO L134 CoverageAnalysis]: Checked inductivity of 86 backedges. 0 proven. 86 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-19 01:28:25,244 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 01:28:25,336 INFO L134 CoverageAnalysis]: Checked inductivity of 86 backedges. 45 proven. 14 refuted. 0 times theorem prover too weak. 27 trivial. 0 not checked. [2024-11-19 01:28:25,336 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1544154793] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 01:28:25,336 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-19 01:28:25,336 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 10, 6] total 22 [2024-11-19 01:28:25,336 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1314559718] [2024-11-19 01:28:25,337 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-19 01:28:25,337 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2024-11-19 01:28:25,338 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 01:28:25,338 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-11-19 01:28:25,340 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=127, Invalid=335, Unknown=0, NotChecked=0, Total=462 [2024-11-19 01:28:25,342 INFO L467 CegarLoopForPetriNet]: Number of universal loopers: 7 out of 34 [2024-11-19 01:28:25,343 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 254 places, 721 transitions, 9427 flow. Second operand has 22 states, 22 states have (on average 12.318181818181818) internal successors, (271), 22 states have internal predecessors, (271), 0 states have call successors, (0), 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-11-19 01:28:25,343 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-11-19 01:28:25,343 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 7 of 34 [2024-11-19 01:28:25,343 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-11-19 01:28:39,568 INFO L124 PetriNetUnfolderBase]: 31819/62084 cut-off events. [2024-11-19 01:28:39,568 INFO L125 PetriNetUnfolderBase]: For 437317/437317 co-relation queries the response was YES. [2024-11-19 01:28:40,592 INFO L83 FinitePrefix]: Finished finitePrefix Result has 197550 conditions, 62084 events. 31819/62084 cut-off events. For 437317/437317 co-relation queries the response was YES. Maximal size of possible extension queue 676. Compared 511214 event pairs, 4080 based on Foata normal form. 525/62600 useless extension candidates. Maximal degree in co-relation 195401. Up to 10377 conditions per place. [2024-11-19 01:28:40,812 INFO L140 encePairwiseOnDemand]: 28/34 looper letters, 665 selfloop transitions, 1260 changer transitions 30/1960 dead transitions. [2024-11-19 01:28:40,812 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 318 places, 1960 transitions, 24286 flow [2024-11-19 01:28:40,813 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 65 states. [2024-11-19 01:28:40,813 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 65 states. [2024-11-19 01:28:40,816 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 65 states to 65 states and 1142 transitions. [2024-11-19 01:28:40,816 INFO L512 CegarLoopForPetriNet]: DFA transition density 0.5167420814479639 [2024-11-19 01:28:40,817 INFO L175 Difference]: Start difference. First operand has 254 places, 721 transitions, 9427 flow. Second operand 65 states and 1142 transitions. [2024-11-19 01:28:40,817 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 318 places, 1960 transitions, 24286 flow [2024-11-19 01:28:46,226 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 317 places, 1960 transitions, 22875 flow, removed 702 selfloop flow, removed 1 redundant places. [2024-11-19 01:28:46,248 INFO L231 Difference]: Finished difference. Result has 329 places, 1387 transitions, 19826 flow [2024-11-19 01:28:46,249 INFO L260 CegarLoopForPetriNet]: {PETRI_ALPHABET=34, PETRI_DIFFERENCE_MINUEND_FLOW=8910, PETRI_DIFFERENCE_MINUEND_PLACES=253, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=721, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=634, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=87, PETRI_DIFFERENCE_SUBTRAHEND_STATES=65, PETRI_FLOW=19826, PETRI_PLACES=329, PETRI_TRANSITIONS=1387} [2024-11-19 01:28:46,250 INFO L277 CegarLoopForPetriNet]: 32 programPoint places, 297 predicate places. [2024-11-19 01:28:46,250 INFO L471 AbstractCegarLoop]: Abstraction has has 329 places, 1387 transitions, 19826 flow [2024-11-19 01:28:46,250 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 22 states have (on average 12.318181818181818) internal successors, (271), 22 states have internal predecessors, (271), 0 states have call successors, (0), 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-11-19 01:28:46,251 INFO L196 CegarLoopForPetriNet]: Found error trace [2024-11-19 01:28:46,251 INFO L204 CegarLoopForPetriNet]: trace histogram [4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 01:28:46,266 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-11-19 01:28:46,451 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 01:28:46,451 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting t2Err0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES, ULTIMATE.startErr1INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (and 4 more)] === [2024-11-19 01:28:46,452 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 01:28:46,452 INFO L85 PathProgramCache]: Analyzing trace with hash -502864770, now seen corresponding path program 3 times [2024-11-19 01:28:46,453 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 01:28:46,453 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2065107367] [2024-11-19 01:28:46,453 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-19 01:28:46,453 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 01:28:46,796 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2024-11-19 01:28:46,796 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 01:28:48,913 INFO L134 CoverageAnalysis]: Checked inductivity of 69 backedges. 30 proven. 39 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-19 01:28:48,914 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 01:28:48,914 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2065107367] [2024-11-19 01:28:48,914 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2065107367] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-19 01:28:48,914 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [698574830] [2024-11-19 01:28:48,914 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-19 01:28:48,914 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 01:28:48,914 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 01:28:48,915 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 01:28:48,916 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-11-19 01:28:49,228 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2024-11-19 01:28:49,228 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 01:28:49,233 INFO L255 TraceCheckSpWp]: Trace formula consists of 1093 conjuncts, 30 conjuncts are in the unsatisfiable core [2024-11-19 01:28:49,239 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 01:28:49,261 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 15 treesize of output 1 [2024-11-19 01:28:49,308 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 34 treesize of output 14 [2024-11-19 01:28:49,355 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 34 treesize of output 14 [2024-11-19 01:28:49,405 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 34 treesize of output 14 [2024-11-19 01:28:49,754 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-19 01:28:49,754 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 74 treesize of output 38 [2024-11-19 01:28:49,790 INFO L134 CoverageAnalysis]: Checked inductivity of 69 backedges. 0 proven. 69 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-19 01:28:49,790 INFO L311 TraceCheckSpWp]: Computing backward predicates...