./Ultimate.py --spec ../sv-benchmarks/c/properties/no-overflow.prp --file ../sv-benchmarks/c/pthread/queue_ok_longest.i --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for overflows Using default analysis Version c7c6ca5d 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/queue_ok_longest.i -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Overflow-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 ! overflow) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 0e9bc4a9a6dcd238ac18925269a0bd7c8c54c2dafb57744151e37b58cf6eab8d --- Real Ultimate output --- This is Ultimate 0.2.5-?-c7c6ca5-m [2024-11-09 14:52:47,033 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-09 14:52:47,100 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Overflow-32bit-Automizer_Default.epf [2024-11-09 14:52:47,103 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-09 14:52:47,104 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-09 14:52:47,119 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-09 14:52:47,119 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-09 14:52:47,120 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-09 14:52:47,120 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-09 14:52:47,121 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-09 14:52:47,121 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-09 14:52:47,121 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-09 14:52:47,125 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-09 14:52:47,125 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-09 14:52:47,125 INFO L153 SettingsManager]: * Use SBE=true [2024-11-09 14:52:47,125 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-09 14:52:47,126 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-09 14:52:47,126 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-09 14:52:47,126 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-09 14:52:47,126 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-09 14:52:47,127 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-09 14:52:47,127 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-09 14:52:47,127 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-09 14:52:47,128 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-09 14:52:47,128 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-09 14:52:47,128 INFO L153 SettingsManager]: * Check absence of signed integer overflows=ASSERTandASSUME [2024-11-09 14:52:47,128 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2024-11-09 14:52:47,129 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-09 14:52:47,129 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-09 14:52:47,129 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-09 14:52:47,129 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-09 14:52:47,130 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-09 14:52:47,130 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-09 14:52:47,130 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-09 14:52:47,130 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-09 14:52:47,131 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-09 14:52:47,131 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-09 14:52:47,131 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-09 14:52:47,131 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-09 14:52:47,132 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-09 14:52:47,132 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-09 14:52:47,132 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-09 14:52:47,132 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-09 14:52:47,133 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-09 14:52:47,133 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 ! overflow) ) 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 -> 0e9bc4a9a6dcd238ac18925269a0bd7c8c54c2dafb57744151e37b58cf6eab8d [2024-11-09 14:52:47,327 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-09 14:52:47,348 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-09 14:52:47,351 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-09 14:52:47,352 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-09 14:52:47,353 INFO L274 PluginConnector]: CDTParser initialized [2024-11-09 14:52:47,354 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/pthread/queue_ok_longest.i [2024-11-09 14:52:48,721 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-09 14:52:48,923 INFO L384 CDTParser]: Found 1 translation units. [2024-11-09 14:52:48,923 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/pthread/queue_ok_longest.i [2024-11-09 14:52:48,939 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/0d50839a7/1a42868c31074ff187edbb374b16a344/FLAG465b79f57 [2024-11-09 14:52:48,954 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/0d50839a7/1a42868c31074ff187edbb374b16a344 [2024-11-09 14:52:48,957 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-09 14:52:48,958 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-09 14:52:48,959 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-09 14:52:48,959 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-09 14:52:48,966 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-09 14:52:48,967 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 02:52:48" (1/1) ... [2024-11-09 14:52:48,969 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@31438742 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 02:52:48, skipping insertion in model container [2024-11-09 14:52:48,970 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 02:52:48" (1/1) ... [2024-11-09 14:52:49,008 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-09 14:52:49,406 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 14:52:49,451 INFO L200 MainTranslator]: Completed pre-run [2024-11-09 14:52:49,502 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 14:52:49,615 INFO L204 MainTranslator]: Completed translation [2024-11-09 14:52:49,615 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 02:52:49 WrapperNode [2024-11-09 14:52:49,616 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-09 14:52:49,617 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-09 14:52:49,617 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-09 14:52:49,617 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-09 14:52:49,622 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 02:52:49" (1/1) ... [2024-11-09 14:52:49,659 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 02:52:49" (1/1) ... [2024-11-09 14:52:49,733 INFO L138 Inliner]: procedures = 274, calls = 1654, calls flagged for inlining = 9, calls inlined = 9, statements flattened = 1813 [2024-11-09 14:52:49,735 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-09 14:52:49,736 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-09 14:52:49,736 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-09 14:52:49,736 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-09 14:52:49,744 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 02:52:49" (1/1) ... [2024-11-09 14:52:49,745 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 02:52:49" (1/1) ... [2024-11-09 14:52:49,759 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 02:52:49" (1/1) ... [2024-11-09 14:52:49,801 INFO L175 MemorySlicer]: Split 1635 memory accesses to 4 slices as follows [2, 5, 826, 802]. 51 percent of accesses are in the largest equivalence class. The 1610 initializations are split as follows [2, 5, 803, 800]. The 11 writes are split as follows [0, 0, 10, 1]. [2024-11-09 14:52:49,802 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 02:52:49" (1/1) ... [2024-11-09 14:52:49,803 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 02:52:49" (1/1) ... [2024-11-09 14:52:49,904 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 02:52:49" (1/1) ... [2024-11-09 14:52:49,916 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 02:52:49" (1/1) ... [2024-11-09 14:52:49,930 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 02:52:49" (1/1) ... [2024-11-09 14:52:49,942 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 02:52:49" (1/1) ... [2024-11-09 14:52:49,982 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-09 14:52:49,987 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-09 14:52:49,987 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-09 14:52:49,987 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-09 14:52:49,988 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 02:52:49" (1/1) ... [2024-11-09 14:52:49,999 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-09 14:52:50,007 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 14:52:50,026 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-09 14:52:50,032 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-09 14:52:50,066 INFO L130 BoogieDeclarations]: Found specification of procedure t1 [2024-11-09 14:52:50,067 INFO L138 BoogieDeclarations]: Found implementation of procedure t1 [2024-11-09 14:52:50,067 INFO L130 BoogieDeclarations]: Found specification of procedure t2 [2024-11-09 14:52:50,067 INFO L138 BoogieDeclarations]: Found implementation of procedure t2 [2024-11-09 14:52:50,067 INFO L130 BoogieDeclarations]: Found specification of procedure #PthreadsMutexUnlock [2024-11-09 14:52:50,067 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2024-11-09 14:52:50,067 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2024-11-09 14:52:50,067 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#2 [2024-11-09 14:52:50,067 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#3 [2024-11-09 14:52:50,067 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2024-11-09 14:52:50,067 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2024-11-09 14:52:50,067 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#2 [2024-11-09 14:52:50,067 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#3 [2024-11-09 14:52:50,067 INFO L130 BoogieDeclarations]: Found specification of procedure #PthreadsMutexLock [2024-11-09 14:52:50,067 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-09 14:52:50,067 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-09 14:52:50,068 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2024-11-09 14:52:50,068 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2024-11-09 14:52:50,068 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#3 [2024-11-09 14:52:50,068 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-09 14:52:50,068 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-09 14:52:50,074 WARN L207 CfgBuilder]: User set CodeBlockSize to SequenceOfStatements but program contains fork statements. Overwriting the user preferences and setting CodeBlockSize to OneNontrivialStatement. [2024-11-09 14:52:50,296 INFO L238 CfgBuilder]: Building ICFG [2024-11-09 14:52:50,297 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-09 14:52:51,697 INFO L283 CfgBuilder]: Omitted future-live optimization because the input is a concurrent program. [2024-11-09 14:52:51,697 INFO L287 CfgBuilder]: Performing block encoding [2024-11-09 14:53:21,621 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-09 14:53:21,621 INFO L316 CfgBuilder]: Removed 2 assume(true) statements. [2024-11-09 14:53:21,622 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.11 02:53:21 BoogieIcfgContainer [2024-11-09 14:53:21,622 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-09 14:53:21,623 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-09 14:53:21,623 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-09 14:53:21,626 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-09 14:53:21,626 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 09.11 02:52:48" (1/3) ... [2024-11-09 14:53:21,626 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@40ff6cd7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.11 02:53:21, skipping insertion in model container [2024-11-09 14:53:21,626 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 02:52:49" (2/3) ... [2024-11-09 14:53:21,626 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@40ff6cd7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.11 02:53:21, skipping insertion in model container [2024-11-09 14:53:21,627 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.11 02:53:21" (3/3) ... [2024-11-09 14:53:21,627 INFO L112 eAbstractionObserver]: Analyzing ICFG queue_ok_longest.i [2024-11-09 14:53:21,640 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-09 14:53:21,640 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 12 error locations. [2024-11-09 14:53:21,640 INFO L489 ceAbstractionStarter]: Constructing petrified ICFG for 1 thread instances. [2024-11-09 14:53:21,714 INFO L143 ThreadInstanceAdder]: Constructed 2 joinOtherThreadTransitions. [2024-11-09 14:53:21,749 INFO L73 FinitePrefix]: Start finitePrefix. Operand has 61 places, 61 transitions, 136 flow [2024-11-09 14:53:21,856 INFO L124 PetriNetUnfolderBase]: 7/59 cut-off events. [2024-11-09 14:53:21,857 INFO L125 PetriNetUnfolderBase]: For 2/2 co-relation queries the response was YES. [2024-11-09 14:53:21,860 INFO L83 FinitePrefix]: Finished finitePrefix Result has 68 conditions, 59 events. 7/59 cut-off events. For 2/2 co-relation queries the response was YES. Maximal size of possible extension queue 9. Compared 173 event pairs, 0 based on Foata normal form. 0/40 useless extension candidates. Maximal degree in co-relation 56. Up to 2 conditions per place. [2024-11-09 14:53:21,860 INFO L82 GeneralOperation]: Start removeDead. Operand has 61 places, 61 transitions, 136 flow [2024-11-09 14:53:21,864 INFO L88 GeneralOperation]: Finished RemoveDead, result has has 57 places, 57 transitions, 123 flow [2024-11-09 14:53:21,871 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-09 14:53:21,878 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;@73814804, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-09 14:53:21,879 INFO L334 AbstractCegarLoop]: Starting to check reachability of 26 error locations. [2024-11-09 14:53:21,928 INFO L185 PetriNetUnfolderBase]: Found word, exiting Unfolder. [2024-11-09 14:53:21,929 INFO L124 PetriNetUnfolderBase]: 2/20 cut-off events. [2024-11-09 14:53:21,929 INFO L125 PetriNetUnfolderBase]: For 1/1 co-relation queries the response was YES. [2024-11-09 14:53:21,929 INFO L196 CegarLoopForPetriNet]: Found error trace [2024-11-09 14:53:21,929 INFO L204 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 14:53:21,930 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting t1Err0ASSERT_VIOLATIONINTEGER_OVERFLOW === [ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES, ULTIMATE.startErr1INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (and 24 more)] === [2024-11-09 14:53:21,934 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 14:53:21,934 INFO L85 PathProgramCache]: Analyzing trace with hash 1319946339, now seen corresponding path program 1 times [2024-11-09 14:53:21,942 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 14:53:21,942 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [925779612] [2024-11-09 14:53:21,942 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 14:53:21,942 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 14:53:22,426 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 14:53:23,959 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-09 14:53:23,960 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 14:53:23,960 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [925779612] [2024-11-09 14:53:23,960 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [925779612] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 14:53:23,961 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 14:53:23,961 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-09 14:53:23,962 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [397466152] [2024-11-09 14:53:23,963 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 14:53:23,968 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-09 14:53:23,973 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 14:53:23,994 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-09 14:53:23,994 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-09 14:53:24,002 INFO L467 CegarLoopForPetriNet]: Number of universal loopers: 23 out of 61 [2024-11-09 14:53:24,004 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 57 places, 57 transitions, 123 flow. Second operand has 4 states, 4 states have (on average 24.75) internal successors, (99), 4 states have internal predecessors, (99), 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-09 14:53:24,005 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-11-09 14:53:24,005 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 23 of 61 [2024-11-09 14:53:24,006 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-11-09 14:53:24,708 INFO L124 PetriNetUnfolderBase]: 1022/2058 cut-off events. [2024-11-09 14:53:24,709 INFO L125 PetriNetUnfolderBase]: For 58/58 co-relation queries the response was YES. [2024-11-09 14:53:24,712 INFO L83 FinitePrefix]: Finished finitePrefix Result has 3706 conditions, 2058 events. 1022/2058 cut-off events. For 58/58 co-relation queries the response was YES. Maximal size of possible extension queue 126. Compared 13221 event pairs, 209 based on Foata normal form. 28/1694 useless extension candidates. Maximal degree in co-relation 3564. Up to 1033 conditions per place. [2024-11-09 14:53:24,720 INFO L140 encePairwiseOnDemand]: 55/61 looper letters, 73 selfloop transitions, 5 changer transitions 0/99 dead transitions. [2024-11-09 14:53:24,721 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 60 places, 99 transitions, 372 flow [2024-11-09 14:53:24,723 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-09 14:53:24,725 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 4 states. [2024-11-09 14:53:24,732 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 171 transitions. [2024-11-09 14:53:24,734 INFO L512 CegarLoopForPetriNet]: DFA transition density 0.7008196721311475 [2024-11-09 14:53:24,736 INFO L175 Difference]: Start difference. First operand has 57 places, 57 transitions, 123 flow. Second operand 4 states and 171 transitions. [2024-11-09 14:53:24,736 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 60 places, 99 transitions, 372 flow [2024-11-09 14:53:24,739 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 57 places, 99 transitions, 363 flow, removed 0 selfloop flow, removed 3 redundant places. [2024-11-09 14:53:24,742 INFO L231 Difference]: Finished difference. Result has 60 places, 61 transitions, 156 flow [2024-11-09 14:53:24,746 INFO L260 CegarLoopForPetriNet]: {PETRI_ALPHABET=61, PETRI_DIFFERENCE_MINUEND_FLOW=118, PETRI_DIFFERENCE_MINUEND_PLACES=54, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=57, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=1, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=52, PETRI_DIFFERENCE_SUBTRAHEND_STATES=4, PETRI_FLOW=156, PETRI_PLACES=60, PETRI_TRANSITIONS=61} [2024-11-09 14:53:24,748 INFO L277 CegarLoopForPetriNet]: 57 programPoint places, 3 predicate places. [2024-11-09 14:53:24,750 INFO L471 AbstractCegarLoop]: Abstraction has has 60 places, 61 transitions, 156 flow [2024-11-09 14:53:24,751 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 24.75) internal successors, (99), 4 states have internal predecessors, (99), 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-09 14:53:24,751 INFO L196 CegarLoopForPetriNet]: Found error trace [2024-11-09 14:53:24,751 INFO L204 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 14:53:24,752 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-09 14:53:24,752 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting t1Err1ASSERT_VIOLATIONINTEGER_OVERFLOW === [ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES, ULTIMATE.startErr1INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (and 24 more)] === [2024-11-09 14:53:24,753 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 14:53:24,753 INFO L85 PathProgramCache]: Analyzing trace with hash -2031332627, now seen corresponding path program 1 times [2024-11-09 14:53:24,753 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 14:53:24,754 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1800794002] [2024-11-09 14:53:24,754 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 14:53:24,754 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 14:53:24,879 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 14:53:25,974 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-09 14:53:25,974 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 14:53:25,974 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1800794002] [2024-11-09 14:53:25,974 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1800794002] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 14:53:25,974 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 14:53:25,975 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-09 14:53:25,975 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1303910040] [2024-11-09 14:53:25,975 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 14:53:25,976 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-09 14:53:25,976 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 14:53:25,976 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-09 14:53:25,976 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-09 14:53:25,980 INFO L467 CegarLoopForPetriNet]: Number of universal loopers: 23 out of 61 [2024-11-09 14:53:25,980 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 60 places, 61 transitions, 156 flow. Second operand has 4 states, 4 states have (on average 24.75) internal successors, (99), 4 states have internal predecessors, (99), 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-09 14:53:25,980 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-11-09 14:53:25,981 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 23 of 61 [2024-11-09 14:53:25,981 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-11-09 14:53:26,525 INFO L124 PetriNetUnfolderBase]: 1017/2063 cut-off events. [2024-11-09 14:53:26,525 INFO L125 PetriNetUnfolderBase]: For 425/429 co-relation queries the response was YES. [2024-11-09 14:53:26,528 INFO L83 FinitePrefix]: Finished finitePrefix Result has 4026 conditions, 2063 events. 1017/2063 cut-off events. For 425/429 co-relation queries the response was YES. Maximal size of possible extension queue 126. Compared 13211 event pairs, 213 based on Foata normal form. 46/1819 useless extension candidates. Maximal degree in co-relation 3538. Up to 1122 conditions per place. [2024-11-09 14:53:26,534 INFO L140 encePairwiseOnDemand]: 56/61 looper letters, 81 selfloop transitions, 6 changer transitions 0/108 dead transitions. [2024-11-09 14:53:26,534 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 64 places, 108 transitions, 435 flow [2024-11-09 14:53:26,535 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-09 14:53:26,535 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 5 states. [2024-11-09 14:53:26,536 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 204 transitions. [2024-11-09 14:53:26,536 INFO L512 CegarLoopForPetriNet]: DFA transition density 0.6688524590163935 [2024-11-09 14:53:26,536 INFO L175 Difference]: Start difference. First operand has 60 places, 61 transitions, 156 flow. Second operand 5 states and 204 transitions. [2024-11-09 14:53:26,536 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 64 places, 108 transitions, 435 flow [2024-11-09 14:53:26,538 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 63 places, 108 transitions, 430 flow, removed 0 selfloop flow, removed 1 redundant places. [2024-11-09 14:53:26,539 INFO L231 Difference]: Finished difference. Result has 64 places, 62 transitions, 174 flow [2024-11-09 14:53:26,540 INFO L260 CegarLoopForPetriNet]: {PETRI_ALPHABET=61, PETRI_DIFFERENCE_MINUEND_FLOW=148, PETRI_DIFFERENCE_MINUEND_PLACES=59, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=60, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=4, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=55, PETRI_DIFFERENCE_SUBTRAHEND_STATES=5, PETRI_FLOW=174, PETRI_PLACES=64, PETRI_TRANSITIONS=62} [2024-11-09 14:53:26,540 INFO L277 CegarLoopForPetriNet]: 57 programPoint places, 7 predicate places. [2024-11-09 14:53:26,540 INFO L471 AbstractCegarLoop]: Abstraction has has 64 places, 62 transitions, 174 flow [2024-11-09 14:53:26,540 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 24.75) internal successors, (99), 4 states have internal predecessors, (99), 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-09 14:53:26,541 INFO L196 CegarLoopForPetriNet]: Found error trace [2024-11-09 14:53:26,541 INFO L204 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 14:53:26,541 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-09 14:53:26,541 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting t2Err0ASSERT_VIOLATIONINTEGER_OVERFLOW === [ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES, ULTIMATE.startErr1INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (and 24 more)] === [2024-11-09 14:53:26,541 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 14:53:26,542 INFO L85 PathProgramCache]: Analyzing trace with hash 1119146303, now seen corresponding path program 1 times [2024-11-09 14:53:26,542 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 14:53:26,542 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1173472245] [2024-11-09 14:53:26,542 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 14:53:26,542 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 14:53:26,597 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 14:53:27,186 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-09 14:53:27,186 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 14:53:27,186 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1173472245] [2024-11-09 14:53:27,186 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1173472245] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 14:53:27,186 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 14:53:27,186 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-09 14:53:27,187 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1336097806] [2024-11-09 14:53:27,187 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 14:53:27,187 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-09 14:53:27,187 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 14:53:27,188 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-09 14:53:27,188 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-09 14:53:27,190 INFO L467 CegarLoopForPetriNet]: Number of universal loopers: 25 out of 61 [2024-11-09 14:53:27,190 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 64 places, 62 transitions, 174 flow. Second operand has 3 states, 3 states have (on average 28.0) internal successors, (84), 3 states have internal predecessors, (84), 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-09 14:53:27,190 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-11-09 14:53:27,191 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 25 of 61 [2024-11-09 14:53:27,191 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-11-09 14:53:27,452 INFO L124 PetriNetUnfolderBase]: 473/1087 cut-off events. [2024-11-09 14:53:27,452 INFO L125 PetriNetUnfolderBase]: For 225/225 co-relation queries the response was YES. [2024-11-09 14:53:27,454 INFO L83 FinitePrefix]: Finished finitePrefix Result has 2126 conditions, 1087 events. 473/1087 cut-off events. For 225/225 co-relation queries the response was YES. Maximal size of possible extension queue 57. Compared 6373 event pairs, 266 based on Foata normal form. 27/998 useless extension candidates. Maximal degree in co-relation 1822. Up to 444 conditions per place. [2024-11-09 14:53:27,457 INFO L140 encePairwiseOnDemand]: 57/61 looper letters, 39 selfloop transitions, 2 changer transitions 6/70 dead transitions. [2024-11-09 14:53:27,457 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 65 places, 70 transitions, 277 flow [2024-11-09 14:53:27,457 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-09 14:53:27,457 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3 states. [2024-11-09 14:53:27,458 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 120 transitions. [2024-11-09 14:53:27,458 INFO L512 CegarLoopForPetriNet]: DFA transition density 0.6557377049180327 [2024-11-09 14:53:27,458 INFO L175 Difference]: Start difference. First operand has 64 places, 62 transitions, 174 flow. Second operand 3 states and 120 transitions. [2024-11-09 14:53:27,458 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 65 places, 70 transitions, 277 flow [2024-11-09 14:53:27,459 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 61 places, 70 transitions, 264 flow, removed 1 selfloop flow, removed 4 redundant places. [2024-11-09 14:53:27,460 INFO L231 Difference]: Finished difference. Result has 62 places, 59 transitions, 153 flow [2024-11-09 14:53:27,461 INFO L260 CegarLoopForPetriNet]: {PETRI_ALPHABET=61, PETRI_DIFFERENCE_MINUEND_FLOW=147, PETRI_DIFFERENCE_MINUEND_PLACES=59, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=60, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=2, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=58, PETRI_DIFFERENCE_SUBTRAHEND_STATES=3, PETRI_FLOW=153, PETRI_PLACES=62, PETRI_TRANSITIONS=59} [2024-11-09 14:53:27,461 INFO L277 CegarLoopForPetriNet]: 57 programPoint places, 5 predicate places. [2024-11-09 14:53:27,461 INFO L471 AbstractCegarLoop]: Abstraction has has 62 places, 59 transitions, 153 flow [2024-11-09 14:53:27,462 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 28.0) internal successors, (84), 3 states have internal predecessors, (84), 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-09 14:53:27,462 INFO L196 CegarLoopForPetriNet]: Found error trace [2024-11-09 14:53:27,462 INFO L204 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 14:53:27,462 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2024-11-09 14:53:27,462 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting t1Err2ASSERT_VIOLATIONINTEGER_OVERFLOW === [ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES, ULTIMATE.startErr1INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (and 24 more)] === [2024-11-09 14:53:27,463 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 14:53:27,463 INFO L85 PathProgramCache]: Analyzing trace with hash 2099587536, now seen corresponding path program 1 times [2024-11-09 14:53:27,463 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 14:53:27,463 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1906979015] [2024-11-09 14:53:27,463 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 14:53:27,463 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 14:53:27,606 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 14:53:28,823 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-09 14:53:28,823 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 14:53:28,823 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1906979015] [2024-11-09 14:53:28,823 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1906979015] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 14:53:28,824 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 14:53:28,824 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-09 14:53:28,824 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1987900768] [2024-11-09 14:53:28,824 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 14:53:28,824 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-09 14:53:28,824 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 14:53:28,825 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-09 14:53:28,825 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-09 14:53:28,831 INFO L467 CegarLoopForPetriNet]: Number of universal loopers: 23 out of 61 [2024-11-09 14:53:28,832 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 62 places, 59 transitions, 153 flow. Second operand has 5 states, 5 states have (on average 24.8) internal successors, (124), 5 states have internal predecessors, (124), 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-09 14:53:28,832 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-11-09 14:53:28,832 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 23 of 61 [2024-11-09 14:53:28,832 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-11-09 14:53:29,490 INFO L124 PetriNetUnfolderBase]: 505/1127 cut-off events. [2024-11-09 14:53:29,491 INFO L125 PetriNetUnfolderBase]: For 112/112 co-relation queries the response was YES. [2024-11-09 14:53:29,492 INFO L83 FinitePrefix]: Finished finitePrefix Result has 2224 conditions, 1127 events. 505/1127 cut-off events. For 112/112 co-relation queries the response was YES. Maximal size of possible extension queue 59. Compared 6475 event pairs, 179 based on Foata normal form. 12/1025 useless extension candidates. Maximal degree in co-relation 1878. Up to 476 conditions per place. [2024-11-09 14:53:29,495 INFO L140 encePairwiseOnDemand]: 52/61 looper letters, 71 selfloop transitions, 7 changer transitions 0/99 dead transitions. [2024-11-09 14:53:29,495 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 67 places, 99 transitions, 403 flow [2024-11-09 14:53:29,495 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-09 14:53:29,495 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 6 states. [2024-11-09 14:53:29,496 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 218 transitions. [2024-11-09 14:53:29,496 INFO L512 CegarLoopForPetriNet]: DFA transition density 0.5956284153005464 [2024-11-09 14:53:29,496 INFO L175 Difference]: Start difference. First operand has 62 places, 59 transitions, 153 flow. Second operand 6 states and 218 transitions. [2024-11-09 14:53:29,496 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 67 places, 99 transitions, 403 flow [2024-11-09 14:53:29,497 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 65 places, 99 transitions, 397 flow, removed 0 selfloop flow, removed 2 redundant places. [2024-11-09 14:53:29,498 INFO L231 Difference]: Finished difference. Result has 67 places, 62 transitions, 184 flow [2024-11-09 14:53:29,498 INFO L260 CegarLoopForPetriNet]: {PETRI_ALPHABET=61, PETRI_DIFFERENCE_MINUEND_FLOW=149, PETRI_DIFFERENCE_MINUEND_PLACES=60, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=59, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=4, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=52, PETRI_DIFFERENCE_SUBTRAHEND_STATES=6, PETRI_FLOW=184, PETRI_PLACES=67, PETRI_TRANSITIONS=62} [2024-11-09 14:53:29,499 INFO L277 CegarLoopForPetriNet]: 57 programPoint places, 10 predicate places. [2024-11-09 14:53:29,499 INFO L471 AbstractCegarLoop]: Abstraction has has 67 places, 62 transitions, 184 flow [2024-11-09 14:53:29,499 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 24.8) internal successors, (124), 5 states have internal predecessors, (124), 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-09 14:53:29,499 INFO L196 CegarLoopForPetriNet]: Found error trace [2024-11-09 14:53:29,499 INFO L204 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 14:53:29,499 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2024-11-09 14:53:29,500 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting t1Err4ASSERT_VIOLATIONINTEGER_OVERFLOW === [ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES, ULTIMATE.startErr1INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (and 24 more)] === [2024-11-09 14:53:29,500 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 14:53:29,500 INFO L85 PathProgramCache]: Analyzing trace with hash 662709001, now seen corresponding path program 1 times [2024-11-09 14:53:29,500 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 14:53:29,500 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2089561685] [2024-11-09 14:53:29,500 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 14:53:29,501 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 14:53:29,550 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 14:53:29,699 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-09 14:53:29,699 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 14:53:29,700 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2089561685] [2024-11-09 14:53:29,700 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2089561685] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 14:53:29,700 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 14:53:29,700 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-09 14:53:29,700 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [302448752] [2024-11-09 14:53:29,700 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 14:53:29,701 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-09 14:53:29,701 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 14:53:29,701 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-09 14:53:29,701 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-09 14:53:29,704 INFO L467 CegarLoopForPetriNet]: Number of universal loopers: 23 out of 61 [2024-11-09 14:53:29,705 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 67 places, 62 transitions, 184 flow. Second operand has 4 states, 4 states have (on average 25.5) internal successors, (102), 4 states have internal predecessors, (102), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 14:53:29,705 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-11-09 14:53:29,705 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 23 of 61 [2024-11-09 14:53:29,705 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-11-09 14:53:30,166 INFO L124 PetriNetUnfolderBase]: 440/980 cut-off events. [2024-11-09 14:53:30,166 INFO L125 PetriNetUnfolderBase]: For 185/185 co-relation queries the response was YES. [2024-11-09 14:53:30,168 INFO L83 FinitePrefix]: Finished finitePrefix Result has 2066 conditions, 980 events. 440/980 cut-off events. For 185/185 co-relation queries the response was YES. Maximal size of possible extension queue 47. Compared 5189 event pairs, 293 based on Foata normal form. 24/933 useless extension candidates. Maximal degree in co-relation 1833. Up to 591 conditions per place. [2024-11-09 14:53:30,170 INFO L140 encePairwiseOnDemand]: 55/61 looper letters, 53 selfloop transitions, 3 changer transitions 0/77 dead transitions. [2024-11-09 14:53:30,170 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 70 places, 77 transitions, 325 flow [2024-11-09 14:53:30,171 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-09 14:53:30,171 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 4 states. [2024-11-09 14:53:30,172 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 151 transitions. [2024-11-09 14:53:30,172 INFO L512 CegarLoopForPetriNet]: DFA transition density 0.6188524590163934 [2024-11-09 14:53:30,172 INFO L175 Difference]: Start difference. First operand has 67 places, 62 transitions, 184 flow. Second operand 4 states and 151 transitions. [2024-11-09 14:53:30,172 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 70 places, 77 transitions, 325 flow [2024-11-09 14:53:30,173 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 67 places, 77 transitions, 316 flow, removed 1 selfloop flow, removed 3 redundant places. [2024-11-09 14:53:30,174 INFO L231 Difference]: Finished difference. Result has 69 places, 63 transitions, 192 flow [2024-11-09 14:53:30,174 INFO L260 CegarLoopForPetriNet]: {PETRI_ALPHABET=61, PETRI_DIFFERENCE_MINUEND_FLOW=168, PETRI_DIFFERENCE_MINUEND_PLACES=64, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=61, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=1, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=58, PETRI_DIFFERENCE_SUBTRAHEND_STATES=4, PETRI_FLOW=192, PETRI_PLACES=69, PETRI_TRANSITIONS=63} [2024-11-09 14:53:30,175 INFO L277 CegarLoopForPetriNet]: 57 programPoint places, 12 predicate places. [2024-11-09 14:53:30,175 INFO L471 AbstractCegarLoop]: Abstraction has has 69 places, 63 transitions, 192 flow [2024-11-09 14:53:30,175 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 25.5) internal successors, (102), 4 states have internal predecessors, (102), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 14:53:30,175 INFO L196 CegarLoopForPetriNet]: Found error trace [2024-11-09 14:53:30,176 INFO L204 CegarLoopForPetriNet]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 14:53:30,176 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4 [2024-11-09 14:53:30,176 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting t1Err0ASSERT_VIOLATIONINTEGER_OVERFLOW === [ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES, ULTIMATE.startErr1INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (and 24 more)] === [2024-11-09 14:53:30,177 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 14:53:30,177 INFO L85 PathProgramCache]: Analyzing trace with hash -1197003306, now seen corresponding path program 1 times [2024-11-09 14:53:30,178 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 14:53:30,178 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [171113330] [2024-11-09 14:53:30,178 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 14:53:30,178 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 14:53:30,507 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 14:53:31,721 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 14:53:31,723 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 14:53:31,723 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [171113330] [2024-11-09 14:53:31,724 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [171113330] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 14:53:31,724 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 14:53:31,724 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-09 14:53:31,724 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [274726392] [2024-11-09 14:53:31,724 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 14:53:31,724 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-09 14:53:31,724 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 14:53:31,725 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-09 14:53:31,725 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2024-11-09 14:53:31,725 INFO L467 CegarLoopForPetriNet]: Number of universal loopers: 25 out of 61 [2024-11-09 14:53:31,725 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 69 places, 63 transitions, 192 flow. Second operand has 5 states, 5 states have (on average 27.2) internal successors, (136), 5 states have internal predecessors, (136), 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-09 14:53:31,725 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-11-09 14:53:31,725 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 25 of 61 [2024-11-09 14:53:31,726 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-11-09 14:53:32,198 INFO L124 PetriNetUnfolderBase]: 398/938 cut-off events. [2024-11-09 14:53:32,199 INFO L125 PetriNetUnfolderBase]: For 199/199 co-relation queries the response was YES. [2024-11-09 14:53:32,200 INFO L83 FinitePrefix]: Finished finitePrefix Result has 2020 conditions, 938 events. 398/938 cut-off events. For 199/199 co-relation queries the response was YES. Maximal size of possible extension queue 47. Compared 5013 event pairs, 118 based on Foata normal form. 12/895 useless extension candidates. Maximal degree in co-relation 1667. Up to 457 conditions per place. [2024-11-09 14:53:32,203 INFO L140 encePairwiseOnDemand]: 55/61 looper letters, 55 selfloop transitions, 5 changer transitions 3/86 dead transitions. [2024-11-09 14:53:32,203 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 73 places, 86 transitions, 369 flow [2024-11-09 14:53:32,203 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-09 14:53:32,203 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 5 states. [2024-11-09 14:53:32,204 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 187 transitions. [2024-11-09 14:53:32,204 INFO L512 CegarLoopForPetriNet]: DFA transition density 0.6131147540983607 [2024-11-09 14:53:32,204 INFO L175 Difference]: Start difference. First operand has 69 places, 63 transitions, 192 flow. Second operand 5 states and 187 transitions. [2024-11-09 14:53:32,204 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 73 places, 86 transitions, 369 flow [2024-11-09 14:53:32,206 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 72 places, 86 transitions, 367 flow, removed 0 selfloop flow, removed 1 redundant places. [2024-11-09 14:53:32,207 INFO L231 Difference]: Finished difference. Result has 72 places, 62 transitions, 196 flow [2024-11-09 14:53:32,207 INFO L260 CegarLoopForPetriNet]: {PETRI_ALPHABET=61, PETRI_DIFFERENCE_MINUEND_FLOW=186, PETRI_DIFFERENCE_MINUEND_PLACES=68, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=62, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=5, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=57, PETRI_DIFFERENCE_SUBTRAHEND_STATES=5, PETRI_FLOW=196, PETRI_PLACES=72, PETRI_TRANSITIONS=62} [2024-11-09 14:53:32,207 INFO L277 CegarLoopForPetriNet]: 57 programPoint places, 15 predicate places. [2024-11-09 14:53:32,208 INFO L471 AbstractCegarLoop]: Abstraction has has 72 places, 62 transitions, 196 flow [2024-11-09 14:53:32,208 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 27.2) internal successors, (136), 5 states have internal predecessors, (136), 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-09 14:53:32,208 INFO L196 CegarLoopForPetriNet]: Found error trace [2024-11-09 14:53:32,208 INFO L204 CegarLoopForPetriNet]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 14:53:32,208 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5 [2024-11-09 14:53:32,208 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting t1Err0ASSERT_VIOLATIONINTEGER_OVERFLOW === [ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES, ULTIMATE.startErr1INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (and 24 more)] === [2024-11-09 14:53:32,209 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 14:53:32,209 INFO L85 PathProgramCache]: Analyzing trace with hash -1961473644, now seen corresponding path program 1 times [2024-11-09 14:53:32,209 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 14:53:32,209 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1580354120] [2024-11-09 14:53:32,209 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 14:53:32,209 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 14:53:32,308 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 14:53:35,121 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 14:53:35,122 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 14:53:35,122 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1580354120] [2024-11-09 14:53:35,122 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1580354120] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 14:53:35,122 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1300799847] [2024-11-09 14:53:35,122 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 14:53:35,122 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 14:53:35,122 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 14:53:35,127 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-09 14:53:35,130 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-09 14:53:35,581 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 14:53:35,594 INFO L255 TraceCheckSpWp]: Trace formula consists of 3391 conjuncts, 32 conjuncts are in the unsatisfiable core [2024-11-09 14:53:35,600 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 14:53:35,728 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 19 treesize of output 1 [2024-11-09 14:53:35,815 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 31 treesize of output 15 [2024-11-09 14:53:35,896 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 34 treesize of output 28 [2024-11-09 14:53:35,906 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-09 14:53:35,906 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 38 treesize of output 22 [2024-11-09 14:53:35,945 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 14:53:35,945 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 14:53:36,155 INFO L349 Elim1Store]: treesize reduction 45, result has 53.6 percent of original size [2024-11-09 14:53:36,155 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 2 new quantified variables, introduced 3 case distinctions, treesize of input 196 treesize of output 181 [2024-11-09 14:53:36,173 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-09 14:53:36,173 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 148 treesize of output 142 [2024-11-09 14:53:36,235 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 9 treesize of output 5 [2024-11-09 14:53:36,265 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-09 14:53:36,265 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 179 treesize of output 175 [2024-11-09 14:53:36,521 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 14:53:36,522 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1300799847] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 14:53:36,522 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 14:53:36,522 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 6] total 18 [2024-11-09 14:53:36,522 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [580173742] [2024-11-09 14:53:36,522 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 14:53:36,522 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2024-11-09 14:53:36,523 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 14:53:36,523 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2024-11-09 14:53:36,523 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=68, Invalid=274, Unknown=0, NotChecked=0, Total=342 [2024-11-09 14:53:36,546 INFO L467 CegarLoopForPetriNet]: Number of universal loopers: 20 out of 61 [2024-11-09 14:53:36,547 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 72 places, 62 transitions, 196 flow. Second operand has 19 states, 19 states have (on average 22.210526315789473) internal successors, (422), 19 states have internal predecessors, (422), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 14:53:36,547 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-11-09 14:53:36,547 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 20 of 61 [2024-11-09 14:53:36,547 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-11-09 14:53:38,596 INFO L124 PetriNetUnfolderBase]: 769/1660 cut-off events. [2024-11-09 14:53:38,596 INFO L125 PetriNetUnfolderBase]: For 269/269 co-relation queries the response was YES. [2024-11-09 14:53:38,598 INFO L83 FinitePrefix]: Finished finitePrefix Result has 3614 conditions, 1660 events. 769/1660 cut-off events. For 269/269 co-relation queries the response was YES. Maximal size of possible extension queue 57. Compared 9220 event pairs, 123 based on Foata normal form. 24/1551 useless extension candidates. Maximal degree in co-relation 3050. Up to 250 conditions per place. [2024-11-09 14:53:38,603 INFO L140 encePairwiseOnDemand]: 52/61 looper letters, 128 selfloop transitions, 16 changer transitions 3/165 dead transitions. [2024-11-09 14:53:38,603 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 84 places, 165 transitions, 742 flow [2024-11-09 14:53:38,603 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-11-09 14:53:38,603 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 14 states. [2024-11-09 14:53:38,604 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 14 states to 14 states and 427 transitions. [2024-11-09 14:53:38,605 INFO L512 CegarLoopForPetriNet]: DFA transition density 0.5 [2024-11-09 14:53:38,605 INFO L175 Difference]: Start difference. First operand has 72 places, 62 transitions, 196 flow. Second operand 14 states and 427 transitions. [2024-11-09 14:53:38,605 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 84 places, 165 transitions, 742 flow [2024-11-09 14:53:38,606 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 80 places, 165 transitions, 732 flow, removed 0 selfloop flow, removed 4 redundant places. [2024-11-09 14:53:38,608 INFO L231 Difference]: Finished difference. Result has 82 places, 68 transitions, 252 flow [2024-11-09 14:53:38,608 INFO L260 CegarLoopForPetriNet]: {PETRI_ALPHABET=61, PETRI_DIFFERENCE_MINUEND_FLOW=182, PETRI_DIFFERENCE_MINUEND_PLACES=67, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=61, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=10, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=49, PETRI_DIFFERENCE_SUBTRAHEND_STATES=14, PETRI_FLOW=252, PETRI_PLACES=82, PETRI_TRANSITIONS=68} [2024-11-09 14:53:38,608 INFO L277 CegarLoopForPetriNet]: 57 programPoint places, 25 predicate places. [2024-11-09 14:53:38,609 INFO L471 AbstractCegarLoop]: Abstraction has has 82 places, 68 transitions, 252 flow [2024-11-09 14:53:38,609 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 19 states have (on average 22.210526315789473) internal successors, (422), 19 states have internal predecessors, (422), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 14:53:38,609 INFO L196 CegarLoopForPetriNet]: Found error trace [2024-11-09 14:53:38,609 INFO L204 CegarLoopForPetriNet]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 14:53:38,634 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-09 14:53:38,813 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 14:53:38,814 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting t1Err1ASSERT_VIOLATIONINTEGER_OVERFLOW === [ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES, ULTIMATE.startErr1INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (and 24 more)] === [2024-11-09 14:53:38,814 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 14:53:38,814 INFO L85 PathProgramCache]: Analyzing trace with hash -676136996, now seen corresponding path program 1 times [2024-11-09 14:53:38,814 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 14:53:38,814 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [471881187] [2024-11-09 14:53:38,814 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 14:53:38,815 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 14:53:38,965 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 14:53:41,534 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 14:53:41,535 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 14:53:41,535 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [471881187] [2024-11-09 14:53:41,535 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [471881187] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 14:53:41,535 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [662107148] [2024-11-09 14:53:41,535 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 14:53:41,535 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 14:53:41,535 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 14:53:41,537 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 14:53:41,540 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-09 14:53:41,972 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 14:53:41,990 INFO L255 TraceCheckSpWp]: Trace formula consists of 3392 conjuncts, 39 conjuncts are in the unsatisfiable core [2024-11-09 14:53:41,997 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 14:53:42,009 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 22 [2024-11-09 14:53:42,100 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 6 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 37 treesize of output 31 [2024-11-09 14:53:42,175 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 3 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 37 treesize of output 24 [2024-11-09 14:53:42,283 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 3 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 37 treesize of output 24 [2024-11-09 14:53:42,378 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 38 treesize of output 28 [2024-11-09 14:53:42,381 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 3 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 38 treesize of output 26 [2024-11-09 14:53:42,404 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 14:53:42,404 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 14:53:45,597 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 14:53:45,597 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [662107148] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 14:53:45,597 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 14:53:45,597 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 6] total 17 [2024-11-09 14:53:45,597 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1504610099] [2024-11-09 14:53:45,598 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 14:53:45,598 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2024-11-09 14:53:45,598 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 14:53:45,599 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2024-11-09 14:53:45,599 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=88, Invalid=252, Unknown=2, NotChecked=0, Total=342 [2024-11-09 14:53:47,283 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.67s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2024-11-09 14:53:48,882 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.59s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2024-11-09 14:53:50,546 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.65s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2024-11-09 14:53:50,546 INFO L467 CegarLoopForPetriNet]: Number of universal loopers: 19 out of 61 [2024-11-09 14:53:50,547 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 82 places, 68 transitions, 252 flow. Second operand has 19 states, 19 states have (on average 21.42105263157895) internal successors, (407), 19 states have internal predecessors, (407), 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-09 14:53:50,547 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-11-09 14:53:50,547 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 19 of 61 [2024-11-09 14:53:50,547 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-11-09 14:53:57,179 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.87s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2024-11-09 14:54:05,101 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.97s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2024-11-09 14:54:05,623 INFO L124 PetriNetUnfolderBase]: 1381/2914 cut-off events. [2024-11-09 14:54:05,623 INFO L125 PetriNetUnfolderBase]: For 794/794 co-relation queries the response was YES. [2024-11-09 14:54:05,629 INFO L83 FinitePrefix]: Finished finitePrefix Result has 6700 conditions, 2914 events. 1381/2914 cut-off events. For 794/794 co-relation queries the response was YES. Maximal size of possible extension queue 107. Compared 18065 event pairs, 183 based on Foata normal form. 36/2766 useless extension candidates. Maximal degree in co-relation 5771. Up to 1111 conditions per place. [2024-11-09 14:54:05,638 INFO L140 encePairwiseOnDemand]: 52/61 looper letters, 150 selfloop transitions, 18 changer transitions 3/188 dead transitions. [2024-11-09 14:54:05,638 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 94 places, 188 transitions, 927 flow [2024-11-09 14:54:05,639 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2024-11-09 14:54:05,639 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 13 states. [2024-11-09 14:54:05,640 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 13 states to 13 states and 410 transitions. [2024-11-09 14:54:05,640 INFO L512 CegarLoopForPetriNet]: DFA transition density 0.5170239596469105 [2024-11-09 14:54:05,640 INFO L175 Difference]: Start difference. First operand has 82 places, 68 transitions, 252 flow. Second operand 13 states and 410 transitions. [2024-11-09 14:54:05,640 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 94 places, 188 transitions, 927 flow [2024-11-09 14:54:05,644 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 88 places, 188 transitions, 898 flow, removed 9 selfloop flow, removed 6 redundant places. [2024-11-09 14:54:05,646 INFO L231 Difference]: Finished difference. Result has 94 places, 81 transitions, 380 flow [2024-11-09 14:54:05,647 INFO L260 CegarLoopForPetriNet]: {PETRI_ALPHABET=61, PETRI_DIFFERENCE_MINUEND_FLOW=233, PETRI_DIFFERENCE_MINUEND_PLACES=76, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=68, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=8, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=53, PETRI_DIFFERENCE_SUBTRAHEND_STATES=13, PETRI_FLOW=380, PETRI_PLACES=94, PETRI_TRANSITIONS=81} [2024-11-09 14:54:05,647 INFO L277 CegarLoopForPetriNet]: 57 programPoint places, 37 predicate places. [2024-11-09 14:54:05,647 INFO L471 AbstractCegarLoop]: Abstraction has has 94 places, 81 transitions, 380 flow [2024-11-09 14:54:05,647 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 19 states have (on average 21.42105263157895) internal successors, (407), 19 states have internal predecessors, (407), 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-09 14:54:05,647 INFO L196 CegarLoopForPetriNet]: Found error trace [2024-11-09 14:54:05,648 INFO L204 CegarLoopForPetriNet]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 14:54:05,669 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2024-11-09 14:54:05,848 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable7 [2024-11-09 14:54:05,848 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting t1Err2ASSERT_VIOLATIONINTEGER_OVERFLOW === [ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES, ULTIMATE.startErr1INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (and 24 more)] === [2024-11-09 14:54:05,848 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 14:54:05,849 INFO L85 PathProgramCache]: Analyzing trace with hash -1227469057, now seen corresponding path program 1 times [2024-11-09 14:54:05,849 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 14:54:05,849 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1939762597] [2024-11-09 14:54:05,849 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 14:54:05,849 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 14:54:05,986 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 14:54:07,346 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 1 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 14:54:07,346 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 14:54:07,347 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1939762597] [2024-11-09 14:54:07,347 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1939762597] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 14:54:07,347 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1465325644] [2024-11-09 14:54:07,347 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 14:54:07,347 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 14:54:07,349 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 14:54:07,353 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-09 14:54:07,355 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-09 14:54:07,760 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 14:54:07,771 INFO L255 TraceCheckSpWp]: Trace formula consists of 3404 conjuncts, 37 conjuncts are in the unsatisfiable core [2024-11-09 14:54:07,774 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 14:54:07,914 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 43 treesize of output 21 [2024-11-09 14:54:07,974 INFO L349 Elim1Store]: treesize reduction 31, result has 22.5 percent of original size [2024-11-09 14:54:07,974 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 2 new quantified variables, introduced 1 case distinctions, treesize of input 57 treesize of output 41 [2024-11-09 14:54:08,016 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 41 treesize of output 19 [2024-11-09 14:54:08,029 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 31 treesize of output 13 [2024-11-09 14:54:08,045 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 1 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 14:54:08,045 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 14:54:08,239 INFO L349 Elim1Store]: treesize reduction 40, result has 36.5 percent of original size [2024-11-09 14:54:08,239 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 3 new quantified variables, introduced 4 case distinctions, treesize of input 123 treesize of output 85 [2024-11-09 14:54:08,249 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-09 14:54:08,249 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 86 treesize of output 82 [2024-11-09 14:54:08,269 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 9 [2024-11-09 14:54:08,285 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-09 14:54:08,285 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 56 treesize of output 44 [2024-11-09 14:54:08,302 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 1 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 14:54:08,302 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1465325644] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 14:54:08,302 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 14:54:08,303 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 8, 8] total 19 [2024-11-09 14:54:08,303 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [978712857] [2024-11-09 14:54:08,303 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 14:54:08,303 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2024-11-09 14:54:08,304 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 14:54:08,304 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2024-11-09 14:54:08,304 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=68, Invalid=312, Unknown=0, NotChecked=0, Total=380 [2024-11-09 14:54:08,311 INFO L467 CegarLoopForPetriNet]: Number of universal loopers: 22 out of 61 [2024-11-09 14:54:08,311 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 94 places, 81 transitions, 380 flow. Second operand has 20 states, 20 states have (on average 24.05) internal successors, (481), 20 states have internal predecessors, (481), 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-09 14:54:08,311 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-11-09 14:54:08,312 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 22 of 61 [2024-11-09 14:54:08,312 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-11-09 14:54:10,472 INFO L124 PetriNetUnfolderBase]: 1231/2738 cut-off events. [2024-11-09 14:54:10,473 INFO L125 PetriNetUnfolderBase]: For 1544/1544 co-relation queries the response was YES. [2024-11-09 14:54:10,479 INFO L83 FinitePrefix]: Finished finitePrefix Result has 6540 conditions, 2738 events. 1231/2738 cut-off events. For 1544/1544 co-relation queries the response was YES. Maximal size of possible extension queue 104. Compared 17574 event pairs, 638 based on Foata normal form. 36/2600 useless extension candidates. Maximal degree in co-relation 5698. Up to 1227 conditions per place. [2024-11-09 14:54:10,487 INFO L140 encePairwiseOnDemand]: 51/61 looper letters, 64 selfloop transitions, 33 changer transitions 0/117 dead transitions. [2024-11-09 14:54:10,488 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 101 places, 117 transitions, 655 flow [2024-11-09 14:54:10,489 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-09 14:54:10,489 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 9 states. [2024-11-09 14:54:10,490 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 9 states to 9 states and 272 transitions. [2024-11-09 14:54:10,490 INFO L512 CegarLoopForPetriNet]: DFA transition density 0.49544626593806923 [2024-11-09 14:54:10,490 INFO L175 Difference]: Start difference. First operand has 94 places, 81 transitions, 380 flow. Second operand 9 states and 272 transitions. [2024-11-09 14:54:10,490 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 101 places, 117 transitions, 655 flow [2024-11-09 14:54:10,494 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 97 places, 117 transitions, 637 flow, removed 5 selfloop flow, removed 4 redundant places. [2024-11-09 14:54:10,495 INFO L231 Difference]: Finished difference. Result has 97 places, 81 transitions, 428 flow [2024-11-09 14:54:10,495 INFO L260 CegarLoopForPetriNet]: {PETRI_ALPHABET=61, PETRI_DIFFERENCE_MINUEND_FLOW=358, PETRI_DIFFERENCE_MINUEND_PLACES=89, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=80, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=32, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=48, PETRI_DIFFERENCE_SUBTRAHEND_STATES=9, PETRI_FLOW=428, PETRI_PLACES=97, PETRI_TRANSITIONS=81} [2024-11-09 14:54:10,496 INFO L277 CegarLoopForPetriNet]: 57 programPoint places, 40 predicate places. [2024-11-09 14:54:10,496 INFO L471 AbstractCegarLoop]: Abstraction has has 97 places, 81 transitions, 428 flow [2024-11-09 14:54:10,496 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 20 states have (on average 24.05) internal successors, (481), 20 states have internal predecessors, (481), 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-09 14:54:10,497 INFO L196 CegarLoopForPetriNet]: Found error trace [2024-11-09 14:54:10,497 INFO L204 CegarLoopForPetriNet]: trace histogram [2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 14:54:10,515 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-09 14:54:10,700 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 14:54:10,701 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting t1Err3ASSERT_VIOLATIONINTEGER_OVERFLOW === [ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES, ULTIMATE.startErr1INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES (and 24 more)] === [2024-11-09 14:54:10,701 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 14:54:10,703 INFO L85 PathProgramCache]: Analyzing trace with hash 603168728, now seen corresponding path program 1 times [2024-11-09 14:54:10,703 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 14:54:10,703 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1650797781] [2024-11-09 14:54:10,703 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 14:54:10,703 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms