./Ultimate.py --spec ../../../trunk/examples/svcomp/properties/unreach-call.prp --file ../../../trunk/examples/svcomp/weaver/popl20-more-inc-subseq.wvr.c --full-output --traceabstraction.when.to.check.the.insufficient.erros.location.relative.to.the.other.error.locations TOGETHER --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version b8dbc81d Calling Ultimate with: /usr/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 ../../../trunk/examples/svcomp/weaver/popl20-more-inc-subseq.wvr.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness.graphml --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash cd94157895dc71e9f24fce5dbc4a71d4e4b55c4da9be28372139a3001decae0a --traceabstraction.when.to.check.the.insufficient.erros.location.relative.to.the.other.error.locations TOGETHER --- Real Ultimate output --- This is Ultimate 0.2.3-?-b8dbc81 [2023-08-31 02:59:16,616 INFO L177 SettingsManager]: Resetting all preferences to default values... [2023-08-31 02:59:16,618 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2023-08-31 02:59:16,663 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2023-08-31 02:59:16,665 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2023-08-31 02:59:16,668 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2023-08-31 02:59:16,670 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2023-08-31 02:59:16,672 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2023-08-31 02:59:16,674 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2023-08-31 02:59:16,679 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2023-08-31 02:59:16,680 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2023-08-31 02:59:16,686 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2023-08-31 02:59:16,686 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2023-08-31 02:59:16,688 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2023-08-31 02:59:16,689 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2023-08-31 02:59:16,692 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2023-08-31 02:59:16,693 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2023-08-31 02:59:16,694 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2023-08-31 02:59:16,696 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2023-08-31 02:59:16,700 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2023-08-31 02:59:16,702 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2023-08-31 02:59:16,703 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2023-08-31 02:59:16,703 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2023-08-31 02:59:16,704 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2023-08-31 02:59:16,711 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2023-08-31 02:59:16,711 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2023-08-31 02:59:16,711 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2023-08-31 02:59:16,713 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2023-08-31 02:59:16,713 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2023-08-31 02:59:16,714 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2023-08-31 02:59:16,714 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2023-08-31 02:59:16,720 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2023-08-31 02:59:16,722 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2023-08-31 02:59:16,723 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2023-08-31 02:59:16,723 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2023-08-31 02:59:16,723 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2023-08-31 02:59:16,724 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2023-08-31 02:59:16,724 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2023-08-31 02:59:16,724 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2023-08-31 02:59:16,725 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2023-08-31 02:59:16,726 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2023-08-31 02:59:16,727 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2023-08-31 02:59:16,765 INFO L113 SettingsManager]: Loading preferences was successful [2023-08-31 02:59:16,766 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2023-08-31 02:59:16,767 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-08-31 02:59:16,767 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-08-31 02:59:16,768 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-08-31 02:59:16,768 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-08-31 02:59:16,769 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2023-08-31 02:59:16,769 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2023-08-31 02:59:16,769 INFO L138 SettingsManager]: * Use SBE=true [2023-08-31 02:59:16,769 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-08-31 02:59:16,770 INFO L138 SettingsManager]: * sizeof long=4 [2023-08-31 02:59:16,770 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2023-08-31 02:59:16,770 INFO L138 SettingsManager]: * sizeof POINTER=4 [2023-08-31 02:59:16,771 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2023-08-31 02:59:16,771 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-08-31 02:59:16,771 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-08-31 02:59:16,771 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-08-31 02:59:16,771 INFO L138 SettingsManager]: * sizeof long double=12 [2023-08-31 02:59:16,771 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2023-08-31 02:59:16,773 INFO L138 SettingsManager]: * Use constant arrays=true [2023-08-31 02:59:16,773 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-08-31 02:59:16,777 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-08-31 02:59:16,777 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2023-08-31 02:59:16,778 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2023-08-31 02:59:16,779 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-08-31 02:59:16,779 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-08-31 02:59:16,780 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-08-31 02:59:16,780 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2023-08-31 02:59:16,780 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2023-08-31 02:59:16,780 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-08-31 02:59:16,780 INFO L138 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2023-08-31 02:59:16,781 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-08-31 02:59:16,781 INFO L138 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2023-08-31 02:59:16,781 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-08-31 02:59:16,781 INFO L138 SettingsManager]: * Independence relation used for large block encoding in concurrent analysis=SYNTACTIC [2023-08-31 02:59:16,781 INFO L138 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.graphml Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> cd94157895dc71e9f24fce5dbc4a71d4e4b55c4da9be28372139a3001decae0a Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: When to check the insufficient erros location relative to the other error locations -> TOGETHER [2023-08-31 02:59:17,080 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-08-31 02:59:17,099 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-08-31 02:59:17,102 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-08-31 02:59:17,103 INFO L271 PluginConnector]: Initializing CDTParser... [2023-08-31 02:59:17,103 INFO L275 PluginConnector]: CDTParser initialized [2023-08-31 02:59:17,105 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/weaver/popl20-more-inc-subseq.wvr.c [2023-08-31 02:59:18,196 INFO L500 CDTParser]: Created temporary CDT project at NULL [2023-08-31 02:59:18,381 INFO L351 CDTParser]: Found 1 translation units. [2023-08-31 02:59:18,382 INFO L172 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/weaver/popl20-more-inc-subseq.wvr.c [2023-08-31 02:59:18,391 INFO L394 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/4fa273221/00c4667f03914f8b9f6ece82798bfceb/FLAG006fafd78 [2023-08-31 02:59:18,403 INFO L402 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/4fa273221/00c4667f03914f8b9f6ece82798bfceb [2023-08-31 02:59:18,406 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-08-31 02:59:18,407 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2023-08-31 02:59:18,408 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-08-31 02:59:18,408 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-08-31 02:59:18,411 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2023-08-31 02:59:18,411 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 31.08 02:59:18" (1/1) ... [2023-08-31 02:59:18,412 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@77f78444 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.08 02:59:18, skipping insertion in model container [2023-08-31 02:59:18,412 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 31.08 02:59:18" (1/1) ... [2023-08-31 02:59:18,419 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2023-08-31 02:59:18,444 INFO L178 MainTranslator]: Built tables and reachable declarations [2023-08-31 02:59:18,565 WARN L247 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/weaver/popl20-more-inc-subseq.wvr.c[2924,2937] [2023-08-31 02:59:18,572 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-08-31 02:59:18,580 INFO L203 MainTranslator]: Completed pre-run [2023-08-31 02:59:18,599 WARN L247 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/weaver/popl20-more-inc-subseq.wvr.c[2924,2937] [2023-08-31 02:59:18,602 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-08-31 02:59:18,609 WARN L667 CHandler]: The function __VERIFIER_atomic_begin is called, but not defined or handled by StandardFunctionHandler. [2023-08-31 02:59:18,609 WARN L667 CHandler]: The function __VERIFIER_atomic_end is called, but not defined or handled by StandardFunctionHandler. [2023-08-31 02:59:18,615 INFO L208 MainTranslator]: Completed translation [2023-08-31 02:59:18,616 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.08 02:59:18 WrapperNode [2023-08-31 02:59:18,616 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-08-31 02:59:18,617 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-08-31 02:59:18,617 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-08-31 02:59:18,617 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2023-08-31 02:59:18,623 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.08 02:59:18" (1/1) ... [2023-08-31 02:59:18,630 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.08 02:59:18" (1/1) ... [2023-08-31 02:59:18,651 INFO L138 Inliner]: procedures = 24, calls = 45, calls flagged for inlining = 11, calls inlined = 13, statements flattened = 196 [2023-08-31 02:59:18,651 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-08-31 02:59:18,652 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-08-31 02:59:18,652 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2023-08-31 02:59:18,652 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2023-08-31 02:59:18,659 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.08 02:59:18" (1/1) ... [2023-08-31 02:59:18,660 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.08 02:59:18" (1/1) ... [2023-08-31 02:59:18,663 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.08 02:59:18" (1/1) ... [2023-08-31 02:59:18,663 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.08 02:59:18" (1/1) ... [2023-08-31 02:59:18,669 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.08 02:59:18" (1/1) ... [2023-08-31 02:59:18,679 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.08 02:59:18" (1/1) ... [2023-08-31 02:59:18,683 INFO L185 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.08 02:59:18" (1/1) ... [2023-08-31 02:59:18,691 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.08 02:59:18" (1/1) ... [2023-08-31 02:59:18,694 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-08-31 02:59:18,695 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-08-31 02:59:18,698 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2023-08-31 02:59:18,698 INFO L275 PluginConnector]: RCFGBuilder initialized [2023-08-31 02:59:18,699 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.08 02:59:18" (1/1) ... [2023-08-31 02:59:18,704 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-08-31 02:59:18,714 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-08-31 02:59:18,730 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2023-08-31 02:59:18,752 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2023-08-31 02:59:18,773 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-08-31 02:59:18,773 INFO L130 BoogieDeclarations]: Found specification of procedure thread1 [2023-08-31 02:59:18,773 INFO L138 BoogieDeclarations]: Found implementation of procedure thread1 [2023-08-31 02:59:18,774 INFO L130 BoogieDeclarations]: Found specification of procedure thread2 [2023-08-31 02:59:18,775 INFO L138 BoogieDeclarations]: Found implementation of procedure thread2 [2023-08-31 02:59:18,775 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-08-31 02:59:18,775 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2023-08-31 02:59:18,775 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2023-08-31 02:59:18,775 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_atomic_end [2023-08-31 02:59:18,776 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_atomic_begin [2023-08-31 02:59:18,776 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2023-08-31 02:59:18,776 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-08-31 02:59:18,776 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-08-31 02:59:18,776 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2023-08-31 02:59:18,776 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2023-08-31 02:59:18,778 WARN L210 CfgBuilder]: User set CodeBlockSize to SequenceOfStatements but program contains fork statements. Overwriting the user preferences and setting CodeBlockSize to OneNontrivialStatement [2023-08-31 02:59:18,937 INFO L236 CfgBuilder]: Building ICFG [2023-08-31 02:59:18,938 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2023-08-31 02:59:19,251 INFO L277 CfgBuilder]: Performing block encoding [2023-08-31 02:59:19,390 INFO L297 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-08-31 02:59:19,391 INFO L302 CfgBuilder]: Removed 4 assume(true) statements. [2023-08-31 02:59:19,393 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 31.08 02:59:19 BoogieIcfgContainer [2023-08-31 02:59:19,393 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-08-31 02:59:19,395 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-08-31 02:59:19,395 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2023-08-31 02:59:19,398 INFO L275 PluginConnector]: TraceAbstraction initialized [2023-08-31 02:59:19,398 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 31.08 02:59:18" (1/3) ... [2023-08-31 02:59:19,399 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@ddffb28 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 31.08 02:59:19, skipping insertion in model container [2023-08-31 02:59:19,399 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.08 02:59:18" (2/3) ... [2023-08-31 02:59:19,399 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@ddffb28 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 31.08 02:59:19, skipping insertion in model container [2023-08-31 02:59:19,399 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 31.08 02:59:19" (3/3) ... [2023-08-31 02:59:19,400 INFO L112 eAbstractionObserver]: Analyzing ICFG popl20-more-inc-subseq.wvr.c [2023-08-31 02:59:19,407 WARN L145 ceAbstractionStarter]: Switching off computation of Hoare annotation because input is a concurrent program [2023-08-31 02:59:19,416 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-08-31 02:59:19,417 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-08-31 02:59:19,417 INFO L515 ceAbstractionStarter]: Constructing petrified ICFG for 1 thread instances. [2023-08-31 02:59:19,511 INFO L144 ThreadInstanceAdder]: Constructed 2 joinOtherThreadTransitions. [2023-08-31 02:59:19,558 INFO L73 FinitePrefix]: Start finitePrefix. Operand has 170 places, 178 transitions, 372 flow [2023-08-31 02:59:19,658 INFO L130 PetriNetUnfolder]: 15/176 cut-off events. [2023-08-31 02:59:19,659 INFO L131 PetriNetUnfolder]: For 2/2 co-relation queries the response was YES. [2023-08-31 02:59:19,664 INFO L83 FinitePrefix]: Finished finitePrefix Result has 185 conditions, 176 events. 15/176 cut-off events. For 2/2 co-relation queries the response was YES. Maximal size of possible extension queue 4. Compared 108 event pairs, 0 based on Foata normal form. 0/160 useless extension candidates. Maximal degree in co-relation 143. Up to 2 conditions per place. [2023-08-31 02:59:19,665 INFO L82 GeneralOperation]: Start removeDead. Operand has 170 places, 178 transitions, 372 flow [2023-08-31 02:59:19,669 INFO L88 GeneralOperation]: Finished RemoveDead, result has has 160 places, 168 transitions, 348 flow [2023-08-31 02:59:19,675 INFO L124 etLargeBlockEncoding]: Petri net LBE is using variable-based independence relation. [2023-08-31 02:59:19,717 INFO L131 etLargeBlockEncoding]: Starting large block encoding on Petri net that has 160 places, 168 transitions, 348 flow [2023-08-31 02:59:19,720 INFO L113 LiptonReduction]: Starting Lipton reduction on Petri net that has 160 places, 168 transitions, 348 flow [2023-08-31 02:59:19,720 INFO L73 FinitePrefix]: Start finitePrefix. Operand has 160 places, 168 transitions, 348 flow [2023-08-31 02:59:19,796 INFO L130 PetriNetUnfolder]: 15/168 cut-off events. [2023-08-31 02:59:19,797 INFO L131 PetriNetUnfolder]: For 2/2 co-relation queries the response was YES. [2023-08-31 02:59:19,799 INFO L83 FinitePrefix]: Finished finitePrefix Result has 177 conditions, 168 events. 15/168 cut-off events. For 2/2 co-relation queries the response was YES. Maximal size of possible extension queue 4. Compared 109 event pairs, 0 based on Foata normal form. 0/153 useless extension candidates. Maximal degree in co-relation 143. Up to 2 conditions per place. [2023-08-31 02:59:19,801 INFO L119 LiptonReduction]: Number of co-enabled transitions 690 [2023-08-31 02:59:25,181 INFO L134 LiptonReduction]: Checked pairs total: 1199 [2023-08-31 02:59:25,182 INFO L136 LiptonReduction]: Total number of compositions: 174 [2023-08-31 02:59:25,197 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-08-31 02:59:25,201 INFO L357 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=PETRI_NET, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopsAndPotentialCycles, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP, mPorIndependenceSettings=[Lde.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings;@2416f734, mLbeIndependenceSettings=[IndependenceType=SYNTACTIC, AbstractionType=NONE, UseConditional=, UseSemiCommutativity=, Solver=, SolverTimeout=] [2023-08-31 02:59:25,201 INFO L358 AbstractCegarLoop]: Starting to check reachability of 3 error locations. [2023-08-31 02:59:25,210 INFO L130 PetriNetUnfolder]: 5/22 cut-off events. [2023-08-31 02:59:25,211 INFO L131 PetriNetUnfolder]: For 2/2 co-relation queries the response was YES. [2023-08-31 02:59:25,211 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-31 02:59:25,211 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-08-31 02:59:25,212 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES, ULTIMATE.startErr1INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES] === [2023-08-31 02:59:25,215 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-31 02:59:25,215 INFO L85 PathProgramCache]: Analyzing trace with hash 1033780346, now seen corresponding path program 1 times [2023-08-31 02:59:25,222 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-31 02:59:25,222 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [938296451] [2023-08-31 02:59:25,223 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-31 02:59:25,223 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-31 02:59:25,414 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-31 02:59:25,692 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-31 02:59:25,693 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-31 02:59:25,693 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [938296451] [2023-08-31 02:59:25,693 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [938296451] provided 1 perfect and 0 imperfect interpolant sequences [2023-08-31 02:59:25,694 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-08-31 02:59:25,694 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2023-08-31 02:59:25,695 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [961006371] [2023-08-31 02:59:25,696 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-08-31 02:59:25,702 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-08-31 02:59:25,707 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-31 02:59:25,727 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-08-31 02:59:25,728 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-08-31 02:59:25,784 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 152 out of 352 [2023-08-31 02:59:25,790 INFO L100 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 25 places, 23 transitions, 58 flow. Second operand has 3 states, 3 states have (on average 156.33333333333334) internal successors, (469), 3 states have internal predecessors, (469), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 02:59:25,790 INFO L109 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-31 02:59:25,790 INFO L110 encePairwiseOnDemand]: Number of universal subtrahend loopers: 152 of 352 [2023-08-31 02:59:25,791 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-31 02:59:25,868 INFO L130 PetriNetUnfolder]: 93/157 cut-off events. [2023-08-31 02:59:25,869 INFO L131 PetriNetUnfolder]: For 11/11 co-relation queries the response was YES. [2023-08-31 02:59:25,869 INFO L83 FinitePrefix]: Finished finitePrefix Result has 332 conditions, 157 events. 93/157 cut-off events. For 11/11 co-relation queries the response was YES. Maximal size of possible extension queue 18. Compared 450 event pairs, 51 based on Foata normal form. 0/115 useless extension candidates. Maximal degree in co-relation 267. Up to 154 conditions per place. [2023-08-31 02:59:25,872 INFO L137 encePairwiseOnDemand]: 349/352 looper letters, 21 selfloop transitions, 2 changer transitions 0/24 dead transitions. [2023-08-31 02:59:25,872 INFO L142 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 27 places, 24 transitions, 106 flow [2023-08-31 02:59:25,874 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-08-31 02:59:25,876 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3 states. [2023-08-31 02:59:25,888 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 480 transitions. [2023-08-31 02:59:25,892 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.45454545454545453 [2023-08-31 02:59:25,893 INFO L72 ComplementDD]: Start complementDD. Operand 3 states and 480 transitions. [2023-08-31 02:59:25,893 INFO L73 IsDeterministic]: Start isDeterministic. Operand 3 states and 480 transitions. [2023-08-31 02:59:25,896 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-31 02:59:25,898 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 3 states and 480 transitions. [2023-08-31 02:59:25,903 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 4 states, 3 states have (on average 160.0) internal successors, (480), 3 states have internal predecessors, (480), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 02:59:25,909 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 4 states, 4 states have (on average 352.0) internal successors, (1408), 4 states have internal predecessors, (1408), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 02:59:25,910 INFO L81 ComplementDD]: Finished complementDD. Result has 4 states, 4 states have (on average 352.0) internal successors, (1408), 4 states have internal predecessors, (1408), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 02:59:25,911 INFO L175 Difference]: Start difference. First operand has 25 places, 23 transitions, 58 flow. Second operand 3 states and 480 transitions. [2023-08-31 02:59:25,912 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 27 places, 24 transitions, 106 flow [2023-08-31 02:59:25,914 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 23 places, 24 transitions, 98 flow, removed 0 selfloop flow, removed 4 redundant places. [2023-08-31 02:59:25,916 INFO L231 Difference]: Finished difference. Result has 24 places, 24 transitions, 62 flow [2023-08-31 02:59:25,917 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=352, PETRI_DIFFERENCE_MINUEND_FLOW=50, PETRI_DIFFERENCE_MINUEND_PLACES=21, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=23, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=1, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=21, PETRI_DIFFERENCE_SUBTRAHEND_STATES=3, PETRI_FLOW=62, PETRI_PLACES=24, PETRI_TRANSITIONS=24} [2023-08-31 02:59:25,920 INFO L281 CegarLoopForPetriNet]: 25 programPoint places, -1 predicate places. [2023-08-31 02:59:25,920 INFO L495 AbstractCegarLoop]: Abstraction has has 24 places, 24 transitions, 62 flow [2023-08-31 02:59:25,922 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 156.33333333333334) internal successors, (469), 3 states have internal predecessors, (469), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 02:59:25,922 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-31 02:59:25,923 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-08-31 02:59:25,925 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2023-08-31 02:59:25,925 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES, ULTIMATE.startErr1INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES] === [2023-08-31 02:59:25,932 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-31 02:59:25,932 INFO L85 PathProgramCache]: Analyzing trace with hash -25586866, now seen corresponding path program 1 times [2023-08-31 02:59:25,933 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-31 02:59:25,933 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2127448727] [2023-08-31 02:59:25,933 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-31 02:59:25,934 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-31 02:59:25,971 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-31 02:59:26,134 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-31 02:59:26,138 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-31 02:59:26,138 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2127448727] [2023-08-31 02:59:26,138 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2127448727] provided 0 perfect and 1 imperfect interpolant sequences [2023-08-31 02:59:26,139 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [786660801] [2023-08-31 02:59:26,139 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-31 02:59:26,139 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-31 02:59:26,139 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-08-31 02:59:26,145 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-08-31 02:59:26,170 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-08-31 02:59:26,233 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-31 02:59:26,235 INFO L263 TraceCheckSpWp]: Trace formula consists of 208 conjuncts, 6 conjunts are in the unsatisfiable core [2023-08-31 02:59:26,239 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-08-31 02:59:26,302 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-31 02:59:26,302 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-08-31 02:59:26,338 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-31 02:59:26,338 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [786660801] provided 1 perfect and 1 imperfect interpolant sequences [2023-08-31 02:59:26,339 INFO L185 FreeRefinementEngine]: Found 1 perfect and 2 imperfect interpolant sequences. [2023-08-31 02:59:26,339 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [4, 4] total 9 [2023-08-31 02:59:26,339 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [857526315] [2023-08-31 02:59:26,340 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-08-31 02:59:26,340 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-08-31 02:59:26,340 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-31 02:59:26,341 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-08-31 02:59:26,341 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2023-08-31 02:59:26,410 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 143 out of 352 [2023-08-31 02:59:26,411 INFO L100 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 24 places, 24 transitions, 62 flow. Second operand has 5 states, 5 states have (on average 145.8) internal successors, (729), 5 states have internal predecessors, (729), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 02:59:26,412 INFO L109 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-31 02:59:26,412 INFO L110 encePairwiseOnDemand]: Number of universal subtrahend loopers: 143 of 352 [2023-08-31 02:59:26,412 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-31 02:59:26,503 INFO L130 PetriNetUnfolder]: 170/274 cut-off events. [2023-08-31 02:59:26,503 INFO L131 PetriNetUnfolder]: For 1/1 co-relation queries the response was YES. [2023-08-31 02:59:26,504 INFO L83 FinitePrefix]: Finished finitePrefix Result has 565 conditions, 274 events. 170/274 cut-off events. For 1/1 co-relation queries the response was YES. Maximal size of possible extension queue 27. Compared 946 event pairs, 36 based on Foata normal form. 0/205 useless extension candidates. Maximal degree in co-relation 550. Up to 102 conditions per place. [2023-08-31 02:59:26,505 INFO L137 encePairwiseOnDemand]: 345/352 looper letters, 32 selfloop transitions, 8 changer transitions 0/41 dead transitions. [2023-08-31 02:59:26,505 INFO L142 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 29 places, 41 transitions, 178 flow [2023-08-31 02:59:26,506 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-08-31 02:59:26,506 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 6 states. [2023-08-31 02:59:26,508 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 899 transitions. [2023-08-31 02:59:26,508 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.4256628787878788 [2023-08-31 02:59:26,508 INFO L72 ComplementDD]: Start complementDD. Operand 6 states and 899 transitions. [2023-08-31 02:59:26,509 INFO L73 IsDeterministic]: Start isDeterministic. Operand 6 states and 899 transitions. [2023-08-31 02:59:26,509 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-31 02:59:26,509 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 6 states and 899 transitions. [2023-08-31 02:59:26,511 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 7 states, 6 states have (on average 149.83333333333334) internal successors, (899), 6 states have internal predecessors, (899), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 02:59:26,515 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 7 states, 7 states have (on average 352.0) internal successors, (2464), 7 states have internal predecessors, (2464), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 02:59:26,516 INFO L81 ComplementDD]: Finished complementDD. Result has 7 states, 7 states have (on average 352.0) internal successors, (2464), 7 states have internal predecessors, (2464), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 02:59:26,516 INFO L175 Difference]: Start difference. First operand has 24 places, 24 transitions, 62 flow. Second operand 6 states and 899 transitions. [2023-08-31 02:59:26,516 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 29 places, 41 transitions, 178 flow [2023-08-31 02:59:26,517 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 28 places, 41 transitions, 174 flow, removed 1 selfloop flow, removed 1 redundant places. [2023-08-31 02:59:26,517 INFO L231 Difference]: Finished difference. Result has 30 places, 27 transitions, 93 flow [2023-08-31 02:59:26,518 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=352, PETRI_DIFFERENCE_MINUEND_FLOW=58, PETRI_DIFFERENCE_MINUEND_PLACES=23, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=24, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=5, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=18, PETRI_DIFFERENCE_SUBTRAHEND_STATES=6, PETRI_FLOW=93, PETRI_PLACES=30, PETRI_TRANSITIONS=27} [2023-08-31 02:59:26,518 INFO L281 CegarLoopForPetriNet]: 25 programPoint places, 5 predicate places. [2023-08-31 02:59:26,518 INFO L495 AbstractCegarLoop]: Abstraction has has 30 places, 27 transitions, 93 flow [2023-08-31 02:59:26,519 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 145.8) internal successors, (729), 5 states have internal predecessors, (729), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 02:59:26,519 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-31 02:59:26,519 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-08-31 02:59:26,525 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2023-08-31 02:59:26,725 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-31 02:59:26,726 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES, ULTIMATE.startErr1INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES] === [2023-08-31 02:59:26,726 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-31 02:59:26,726 INFO L85 PathProgramCache]: Analyzing trace with hash -1406989011, now seen corresponding path program 1 times [2023-08-31 02:59:26,727 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-31 02:59:26,727 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1409668053] [2023-08-31 02:59:26,727 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-31 02:59:26,727 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-31 02:59:26,762 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-31 02:59:26,869 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-08-31 02:59:26,870 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-31 02:59:26,870 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1409668053] [2023-08-31 02:59:26,870 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1409668053] provided 1 perfect and 0 imperfect interpolant sequences [2023-08-31 02:59:26,871 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-08-31 02:59:26,871 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2023-08-31 02:59:26,871 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1858858787] [2023-08-31 02:59:26,871 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-08-31 02:59:26,871 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-08-31 02:59:26,872 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-31 02:59:26,872 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-08-31 02:59:26,872 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-08-31 02:59:26,894 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 149 out of 352 [2023-08-31 02:59:26,895 INFO L100 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 30 places, 27 transitions, 93 flow. Second operand has 4 states, 4 states have (on average 153.25) internal successors, (613), 4 states have internal predecessors, (613), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 02:59:26,895 INFO L109 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-31 02:59:26,895 INFO L110 encePairwiseOnDemand]: Number of universal subtrahend loopers: 149 of 352 [2023-08-31 02:59:26,895 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-31 02:59:27,024 INFO L130 PetriNetUnfolder]: 294/476 cut-off events. [2023-08-31 02:59:27,025 INFO L131 PetriNetUnfolder]: For 175/175 co-relation queries the response was YES. [2023-08-31 02:59:27,026 INFO L83 FinitePrefix]: Finished finitePrefix Result has 1150 conditions, 476 events. 294/476 cut-off events. For 175/175 co-relation queries the response was YES. Maximal size of possible extension queue 39. Compared 1767 event pairs, 55 based on Foata normal form. 0/443 useless extension candidates. Maximal degree in co-relation 1126. Up to 250 conditions per place. [2023-08-31 02:59:27,028 INFO L137 encePairwiseOnDemand]: 345/352 looper letters, 46 selfloop transitions, 16 changer transitions 0/62 dead transitions. [2023-08-31 02:59:27,028 INFO L142 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 34 places, 62 transitions, 336 flow [2023-08-31 02:59:27,029 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-08-31 02:59:27,029 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 5 states. [2023-08-31 02:59:27,031 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 799 transitions. [2023-08-31 02:59:27,031 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.45397727272727273 [2023-08-31 02:59:27,031 INFO L72 ComplementDD]: Start complementDD. Operand 5 states and 799 transitions. [2023-08-31 02:59:27,031 INFO L73 IsDeterministic]: Start isDeterministic. Operand 5 states and 799 transitions. [2023-08-31 02:59:27,032 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-31 02:59:27,032 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 5 states and 799 transitions. [2023-08-31 02:59:27,034 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 6 states, 5 states have (on average 159.8) internal successors, (799), 5 states have internal predecessors, (799), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 02:59:27,037 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 6 states, 6 states have (on average 352.0) internal successors, (2112), 6 states have internal predecessors, (2112), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 02:59:27,038 INFO L81 ComplementDD]: Finished complementDD. Result has 6 states, 6 states have (on average 352.0) internal successors, (2112), 6 states have internal predecessors, (2112), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 02:59:27,039 INFO L175 Difference]: Start difference. First operand has 30 places, 27 transitions, 93 flow. Second operand 5 states and 799 transitions. [2023-08-31 02:59:27,039 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 34 places, 62 transitions, 336 flow [2023-08-31 02:59:27,041 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 32 places, 62 transitions, 332 flow, removed 0 selfloop flow, removed 2 redundant places. [2023-08-31 02:59:27,042 INFO L231 Difference]: Finished difference. Result has 35 places, 41 transitions, 234 flow [2023-08-31 02:59:27,042 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=352, PETRI_DIFFERENCE_MINUEND_FLOW=89, PETRI_DIFFERENCE_MINUEND_PLACES=28, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=27, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=2, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=18, PETRI_DIFFERENCE_SUBTRAHEND_STATES=5, PETRI_FLOW=234, PETRI_PLACES=35, PETRI_TRANSITIONS=41} [2023-08-31 02:59:27,043 INFO L281 CegarLoopForPetriNet]: 25 programPoint places, 10 predicate places. [2023-08-31 02:59:27,043 INFO L495 AbstractCegarLoop]: Abstraction has has 35 places, 41 transitions, 234 flow [2023-08-31 02:59:27,044 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 153.25) internal successors, (613), 4 states have internal predecessors, (613), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 02:59:27,044 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-31 02:59:27,044 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-08-31 02:59:27,044 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2023-08-31 02:59:27,054 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES, ULTIMATE.startErr1INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES] === [2023-08-31 02:59:27,055 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-31 02:59:27,055 INFO L85 PathProgramCache]: Analyzing trace with hash -1352553143, now seen corresponding path program 2 times [2023-08-31 02:59:27,055 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-31 02:59:27,055 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [419362589] [2023-08-31 02:59:27,056 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-31 02:59:27,056 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-31 02:59:27,079 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-31 02:59:27,153 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2023-08-31 02:59:27,154 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-31 02:59:27,154 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [419362589] [2023-08-31 02:59:27,154 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [419362589] provided 1 perfect and 0 imperfect interpolant sequences [2023-08-31 02:59:27,154 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-08-31 02:59:27,155 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2023-08-31 02:59:27,155 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1029680965] [2023-08-31 02:59:27,155 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-08-31 02:59:27,155 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-08-31 02:59:27,156 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-31 02:59:27,156 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-08-31 02:59:27,156 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-08-31 02:59:27,162 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 157 out of 352 [2023-08-31 02:59:27,162 INFO L100 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 35 places, 41 transitions, 234 flow. Second operand has 3 states, 3 states have (on average 162.33333333333334) internal successors, (487), 3 states have internal predecessors, (487), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 02:59:27,163 INFO L109 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-31 02:59:27,163 INFO L110 encePairwiseOnDemand]: Number of universal subtrahend loopers: 157 of 352 [2023-08-31 02:59:27,163 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-31 02:59:27,273 INFO L130 PetriNetUnfolder]: 477/766 cut-off events. [2023-08-31 02:59:27,273 INFO L131 PetriNetUnfolder]: For 1197/1219 co-relation queries the response was YES. [2023-08-31 02:59:27,275 INFO L83 FinitePrefix]: Finished finitePrefix Result has 2701 conditions, 766 events. 477/766 cut-off events. For 1197/1219 co-relation queries the response was YES. Maximal size of possible extension queue 59. Compared 3156 event pairs, 137 based on Foata normal form. 16/766 useless extension candidates. Maximal degree in co-relation 2675. Up to 433 conditions per place. [2023-08-31 02:59:27,279 INFO L137 encePairwiseOnDemand]: 349/352 looper letters, 62 selfloop transitions, 4 changer transitions 2/70 dead transitions. [2023-08-31 02:59:27,279 INFO L142 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 37 places, 70 transitions, 562 flow [2023-08-31 02:59:27,279 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-08-31 02:59:27,280 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3 states. [2023-08-31 02:59:27,281 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 507 transitions. [2023-08-31 02:59:27,281 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.48011363636363635 [2023-08-31 02:59:27,281 INFO L72 ComplementDD]: Start complementDD. Operand 3 states and 507 transitions. [2023-08-31 02:59:27,281 INFO L73 IsDeterministic]: Start isDeterministic. Operand 3 states and 507 transitions. [2023-08-31 02:59:27,282 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-31 02:59:27,282 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 3 states and 507 transitions. [2023-08-31 02:59:27,283 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 4 states, 3 states have (on average 169.0) internal successors, (507), 3 states have internal predecessors, (507), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 02:59:27,285 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 4 states, 4 states have (on average 352.0) internal successors, (1408), 4 states have internal predecessors, (1408), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 02:59:27,286 INFO L81 ComplementDD]: Finished complementDD. Result has 4 states, 4 states have (on average 352.0) internal successors, (1408), 4 states have internal predecessors, (1408), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 02:59:27,286 INFO L175 Difference]: Start difference. First operand has 35 places, 41 transitions, 234 flow. Second operand 3 states and 507 transitions. [2023-08-31 02:59:27,286 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 37 places, 70 transitions, 562 flow [2023-08-31 02:59:27,290 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 37 places, 70 transitions, 562 flow, removed 0 selfloop flow, removed 0 redundant places. [2023-08-31 02:59:27,291 INFO L231 Difference]: Finished difference. Result has 38 places, 44 transitions, 271 flow [2023-08-31 02:59:27,291 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=352, PETRI_DIFFERENCE_MINUEND_FLOW=234, PETRI_DIFFERENCE_MINUEND_PLACES=35, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=41, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=1, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=37, PETRI_DIFFERENCE_SUBTRAHEND_STATES=3, PETRI_FLOW=271, PETRI_PLACES=38, PETRI_TRANSITIONS=44} [2023-08-31 02:59:27,292 INFO L281 CegarLoopForPetriNet]: 25 programPoint places, 13 predicate places. [2023-08-31 02:59:27,292 INFO L495 AbstractCegarLoop]: Abstraction has has 38 places, 44 transitions, 271 flow [2023-08-31 02:59:27,293 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 162.33333333333334) internal successors, (487), 3 states have internal predecessors, (487), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 02:59:27,293 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-31 02:59:27,293 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-08-31 02:59:27,293 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2023-08-31 02:59:27,293 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES, ULTIMATE.startErr1INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES] === [2023-08-31 02:59:27,294 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-31 02:59:27,294 INFO L85 PathProgramCache]: Analyzing trace with hash -84645957, now seen corresponding path program 1 times [2023-08-31 02:59:27,294 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-31 02:59:27,294 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1339711455] [2023-08-31 02:59:27,294 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-31 02:59:27,295 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-31 02:59:27,319 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-31 02:59:27,464 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-08-31 02:59:27,465 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-31 02:59:27,465 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1339711455] [2023-08-31 02:59:27,465 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1339711455] provided 0 perfect and 1 imperfect interpolant sequences [2023-08-31 02:59:27,465 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1359024285] [2023-08-31 02:59:27,465 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-31 02:59:27,465 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-31 02:59:27,466 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-08-31 02:59:27,469 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-08-31 02:59:27,496 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-08-31 02:59:27,579 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-31 02:59:27,581 INFO L263 TraceCheckSpWp]: Trace formula consists of 230 conjuncts, 6 conjunts are in the unsatisfiable core [2023-08-31 02:59:27,583 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-08-31 02:59:27,605 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-08-31 02:59:27,606 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-08-31 02:59:27,606 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1359024285] provided 1 perfect and 0 imperfect interpolant sequences [2023-08-31 02:59:27,606 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-08-31 02:59:27,606 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [4] total 4 [2023-08-31 02:59:27,607 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [404054381] [2023-08-31 02:59:27,607 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-08-31 02:59:27,607 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-08-31 02:59:27,608 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-31 02:59:27,608 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-08-31 02:59:27,608 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-08-31 02:59:27,617 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 156 out of 352 [2023-08-31 02:59:27,618 INFO L100 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 38 places, 44 transitions, 271 flow. Second operand has 3 states, 3 states have (on average 162.0) internal successors, (486), 3 states have internal predecessors, (486), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 02:59:27,618 INFO L109 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-31 02:59:27,618 INFO L110 encePairwiseOnDemand]: Number of universal subtrahend loopers: 156 of 352 [2023-08-31 02:59:27,618 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-31 02:59:27,721 INFO L130 PetriNetUnfolder]: 398/667 cut-off events. [2023-08-31 02:59:27,721 INFO L131 PetriNetUnfolder]: For 1124/1156 co-relation queries the response was YES. [2023-08-31 02:59:27,723 INFO L83 FinitePrefix]: Finished finitePrefix Result has 2443 conditions, 667 events. 398/667 cut-off events. For 1124/1156 co-relation queries the response was YES. Maximal size of possible extension queue 39. Compared 2635 event pairs, 91 based on Foata normal form. 46/705 useless extension candidates. Maximal degree in co-relation 2414. Up to 555 conditions per place. [2023-08-31 02:59:27,726 INFO L137 encePairwiseOnDemand]: 349/352 looper letters, 47 selfloop transitions, 2 changer transitions 5/56 dead transitions. [2023-08-31 02:59:27,726 INFO L142 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 40 places, 56 transitions, 430 flow [2023-08-31 02:59:27,727 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-08-31 02:59:27,727 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3 states. [2023-08-31 02:59:27,728 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 502 transitions. [2023-08-31 02:59:27,728 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.4753787878787879 [2023-08-31 02:59:27,728 INFO L72 ComplementDD]: Start complementDD. Operand 3 states and 502 transitions. [2023-08-31 02:59:27,729 INFO L73 IsDeterministic]: Start isDeterministic. Operand 3 states and 502 transitions. [2023-08-31 02:59:27,729 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-31 02:59:27,729 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 3 states and 502 transitions. [2023-08-31 02:59:27,730 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 4 states, 3 states have (on average 167.33333333333334) internal successors, (502), 3 states have internal predecessors, (502), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 02:59:27,732 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 4 states, 4 states have (on average 352.0) internal successors, (1408), 4 states have internal predecessors, (1408), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 02:59:27,733 INFO L81 ComplementDD]: Finished complementDD. Result has 4 states, 4 states have (on average 352.0) internal successors, (1408), 4 states have internal predecessors, (1408), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 02:59:27,733 INFO L175 Difference]: Start difference. First operand has 38 places, 44 transitions, 271 flow. Second operand 3 states and 502 transitions. [2023-08-31 02:59:27,733 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 40 places, 56 transitions, 430 flow [2023-08-31 02:59:27,736 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 39 places, 56 transitions, 426 flow, removed 0 selfloop flow, removed 1 redundant places. [2023-08-31 02:59:27,737 INFO L231 Difference]: Finished difference. Result has 40 places, 44 transitions, 273 flow [2023-08-31 02:59:27,737 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=352, PETRI_DIFFERENCE_MINUEND_FLOW=257, PETRI_DIFFERENCE_MINUEND_PLACES=37, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=43, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=1, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=41, PETRI_DIFFERENCE_SUBTRAHEND_STATES=3, PETRI_FLOW=273, PETRI_PLACES=40, PETRI_TRANSITIONS=44} [2023-08-31 02:59:27,738 INFO L281 CegarLoopForPetriNet]: 25 programPoint places, 15 predicate places. [2023-08-31 02:59:27,738 INFO L495 AbstractCegarLoop]: Abstraction has has 40 places, 44 transitions, 273 flow [2023-08-31 02:59:27,739 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 162.0) internal successors, (486), 3 states have internal predecessors, (486), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 02:59:27,739 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-31 02:59:27,739 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-08-31 02:59:27,747 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2023-08-31 02:59:27,945 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-31 02:59:27,945 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES, ULTIMATE.startErr1INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES] === [2023-08-31 02:59:27,946 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-31 02:59:27,946 INFO L85 PathProgramCache]: Analyzing trace with hash 1320014892, now seen corresponding path program 1 times [2023-08-31 02:59:27,946 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-31 02:59:27,946 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [826654279] [2023-08-31 02:59:27,946 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-31 02:59:27,947 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-31 02:59:27,964 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-31 02:59:28,059 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2023-08-31 02:59:28,060 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-31 02:59:28,060 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [826654279] [2023-08-31 02:59:28,060 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [826654279] provided 1 perfect and 0 imperfect interpolant sequences [2023-08-31 02:59:28,060 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-08-31 02:59:28,060 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2023-08-31 02:59:28,061 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [319501904] [2023-08-31 02:59:28,061 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-08-31 02:59:28,061 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-08-31 02:59:28,062 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-31 02:59:28,062 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-08-31 02:59:28,062 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-08-31 02:59:28,117 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 150 out of 352 [2023-08-31 02:59:28,118 INFO L100 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 40 places, 44 transitions, 273 flow. Second operand has 4 states, 4 states have (on average 155.0) internal successors, (620), 4 states have internal predecessors, (620), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 02:59:28,118 INFO L109 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-31 02:59:28,118 INFO L110 encePairwiseOnDemand]: Number of universal subtrahend loopers: 150 of 352 [2023-08-31 02:59:28,118 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-31 02:59:28,258 INFO L130 PetriNetUnfolder]: 448/776 cut-off events. [2023-08-31 02:59:28,258 INFO L131 PetriNetUnfolder]: For 1574/1606 co-relation queries the response was YES. [2023-08-31 02:59:28,260 INFO L83 FinitePrefix]: Finished finitePrefix Result has 2933 conditions, 776 events. 448/776 cut-off events. For 1574/1606 co-relation queries the response was YES. Maximal size of possible extension queue 41. Compared 3252 event pairs, 242 based on Foata normal form. 42/807 useless extension candidates. Maximal degree in co-relation 2509. Up to 660 conditions per place. [2023-08-31 02:59:28,264 INFO L137 encePairwiseOnDemand]: 347/352 looper letters, 41 selfloop transitions, 2 changer transitions 20/65 dead transitions. [2023-08-31 02:59:28,264 INFO L142 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 44 places, 65 transitions, 505 flow [2023-08-31 02:59:28,264 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-08-31 02:59:28,264 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 5 states. [2023-08-31 02:59:28,266 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 789 transitions. [2023-08-31 02:59:28,266 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.44829545454545455 [2023-08-31 02:59:28,266 INFO L72 ComplementDD]: Start complementDD. Operand 5 states and 789 transitions. [2023-08-31 02:59:28,267 INFO L73 IsDeterministic]: Start isDeterministic. Operand 5 states and 789 transitions. [2023-08-31 02:59:28,267 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-31 02:59:28,267 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 5 states and 789 transitions. [2023-08-31 02:59:28,269 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 6 states, 5 states have (on average 157.8) internal successors, (789), 5 states have internal predecessors, (789), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 02:59:28,271 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 6 states, 6 states have (on average 352.0) internal successors, (2112), 6 states have internal predecessors, (2112), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 02:59:28,272 INFO L81 ComplementDD]: Finished complementDD. Result has 6 states, 6 states have (on average 352.0) internal successors, (2112), 6 states have internal predecessors, (2112), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 02:59:28,272 INFO L175 Difference]: Start difference. First operand has 40 places, 44 transitions, 273 flow. Second operand 5 states and 789 transitions. [2023-08-31 02:59:28,272 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 44 places, 65 transitions, 505 flow [2023-08-31 02:59:28,276 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 43 places, 65 transitions, 503 flow, removed 0 selfloop flow, removed 1 redundant places. [2023-08-31 02:59:28,277 INFO L231 Difference]: Finished difference. Result has 46 places, 45 transitions, 287 flow [2023-08-31 02:59:28,277 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=352, PETRI_DIFFERENCE_MINUEND_FLOW=271, PETRI_DIFFERENCE_MINUEND_PLACES=39, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=44, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=1, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=42, PETRI_DIFFERENCE_SUBTRAHEND_STATES=5, PETRI_FLOW=287, PETRI_PLACES=46, PETRI_TRANSITIONS=45} [2023-08-31 02:59:28,278 INFO L281 CegarLoopForPetriNet]: 25 programPoint places, 21 predicate places. [2023-08-31 02:59:28,278 INFO L495 AbstractCegarLoop]: Abstraction has has 46 places, 45 transitions, 287 flow [2023-08-31 02:59:28,279 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 155.0) internal successors, (620), 4 states have internal predecessors, (620), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 02:59:28,279 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-31 02:59:28,279 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-08-31 02:59:28,279 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5 [2023-08-31 02:59:28,279 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES, ULTIMATE.startErr1INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES] === [2023-08-31 02:59:28,280 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-31 02:59:28,280 INFO L85 PathProgramCache]: Analyzing trace with hash -1802696178, now seen corresponding path program 1 times [2023-08-31 02:59:28,280 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-31 02:59:28,280 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1466206893] [2023-08-31 02:59:28,280 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-31 02:59:28,281 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-31 02:59:28,320 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-31 02:59:29,359 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-08-31 02:59:29,359 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-31 02:59:29,359 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1466206893] [2023-08-31 02:59:29,359 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1466206893] provided 0 perfect and 1 imperfect interpolant sequences [2023-08-31 02:59:29,360 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1343102044] [2023-08-31 02:59:29,360 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-31 02:59:29,360 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-31 02:59:29,360 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-08-31 02:59:29,365 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-08-31 02:59:29,368 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-08-31 02:59:29,462 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-31 02:59:29,465 INFO L263 TraceCheckSpWp]: Trace formula consists of 249 conjuncts, 48 conjunts are in the unsatisfiable core [2023-08-31 02:59:29,467 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-08-31 02:59:29,716 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-08-31 02:59:29,722 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 20 [2023-08-31 02:59:30,095 INFO L321 Elim1Store]: treesize reduction 18, result has 5.3 percent of original size [2023-08-31 02:59:30,095 INFO L350 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 42 treesize of output 10 [2023-08-31 02:59:30,126 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-08-31 02:59:30,126 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-08-31 02:59:30,511 WARN L839 $PredicateComparison]: unable to prove that (or (<= c_~n~0 c_~end~0) (< |c_thread1Thread1of1ForFork1_#t~mem1#1| c_~last~0) (<= (+ c_~end~0 1) c_~start~0) (< c_~start~0 0) (let ((.cse1 (+ (* c_~end~0 4) c_~queue~0.offset)) (.cse3 (+ c_~A~0.offset (* c_~i~0 4)))) (and (forall ((v_ArrVal_173 (Array Int Int)) (~queue~0.base Int)) (let ((.cse2 (store |c_#memory_int| |c_ULTIMATE.start_main_~#t2~0#1.base| v_ArrVal_173))) (let ((.cse0 (select .cse2 ~queue~0.base))) (or (not (= (select .cse0 .cse1) (select (select .cse2 c_~A~0.base) .cse3))) (< c_~v_old~0 (+ (select .cse0 (+ (* c_~start~0 4) c_~queue~0.offset)) 1)))))) (or (forall ((v_ArrVal_173 (Array Int Int)) (~queue~0.base Int)) (not (let ((.cse4 (store |c_#memory_int| |c_ULTIMATE.start_main_~#t2~0#1.base| v_ArrVal_173))) (= (select (select .cse4 ~queue~0.base) .cse1) (select (select .cse4 c_~A~0.base) .cse3))))) (not (= (mod c_~ok~0 256) 0)))))) is different from false [2023-08-31 02:59:30,616 INFO L321 Elim1Store]: treesize reduction 11, result has 87.1 percent of original size [2023-08-31 02:59:30,617 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 258 treesize of output 251 [2023-08-31 02:59:30,652 INFO L321 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-08-31 02:59:30,652 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 174 treesize of output 185 [2023-08-31 02:59:30,675 INFO L321 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-08-31 02:59:30,676 INFO L350 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 144 treesize of output 137 [2023-08-31 02:59:31,788 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-08-31 02:59:31,789 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1343102044] provided 0 perfect and 2 imperfect interpolant sequences [2023-08-31 02:59:31,789 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-08-31 02:59:31,789 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 10, 10] total 28 [2023-08-31 02:59:31,789 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [655403666] [2023-08-31 02:59:31,790 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-08-31 02:59:31,790 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 30 states [2023-08-31 02:59:31,791 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-31 02:59:31,791 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2023-08-31 02:59:31,792 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=176, Invalid=639, Unknown=1, NotChecked=54, Total=870 [2023-08-31 02:59:31,925 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 86 out of 352 [2023-08-31 02:59:31,928 INFO L100 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 46 places, 45 transitions, 287 flow. Second operand has 30 states, 30 states have (on average 88.16666666666667) internal successors, (2645), 30 states have internal predecessors, (2645), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 02:59:31,928 INFO L109 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-31 02:59:31,928 INFO L110 encePairwiseOnDemand]: Number of universal subtrahend loopers: 86 of 352 [2023-08-31 02:59:31,928 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-31 02:59:39,461 INFO L130 PetriNetUnfolder]: 2018/3403 cut-off events. [2023-08-31 02:59:39,461 INFO L131 PetriNetUnfolder]: For 5752/5752 co-relation queries the response was YES. [2023-08-31 02:59:39,470 INFO L83 FinitePrefix]: Finished finitePrefix Result has 12830 conditions, 3403 events. 2018/3403 cut-off events. For 5752/5752 co-relation queries the response was YES. Maximal size of possible extension queue 193. Compared 19661 event pairs, 180 based on Foata normal form. 35/3434 useless extension candidates. Maximal degree in co-relation 12805. Up to 1081 conditions per place. [2023-08-31 02:59:39,487 INFO L137 encePairwiseOnDemand]: 334/352 looper letters, 262 selfloop transitions, 212 changer transitions 129/603 dead transitions. [2023-08-31 02:59:39,487 INFO L142 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 102 places, 603 transitions, 4719 flow [2023-08-31 02:59:39,488 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 59 states. [2023-08-31 02:59:39,488 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 59 states. [2023-08-31 02:59:39,502 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 59 states to 59 states and 5500 transitions. [2023-08-31 02:59:39,505 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.2648305084745763 [2023-08-31 02:59:39,505 INFO L72 ComplementDD]: Start complementDD. Operand 59 states and 5500 transitions. [2023-08-31 02:59:39,505 INFO L73 IsDeterministic]: Start isDeterministic. Operand 59 states and 5500 transitions. [2023-08-31 02:59:39,508 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-31 02:59:39,509 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 59 states and 5500 transitions. [2023-08-31 02:59:39,519 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 60 states, 59 states have (on average 93.22033898305085) internal successors, (5500), 59 states have internal predecessors, (5500), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 02:59:39,583 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 60 states, 60 states have (on average 352.0) internal successors, (21120), 60 states have internal predecessors, (21120), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 02:59:39,587 INFO L81 ComplementDD]: Finished complementDD. Result has 60 states, 60 states have (on average 352.0) internal successors, (21120), 60 states have internal predecessors, (21120), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 02:59:39,587 INFO L175 Difference]: Start difference. First operand has 46 places, 45 transitions, 287 flow. Second operand 59 states and 5500 transitions. [2023-08-31 02:59:39,587 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 102 places, 603 transitions, 4719 flow [2023-08-31 02:59:39,610 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 99 places, 603 transitions, 4687 flow, removed 15 selfloop flow, removed 3 redundant places. [2023-08-31 02:59:39,618 INFO L231 Difference]: Finished difference. Result has 139 places, 274 transitions, 2813 flow [2023-08-31 02:59:39,618 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=352, PETRI_DIFFERENCE_MINUEND_FLOW=279, PETRI_DIFFERENCE_MINUEND_PLACES=41, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=45, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=22, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=6, PETRI_DIFFERENCE_SUBTRAHEND_STATES=59, PETRI_FLOW=2813, PETRI_PLACES=139, PETRI_TRANSITIONS=274} [2023-08-31 02:59:39,619 INFO L281 CegarLoopForPetriNet]: 25 programPoint places, 114 predicate places. [2023-08-31 02:59:39,619 INFO L495 AbstractCegarLoop]: Abstraction has has 139 places, 274 transitions, 2813 flow [2023-08-31 02:59:39,620 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 30 states, 30 states have (on average 88.16666666666667) internal successors, (2645), 30 states have internal predecessors, (2645), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 02:59:39,621 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-31 02:59:39,621 INFO L208 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-08-31 02:59:39,630 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2023-08-31 02:59:39,827 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-31 02:59:39,828 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES, ULTIMATE.startErr1INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES] === [2023-08-31 02:59:39,828 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-31 02:59:39,828 INFO L85 PathProgramCache]: Analyzing trace with hash -1654979636, now seen corresponding path program 2 times [2023-08-31 02:59:39,828 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-31 02:59:39,828 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1967020520] [2023-08-31 02:59:39,829 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-31 02:59:39,829 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-31 02:59:39,887 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-31 02:59:40,784 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-08-31 02:59:40,785 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-31 02:59:40,785 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1967020520] [2023-08-31 02:59:40,785 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1967020520] provided 0 perfect and 1 imperfect interpolant sequences [2023-08-31 02:59:40,785 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1149739958] [2023-08-31 02:59:40,786 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-08-31 02:59:40,786 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-31 02:59:40,786 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-08-31 02:59:40,787 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-08-31 02:59:40,789 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-08-31 02:59:40,894 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-08-31 02:59:40,894 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-08-31 02:59:40,896 INFO L263 TraceCheckSpWp]: Trace formula consists of 249 conjuncts, 47 conjunts are in the unsatisfiable core [2023-08-31 02:59:40,900 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-08-31 02:59:40,913 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-08-31 02:59:40,914 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-08-31 02:59:40,923 INFO L321 Elim1Store]: treesize reduction 11, result has 45.0 percent of original size [2023-08-31 02:59:40,924 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 1 case distinctions, treesize of input 12 treesize of output 20 [2023-08-31 02:59:40,982 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-08-31 02:59:41,032 INFO L321 Elim1Store]: treesize reduction 4, result has 50.0 percent of original size [2023-08-31 02:59:41,032 INFO L350 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 11 treesize of output 11 [2023-08-31 02:59:41,098 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2023-08-31 02:59:41,139 INFO L350 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 6 treesize of output 5 [2023-08-31 02:59:41,304 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-08-31 02:59:41,314 INFO L321 Elim1Store]: treesize reduction 19, result has 32.1 percent of original size [2023-08-31 02:59:41,315 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 37 treesize of output 44 [2023-08-31 02:59:41,325 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 27 treesize of output 15 [2023-08-31 02:59:41,471 INFO L350 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 23 treesize of output 7 [2023-08-31 02:59:41,498 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-31 02:59:41,499 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-08-31 02:59:42,246 INFO L321 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-08-31 02:59:42,246 INFO L350 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 1 new quantified variables, introduced 1 case distinctions, treesize of input 117 treesize of output 81 [2023-08-31 02:59:42,274 INFO L321 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-08-31 02:59:42,275 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 2188 treesize of output 1978 [2023-08-31 02:59:42,372 INFO L321 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-08-31 02:59:42,372 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 1140 treesize of output 1060 [2023-08-31 02:59:42,424 INFO L321 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-08-31 02:59:42,425 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 1020 treesize of output 820 [2023-08-31 02:59:42,457 INFO L350 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 566 treesize of output 470 [2023-08-31 02:59:48,713 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 3 refuted. 1 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-31 02:59:48,713 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1149739958] provided 0 perfect and 2 imperfect interpolant sequences [2023-08-31 02:59:48,714 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-08-31 02:59:48,714 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 11, 11] total 30 [2023-08-31 02:59:48,714 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [653176858] [2023-08-31 02:59:48,714 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-08-31 02:59:48,714 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 32 states [2023-08-31 02:59:48,715 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-31 02:59:48,715 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2023-08-31 02:59:48,716 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=177, Invalid=803, Unknown=12, NotChecked=0, Total=992 [2023-08-31 02:59:49,439 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 78 out of 352 [2023-08-31 02:59:49,441 INFO L100 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 139 places, 274 transitions, 2813 flow. Second operand has 32 states, 32 states have (on average 80.0625) internal successors, (2562), 32 states have internal predecessors, (2562), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 02:59:49,442 INFO L109 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-31 02:59:49,442 INFO L110 encePairwiseOnDemand]: Number of universal subtrahend loopers: 78 of 352 [2023-08-31 02:59:49,442 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-31 02:59:57,221 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0, 1] [2023-08-31 02:59:57,324 WARN L839 $PredicateComparison]: unable to prove that (and (forall ((v_ArrVal_219 (Array Int Int))) (< c_~v_old~0 (+ (select (select (store |c_#memory_int| |c_ULTIMATE.start_main_~#t2~0#1.base| v_ArrVal_219) c_~queue~0.base) (+ (* c_~start~0 4) c_~queue~0.offset)) 1))) (not (= (mod c_~ok~0 256) 0)) (= c_~ok~0 1)) is different from false [2023-08-31 02:59:59,523 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0, 1] [2023-08-31 03:00:06,598 INFO L130 PetriNetUnfolder]: 3148/5231 cut-off events. [2023-08-31 03:00:06,598 INFO L131 PetriNetUnfolder]: For 95188/95188 co-relation queries the response was YES. [2023-08-31 03:00:06,633 INFO L83 FinitePrefix]: Finished finitePrefix Result has 39550 conditions, 5231 events. 3148/5231 cut-off events. For 95188/95188 co-relation queries the response was YES. Maximal size of possible extension queue 265. Compared 31615 event pairs, 373 based on Foata normal form. 3/5234 useless extension candidates. Maximal degree in co-relation 39485. Up to 1869 conditions per place. [2023-08-31 03:00:06,677 INFO L137 encePairwiseOnDemand]: 336/352 looper letters, 397 selfloop transitions, 320 changer transitions 32/749 dead transitions. [2023-08-31 03:00:06,677 INFO L142 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 169 places, 749 transitions, 10269 flow [2023-08-31 03:00:06,678 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 44 states. [2023-08-31 03:00:06,678 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 44 states. [2023-08-31 03:00:06,687 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 3731 transitions. [2023-08-31 03:00:06,689 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.24089617768595042 [2023-08-31 03:00:06,690 INFO L72 ComplementDD]: Start complementDD. Operand 44 states and 3731 transitions. [2023-08-31 03:00:06,690 INFO L73 IsDeterministic]: Start isDeterministic. Operand 44 states and 3731 transitions. [2023-08-31 03:00:06,692 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-31 03:00:06,692 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 44 states and 3731 transitions. [2023-08-31 03:00:06,701 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 45 states, 44 states have (on average 84.79545454545455) internal successors, (3731), 44 states have internal predecessors, (3731), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 03:00:06,721 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 45 states, 45 states have (on average 352.0) internal successors, (15840), 45 states have internal predecessors, (15840), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 03:00:06,725 INFO L81 ComplementDD]: Finished complementDD. Result has 45 states, 45 states have (on average 352.0) internal successors, (15840), 45 states have internal predecessors, (15840), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 03:00:06,725 INFO L175 Difference]: Start difference. First operand has 139 places, 274 transitions, 2813 flow. Second operand 44 states and 3731 transitions. [2023-08-31 03:00:06,725 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 169 places, 749 transitions, 10269 flow [2023-08-31 03:00:07,087 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 155 places, 749 transitions, 9474 flow, removed 382 selfloop flow, removed 14 redundant places. [2023-08-31 03:00:07,099 INFO L231 Difference]: Finished difference. Result has 185 places, 491 transitions, 6413 flow [2023-08-31 03:00:07,099 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=352, PETRI_DIFFERENCE_MINUEND_FLOW=2613, PETRI_DIFFERENCE_MINUEND_PLACES=112, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=274, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=128, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=75, PETRI_DIFFERENCE_SUBTRAHEND_STATES=44, PETRI_FLOW=6413, PETRI_PLACES=185, PETRI_TRANSITIONS=491} [2023-08-31 03:00:07,100 INFO L281 CegarLoopForPetriNet]: 25 programPoint places, 160 predicate places. [2023-08-31 03:00:07,100 INFO L495 AbstractCegarLoop]: Abstraction has has 185 places, 491 transitions, 6413 flow [2023-08-31 03:00:07,101 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 32 states, 32 states have (on average 80.0625) internal successors, (2562), 32 states have internal predecessors, (2562), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 03:00:07,101 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-31 03:00:07,101 INFO L208 CegarLoopForPetriNet]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-08-31 03:00:07,118 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2023-08-31 03:00:07,307 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-31 03:00:07,308 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES, ULTIMATE.startErr1INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES] === [2023-08-31 03:00:07,308 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-31 03:00:07,308 INFO L85 PathProgramCache]: Analyzing trace with hash -655038352, now seen corresponding path program 3 times [2023-08-31 03:00:07,308 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-31 03:00:07,308 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1441274096] [2023-08-31 03:00:07,308 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-31 03:00:07,309 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-31 03:00:07,376 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-31 03:00:08,409 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-08-31 03:00:08,409 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-31 03:00:08,409 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1441274096] [2023-08-31 03:00:08,410 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1441274096] provided 0 perfect and 1 imperfect interpolant sequences [2023-08-31 03:00:08,410 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [768081400] [2023-08-31 03:00:08,410 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-08-31 03:00:08,410 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-31 03:00:08,411 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-08-31 03:00:08,413 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-08-31 03:00:08,438 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-08-31 03:00:08,523 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2023-08-31 03:00:08,524 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-08-31 03:00:08,526 INFO L263 TraceCheckSpWp]: Trace formula consists of 258 conjuncts, 35 conjunts are in the unsatisfiable core [2023-08-31 03:00:08,528 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-08-31 03:00:08,748 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-08-31 03:00:08,761 INFO L321 Elim1Store]: treesize reduction 19, result has 32.1 percent of original size [2023-08-31 03:00:08,761 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 37 treesize of output 44 [2023-08-31 03:00:08,768 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 27 treesize of output 15 [2023-08-31 03:00:08,837 INFO L350 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 23 treesize of output 7 [2023-08-31 03:00:08,864 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2023-08-31 03:00:08,864 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-08-31 03:00:09,024 WARN L839 $PredicateComparison]: unable to prove that (and (forall ((v_ArrVal_262 (Array Int Int))) (< c_~v_old~0 (+ (select (select (store |c_#memory_int| |c_ULTIMATE.start_main_~#t2~0#1.base| v_ArrVal_262) c_~queue~0.base) (+ (* c_~start~0 4) c_~queue~0.offset)) 1))) (not (= (mod c_~ok~0 256) 0))) is different from false [2023-08-31 03:00:09,147 INFO L321 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-08-31 03:00:09,148 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 94 treesize of output 135 [2023-08-31 03:00:09,157 INFO L350 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 42 treesize of output 36 [2023-08-31 03:00:09,589 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 4 trivial. 1 not checked. [2023-08-31 03:00:09,589 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [768081400] provided 0 perfect and 2 imperfect interpolant sequences [2023-08-31 03:00:09,590 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-08-31 03:00:09,590 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10, 9] total 28 [2023-08-31 03:00:09,590 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1276286482] [2023-08-31 03:00:09,590 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-08-31 03:00:09,591 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 30 states [2023-08-31 03:00:09,591 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-31 03:00:09,592 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2023-08-31 03:00:09,592 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=159, Invalid=656, Unknown=1, NotChecked=54, Total=870 [2023-08-31 03:00:09,722 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 88 out of 352 [2023-08-31 03:00:09,730 INFO L100 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 185 places, 491 transitions, 6413 flow. Second operand has 30 states, 30 states have (on average 90.23333333333333) internal successors, (2707), 30 states have internal predecessors, (2707), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 03:00:09,731 INFO L109 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-31 03:00:09,731 INFO L110 encePairwiseOnDemand]: Number of universal subtrahend loopers: 88 of 352 [2023-08-31 03:00:09,731 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-31 03:00:12,087 INFO L130 PetriNetUnfolder]: 4361/7232 cut-off events. [2023-08-31 03:00:12,087 INFO L131 PetriNetUnfolder]: For 130211/130211 co-relation queries the response was YES. [2023-08-31 03:00:12,131 INFO L83 FinitePrefix]: Finished finitePrefix Result has 58119 conditions, 7232 events. 4361/7232 cut-off events. For 130211/130211 co-relation queries the response was YES. Maximal size of possible extension queue 372. Compared 46318 event pairs, 260 based on Foata normal form. 2/7234 useless extension candidates. Maximal degree in co-relation 58040. Up to 2543 conditions per place. [2023-08-31 03:00:12,187 INFO L137 encePairwiseOnDemand]: 339/352 looper letters, 527 selfloop transitions, 260 changer transitions 21/808 dead transitions. [2023-08-31 03:00:12,188 INFO L142 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 202 places, 808 transitions, 12430 flow [2023-08-31 03:00:12,188 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2023-08-31 03:00:12,189 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 20 states. [2023-08-31 03:00:12,193 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 1911 transitions. [2023-08-31 03:00:12,195 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.2714488636363636 [2023-08-31 03:00:12,195 INFO L72 ComplementDD]: Start complementDD. Operand 20 states and 1911 transitions. [2023-08-31 03:00:12,196 INFO L73 IsDeterministic]: Start isDeterministic. Operand 20 states and 1911 transitions. [2023-08-31 03:00:12,196 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-31 03:00:12,197 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 20 states and 1911 transitions. [2023-08-31 03:00:12,200 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 21 states, 20 states have (on average 95.55) internal successors, (1911), 20 states have internal predecessors, (1911), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 03:00:12,207 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 21 states, 21 states have (on average 352.0) internal successors, (7392), 21 states have internal predecessors, (7392), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 03:00:12,209 INFO L81 ComplementDD]: Finished complementDD. Result has 21 states, 21 states have (on average 352.0) internal successors, (7392), 21 states have internal predecessors, (7392), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 03:00:12,209 INFO L175 Difference]: Start difference. First operand has 185 places, 491 transitions, 6413 flow. Second operand 20 states and 1911 transitions. [2023-08-31 03:00:12,209 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 202 places, 808 transitions, 12430 flow [2023-08-31 03:00:12,997 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 193 places, 808 transitions, 11985 flow, removed 209 selfloop flow, removed 9 redundant places. [2023-08-31 03:00:13,016 INFO L231 Difference]: Finished difference. Result has 201 places, 595 transitions, 8298 flow [2023-08-31 03:00:13,017 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=352, PETRI_DIFFERENCE_MINUEND_FLOW=6070, PETRI_DIFFERENCE_MINUEND_PLACES=174, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=491, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=162, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=293, PETRI_DIFFERENCE_SUBTRAHEND_STATES=20, PETRI_FLOW=8298, PETRI_PLACES=201, PETRI_TRANSITIONS=595} [2023-08-31 03:00:13,018 INFO L281 CegarLoopForPetriNet]: 25 programPoint places, 176 predicate places. [2023-08-31 03:00:13,018 INFO L495 AbstractCegarLoop]: Abstraction has has 201 places, 595 transitions, 8298 flow [2023-08-31 03:00:13,019 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 30 states, 30 states have (on average 90.23333333333333) internal successors, (2707), 30 states have internal predecessors, (2707), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 03:00:13,019 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-31 03:00:13,019 INFO L208 CegarLoopForPetriNet]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-08-31 03:00:13,028 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2023-08-31 03:00:13,225 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-31 03:00:13,226 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES, ULTIMATE.startErr1INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES] === [2023-08-31 03:00:13,226 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-31 03:00:13,226 INFO L85 PathProgramCache]: Analyzing trace with hash 747110922, now seen corresponding path program 4 times [2023-08-31 03:00:13,226 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-31 03:00:13,226 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [691450211] [2023-08-31 03:00:13,227 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-31 03:00:13,227 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-31 03:00:13,310 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-31 03:00:13,450 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 4 proven. 1 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2023-08-31 03:00:13,451 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-31 03:00:13,451 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [691450211] [2023-08-31 03:00:13,451 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [691450211] provided 0 perfect and 1 imperfect interpolant sequences [2023-08-31 03:00:13,451 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1128221740] [2023-08-31 03:00:13,451 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-08-31 03:00:13,451 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-31 03:00:13,452 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-08-31 03:00:13,453 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-08-31 03:00:13,455 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-08-31 03:00:13,549 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-08-31 03:00:13,549 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-08-31 03:00:13,551 INFO L263 TraceCheckSpWp]: Trace formula consists of 265 conjuncts, 8 conjunts are in the unsatisfiable core [2023-08-31 03:00:13,552 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-08-31 03:00:13,579 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 4 proven. 1 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2023-08-31 03:00:13,580 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-08-31 03:00:13,669 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 3 proven. 2 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2023-08-31 03:00:13,669 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1128221740] provided 0 perfect and 2 imperfect interpolant sequences [2023-08-31 03:00:13,670 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-08-31 03:00:13,670 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 3, 4] total 9 [2023-08-31 03:00:13,671 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1220274405] [2023-08-31 03:00:13,672 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-08-31 03:00:13,672 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2023-08-31 03:00:13,672 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-31 03:00:13,673 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2023-08-31 03:00:13,673 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=39, Invalid=51, Unknown=0, NotChecked=0, Total=90 [2023-08-31 03:00:13,714 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 148 out of 352 [2023-08-31 03:00:13,715 INFO L100 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 201 places, 595 transitions, 8298 flow. Second operand has 10 states, 10 states have (on average 153.0) internal successors, (1530), 10 states have internal predecessors, (1530), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 03:00:13,715 INFO L109 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-31 03:00:13,715 INFO L110 encePairwiseOnDemand]: Number of universal subtrahend loopers: 148 of 352 [2023-08-31 03:00:13,715 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-31 03:00:15,909 INFO L130 PetriNetUnfolder]: 5790/9749 cut-off events. [2023-08-31 03:00:15,909 INFO L131 PetriNetUnfolder]: For 223393/223393 co-relation queries the response was YES. [2023-08-31 03:00:15,960 INFO L83 FinitePrefix]: Finished finitePrefix Result has 84291 conditions, 9749 events. 5790/9749 cut-off events. For 223393/223393 co-relation queries the response was YES. Maximal size of possible extension queue 379. Compared 64632 event pairs, 609 based on Foata normal form. 240/9989 useless extension candidates. Maximal degree in co-relation 84195. Up to 3285 conditions per place. [2023-08-31 03:00:16,015 INFO L137 encePairwiseOnDemand]: 346/352 looper letters, 600 selfloop transitions, 163 changer transitions 62/825 dead transitions. [2023-08-31 03:00:16,016 INFO L142 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 206 places, 825 transitions, 13115 flow [2023-08-31 03:00:16,016 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2023-08-31 03:00:16,017 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 7 states. [2023-08-31 03:00:16,018 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 1114 transitions. [2023-08-31 03:00:16,019 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.45211038961038963 [2023-08-31 03:00:16,019 INFO L72 ComplementDD]: Start complementDD. Operand 7 states and 1114 transitions. [2023-08-31 03:00:16,019 INFO L73 IsDeterministic]: Start isDeterministic. Operand 7 states and 1114 transitions. [2023-08-31 03:00:16,020 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-31 03:00:16,020 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 7 states and 1114 transitions. [2023-08-31 03:00:16,023 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 8 states, 7 states have (on average 159.14285714285714) internal successors, (1114), 7 states have internal predecessors, (1114), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 03:00:16,025 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 8 states, 8 states have (on average 352.0) internal successors, (2816), 8 states have internal predecessors, (2816), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 03:00:16,026 INFO L81 ComplementDD]: Finished complementDD. Result has 8 states, 8 states have (on average 352.0) internal successors, (2816), 8 states have internal predecessors, (2816), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 03:00:16,026 INFO L175 Difference]: Start difference. First operand has 201 places, 595 transitions, 8298 flow. Second operand 7 states and 1114 transitions. [2023-08-31 03:00:16,026 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 206 places, 825 transitions, 13115 flow [2023-08-31 03:00:16,963 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 200 places, 825 transitions, 12977 flow, removed 49 selfloop flow, removed 6 redundant places. [2023-08-31 03:00:16,978 INFO L231 Difference]: Finished difference. Result has 204 places, 580 transitions, 8728 flow [2023-08-31 03:00:16,979 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=352, PETRI_DIFFERENCE_MINUEND_FLOW=6983, PETRI_DIFFERENCE_MINUEND_PLACES=194, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=509, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=104, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=358, PETRI_DIFFERENCE_SUBTRAHEND_STATES=7, PETRI_FLOW=8728, PETRI_PLACES=204, PETRI_TRANSITIONS=580} [2023-08-31 03:00:16,979 INFO L281 CegarLoopForPetriNet]: 25 programPoint places, 179 predicate places. [2023-08-31 03:00:16,980 INFO L495 AbstractCegarLoop]: Abstraction has has 204 places, 580 transitions, 8728 flow [2023-08-31 03:00:16,980 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 153.0) internal successors, (1530), 10 states have internal predecessors, (1530), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 03:00:16,980 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-31 03:00:16,980 INFO L208 CegarLoopForPetriNet]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-08-31 03:00:16,989 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2023-08-31 03:00:17,185 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-31 03:00:17,186 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES, ULTIMATE.startErr1INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES] === [2023-08-31 03:00:17,186 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-31 03:00:17,187 INFO L85 PathProgramCache]: Analyzing trace with hash -2123166330, now seen corresponding path program 5 times [2023-08-31 03:00:17,187 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-31 03:00:17,187 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1718499409] [2023-08-31 03:00:17,187 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-31 03:00:17,187 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-31 03:00:17,269 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-31 03:00:19,245 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-08-31 03:00:19,245 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-31 03:00:19,245 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1718499409] [2023-08-31 03:00:19,245 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1718499409] provided 0 perfect and 1 imperfect interpolant sequences [2023-08-31 03:00:19,246 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [718036257] [2023-08-31 03:00:19,246 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2023-08-31 03:00:19,246 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-31 03:00:19,246 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-08-31 03:00:19,248 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-08-31 03:00:19,249 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2023-08-31 03:00:19,354 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 3 check-sat command(s) [2023-08-31 03:00:19,354 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-08-31 03:00:19,357 INFO L263 TraceCheckSpWp]: Trace formula consists of 276 conjuncts, 80 conjunts are in the unsatisfiable core [2023-08-31 03:00:19,363 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-08-31 03:00:19,381 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-08-31 03:00:19,382 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-08-31 03:00:19,390 INFO L321 Elim1Store]: treesize reduction 15, result has 25.0 percent of original size [2023-08-31 03:00:19,391 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 1 case distinctions, treesize of input 12 treesize of output 16 [2023-08-31 03:00:19,582 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-08-31 03:00:19,636 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-08-31 03:00:19,637 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-08-31 03:00:19,654 INFO L321 Elim1Store]: treesize reduction 20, result has 39.4 percent of original size [2023-08-31 03:00:19,654 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 4 select indices, 4 select index equivalence classes, 2 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 4 case distinctions, treesize of input 21 treesize of output 25 [2023-08-31 03:00:19,739 INFO L350 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 11 treesize of output 7 [2023-08-31 03:00:19,811 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 16 [2023-08-31 03:00:19,955 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 16 [2023-08-31 03:00:20,266 INFO L321 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-08-31 03:00:20,267 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 1 case distinctions, treesize of input 35 treesize of output 20 [2023-08-31 03:00:20,487 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 0 proven. 13 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-31 03:00:20,487 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-08-31 03:00:22,406 INFO L321 Elim1Store]: treesize reduction 23, result has 60.3 percent of original size [2023-08-31 03:00:22,407 INFO L350 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 1 new quantified variables, introduced 2 case distinctions, treesize of input 94 treesize of output 65 [2023-08-31 03:00:22,428 INFO L321 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-08-31 03:00:22,428 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 417 treesize of output 395 [2023-08-31 03:00:22,444 INFO L321 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-08-31 03:00:22,445 INFO L350 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 334 treesize of output 309 [2023-08-31 03:00:22,462 INFO L321 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-08-31 03:00:22,462 INFO L350 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 294 treesize of output 229 [2023-08-31 03:00:22,706 INFO L321 Elim1Store]: treesize reduction 23, result has 60.3 percent of original size [2023-08-31 03:00:22,707 INFO L350 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 1 new quantified variables, introduced 2 case distinctions, treesize of input 146 treesize of output 84 [2023-08-31 03:00:22,788 INFO L321 Elim1Store]: treesize reduction 44, result has 65.9 percent of original size [2023-08-31 03:00:22,789 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 5 select indices, 5 select index equivalence classes, 0 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 10 case distinctions, treesize of input 1010 treesize of output 926 [2023-08-31 03:00:22,835 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-08-31 03:00:22,843 INFO L321 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-08-31 03:00:22,843 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 366 treesize of output 334 [2023-08-31 03:00:22,860 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-08-31 03:00:22,868 INFO L321 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-08-31 03:00:22,868 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 331 treesize of output 253 [2023-08-31 03:00:24,426 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 0 proven. 12 refuted. 1 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-31 03:00:24,426 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [718036257] provided 0 perfect and 2 imperfect interpolant sequences [2023-08-31 03:00:24,426 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-08-31 03:00:24,426 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 15, 15] total 43 [2023-08-31 03:00:24,427 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1659892466] [2023-08-31 03:00:24,427 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-08-31 03:00:24,427 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 45 states [2023-08-31 03:00:24,428 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-31 03:00:24,428 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 45 interpolants. [2023-08-31 03:00:24,429 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=291, Invalid=1680, Unknown=9, NotChecked=0, Total=1980 [2023-08-31 03:00:26,426 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 77 out of 352 [2023-08-31 03:00:26,428 INFO L100 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 204 places, 580 transitions, 8728 flow. Second operand has 45 states, 45 states have (on average 78.66666666666667) internal successors, (3540), 45 states have internal predecessors, (3540), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 03:00:26,428 INFO L109 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-31 03:00:26,429 INFO L110 encePairwiseOnDemand]: Number of universal subtrahend loopers: 77 of 352 [2023-08-31 03:00:26,429 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-31 03:00:31,958 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2023-08-31 03:00:33,971 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2023-08-31 03:00:35,983 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2023-08-31 03:00:37,992 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2023-08-31 03:00:40,000 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2023-08-31 03:00:52,992 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2023-08-31 03:00:54,995 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2023-08-31 03:00:57,006 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2023-08-31 03:00:59,015 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2023-08-31 03:01:11,260 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2023-08-31 03:01:12,415 WARN L839 $PredicateComparison]: unable to prove that (let ((.cse1 (+ (* c_~i~0 4) |c_ULTIMATE.start_create_fresh_int_array_~arr~0#1.offset|))) (and (or (not (= (mod c_~ok~0 256) 0)) (forall ((v_ArrVal_359 (Array Int Int)) (~end~0 Int) (v_ArrVal_360 (Array Int Int))) (or (< ~end~0 0) (not (let ((.cse0 (store (store |c_#memory_int| |c_ULTIMATE.start_main_~#t1~0#1.base| v_ArrVal_359) |c_ULTIMATE.start_main_~#t2~0#1.base| v_ArrVal_360))) (= (select (select .cse0 |c_ULTIMATE.start_create_fresh_int_array_~arr~0#1.base|) .cse1) (select (select .cse0 c_~queue~0.base) (+ c_~queue~0.offset (* ~end~0 4)))))) (< c_~n~0 (+ ~end~0 1))))) (<= c_~v_old~0 c_~new~0) (forall ((v_ArrVal_359 (Array Int Int)) (~end~0 Int) (v_ArrVal_360 (Array Int Int)) (~start~0 Int)) (let ((.cse3 (store (store |c_#memory_int| |c_ULTIMATE.start_main_~#t1~0#1.base| v_ArrVal_359) |c_ULTIMATE.start_main_~#t2~0#1.base| v_ArrVal_360))) (let ((.cse2 (select .cse3 c_~queue~0.base))) (or (< (select (select |c_#memory_int| |c_ULTIMATE.start_create_fresh_int_array_~arr~0#1.base|) |c_ULTIMATE.start_create_fresh_int_array_~arr~0#1.offset|) (+ (select .cse2 (+ c_~queue~0.offset (* ~start~0 4))) 1)) (< ~start~0 0) (< ~start~0 ~end~0) (<= (+ ~end~0 1) ~start~0) (not (= (select (select .cse3 |c_ULTIMATE.start_create_fresh_int_array_~arr~0#1.base|) .cse1) (select .cse2 (+ c_~queue~0.offset (* ~end~0 4))))) (<= c_~n~0 ~start~0))))) (= c_~ok~0 1))) is different from false [2023-08-31 03:01:15,050 WARN L839 $PredicateComparison]: unable to prove that (let ((.cse1 (= c_~ok~0 1)) (.cse4 (not (= (mod c_~ok~0 256) 0))) (.cse3 (+ c_~A~0.offset (* c_~i~0 4)))) (and (let ((.cse0 (= |c_thread2Thread1of1ForFork0_~cond~0#1| 1))) (or (and (or .cse0 (= |c_thread2Thread1of1ForFork0_~cond~0#1| 0)) .cse1) (and (= c_~ok~0 0) .cse0))) (<= c_~v_old~0 c_~new~0) .cse1 (or (forall ((~end~0 Int) (v_ArrVal_360 (Array Int Int))) (or (< ~end~0 0) (not (let ((.cse2 (store |c_#memory_int| |c_ULTIMATE.start_main_~#t2~0#1.base| v_ArrVal_360))) (= (select (select .cse2 c_~A~0.base) .cse3) (select (select .cse2 c_~queue~0.base) (+ c_~queue~0.offset (* ~end~0 4)))))) (< c_~n~0 (+ ~end~0 1)))) .cse4) (or (let ((.cse5 (select |c_#memory_int| c_~queue~0.base)) (.cse6 (select (select |c_#memory_int| c_~A~0.base) .cse3))) (and (forall ((~end~0 Int)) (or (not (= (select .cse5 (+ c_~queue~0.offset (* ~end~0 4))) .cse6)) (forall ((~start~0 Int)) (or (< c_~v_old~0 (+ (select .cse5 (+ c_~queue~0.offset (* ~start~0 4))) 1)) (< ~start~0 0) (< ~start~0 ~end~0) (<= (+ ~end~0 1) ~start~0) (<= c_~n~0 ~start~0))))) (or (forall ((~end~0 Int)) (or (not (= (select .cse5 (+ c_~queue~0.offset (* ~end~0 4))) .cse6)) (< ~end~0 0) (< c_~n~0 (+ ~end~0 1)))) .cse4))) (<= c_~N~0 c_~i~0)) (forall ((~end~0 Int) (v_ArrVal_360 (Array Int Int))) (let ((.cse7 (store |c_#memory_int| |c_ULTIMATE.start_main_~#t2~0#1.base| v_ArrVal_360))) (let ((.cse8 (select .cse7 c_~queue~0.base))) (or (not (= (select (select .cse7 c_~A~0.base) .cse3) (select .cse8 (+ c_~queue~0.offset (* ~end~0 4))))) (forall ((~start~0 Int)) (or (< c_~v_old~0 (+ (select .cse8 (+ c_~queue~0.offset (* ~start~0 4))) 1)) (< ~start~0 0) (< ~start~0 ~end~0) (<= (+ ~end~0 1) ~start~0) (<= c_~n~0 ~start~0))))))))) is different from false [2023-08-31 03:01:34,650 INFO L130 PetriNetUnfolder]: 15591/27101 cut-off events. [2023-08-31 03:01:34,651 INFO L131 PetriNetUnfolder]: For 637435/637435 co-relation queries the response was YES. [2023-08-31 03:01:34,908 INFO L83 FinitePrefix]: Finished finitePrefix Result has 246187 conditions, 27101 events. 15591/27101 cut-off events. For 637435/637435 co-relation queries the response was YES. Maximal size of possible extension queue 898. Compared 217599 event pairs, 359 based on Foata normal form. 49/27150 useless extension candidates. Maximal degree in co-relation 242310. Up to 8716 conditions per place. [2023-08-31 03:01:35,282 INFO L137 encePairwiseOnDemand]: 333/352 looper letters, 1051 selfloop transitions, 1675 changer transitions 242/2968 dead transitions. [2023-08-31 03:01:35,282 INFO L142 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 356 places, 2968 transitions, 50171 flow [2023-08-31 03:01:35,283 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 153 states. [2023-08-31 03:01:35,283 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 153 states. [2023-08-31 03:01:35,304 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 153 states to 153 states and 12576 transitions. [2023-08-31 03:01:35,309 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.23351158645276293 [2023-08-31 03:01:35,310 INFO L72 ComplementDD]: Start complementDD. Operand 153 states and 12576 transitions. [2023-08-31 03:01:35,310 INFO L73 IsDeterministic]: Start isDeterministic. Operand 153 states and 12576 transitions. [2023-08-31 03:01:35,318 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-31 03:01:35,318 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 153 states and 12576 transitions. [2023-08-31 03:01:35,337 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 154 states, 153 states have (on average 82.19607843137256) internal successors, (12576), 153 states have internal predecessors, (12576), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 03:01:35,380 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 154 states, 154 states have (on average 352.0) internal successors, (54208), 154 states have internal predecessors, (54208), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 03:01:35,395 INFO L81 ComplementDD]: Finished complementDD. Result has 154 states, 154 states have (on average 352.0) internal successors, (54208), 154 states have internal predecessors, (54208), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 03:01:35,395 INFO L175 Difference]: Start difference. First operand has 204 places, 580 transitions, 8728 flow. Second operand 153 states and 12576 transitions. [2023-08-31 03:01:35,395 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 356 places, 2968 transitions, 50171 flow [2023-08-31 03:01:39,792 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 356 places, 2968 transitions, 49693 flow, removed 239 selfloop flow, removed 0 redundant places. [2023-08-31 03:01:39,826 INFO L231 Difference]: Finished difference. Result has 418 places, 2050 transitions, 36959 flow [2023-08-31 03:01:39,827 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=352, PETRI_DIFFERENCE_MINUEND_FLOW=8658, PETRI_DIFFERENCE_MINUEND_PLACES=204, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=580, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=382, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=112, PETRI_DIFFERENCE_SUBTRAHEND_STATES=153, PETRI_FLOW=36959, PETRI_PLACES=418, PETRI_TRANSITIONS=2050} [2023-08-31 03:01:39,827 INFO L281 CegarLoopForPetriNet]: 25 programPoint places, 393 predicate places. [2023-08-31 03:01:39,827 INFO L495 AbstractCegarLoop]: Abstraction has has 418 places, 2050 transitions, 36959 flow [2023-08-31 03:01:39,828 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 45 states, 45 states have (on average 78.66666666666667) internal successors, (3540), 45 states have internal predecessors, (3540), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 03:01:39,828 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-31 03:01:39,828 INFO L208 CegarLoopForPetriNet]: trace histogram [5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-08-31 03:01:39,833 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2023-08-31 03:01:40,029 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-31 03:01:40,029 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES, ULTIMATE.startErr1INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES] === [2023-08-31 03:01:40,030 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-31 03:01:40,030 INFO L85 PathProgramCache]: Analyzing trace with hash 521903976, now seen corresponding path program 6 times [2023-08-31 03:01:40,030 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-31 03:01:40,030 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1938131091] [2023-08-31 03:01:40,030 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-31 03:01:40,030 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-31 03:01:40,096 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-31 03:01:41,954 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 0 proven. 18 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-08-31 03:01:41,954 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-31 03:01:41,954 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1938131091] [2023-08-31 03:01:41,955 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1938131091] provided 0 perfect and 1 imperfect interpolant sequences [2023-08-31 03:01:41,955 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1338768154] [2023-08-31 03:01:41,955 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2023-08-31 03:01:41,955 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-31 03:01:41,955 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-08-31 03:01:41,956 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-08-31 03:01:41,958 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2023-08-31 03:01:42,080 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 3 check-sat command(s) [2023-08-31 03:01:42,081 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-08-31 03:01:42,083 INFO L263 TraceCheckSpWp]: Trace formula consists of 267 conjuncts, 49 conjunts are in the unsatisfiable core [2023-08-31 03:01:42,094 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-08-31 03:01:42,117 INFO L321 Elim1Store]: treesize reduction 44, result has 20.0 percent of original size [2023-08-31 03:01:42,118 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 2 case distinctions, treesize of input 12 treesize of output 16 [2023-08-31 03:01:42,212 INFO L321 Elim1Store]: treesize reduction 16, result has 36.0 percent of original size [2023-08-31 03:01:42,212 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 16 treesize of output 18 [2023-08-31 03:01:42,250 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-08-31 03:01:42,287 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 16 [2023-08-31 03:01:42,361 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 16 [2023-08-31 03:01:42,456 INFO L321 Elim1Store]: treesize reduction 15, result has 6.3 percent of original size [2023-08-31 03:01:42,456 INFO L350 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 34 treesize of output 10 [2023-08-31 03:01:42,500 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2023-08-31 03:01:42,500 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-08-31 03:01:46,694 WARN L839 $PredicateComparison]: unable to prove that (let ((.cse1 (* c_~end~0 4)) (.cse3 (+ c_~A~0.offset (* c_~i~0 4)))) (and (forall ((~queue~0.base Int) (~queue~0.offset Int) (v_ArrVal_423 (Array Int Int))) (let ((.cse2 (store |c_#memory_int| |c_ULTIMATE.start_main_~#t2~0#1.base| v_ArrVal_423))) (let ((.cse0 (select .cse2 ~queue~0.base))) (or (not (= (select .cse0 (+ .cse1 ~queue~0.offset)) (select (select .cse2 c_~A~0.base) .cse3))) (< c_~v_old~0 (+ (select .cse0 (+ (* c_~start~0 4) ~queue~0.offset)) 1)))))) (or (not (= (mod c_~ok~0 256) 0)) (forall ((~queue~0.base Int) (~queue~0.offset Int) (v_ArrVal_423 (Array Int Int))) (not (let ((.cse4 (store |c_#memory_int| |c_ULTIMATE.start_main_~#t2~0#1.base| v_ArrVal_423))) (= (select (select .cse4 ~queue~0.base) (+ .cse1 ~queue~0.offset)) (select (select .cse4 c_~A~0.base) .cse3)))))))) is different from false [2023-08-31 03:01:46,751 WARN L839 $PredicateComparison]: unable to prove that (let ((.cse1 (+ (* c_~i~0 4) |c_ULTIMATE.start_create_fresh_int_array_~arr~0#1.offset|)) (.cse2 (* c_~end~0 4))) (and (or (not (= (mod c_~ok~0 256) 0)) (forall ((~queue~0.base Int) (~queue~0.offset Int) (v_ArrVal_423 (Array Int Int)) (v_ArrVal_422 (Array Int Int))) (not (let ((.cse0 (store (store |c_#memory_int| |c_ULTIMATE.start_main_~#t1~0#1.base| v_ArrVal_422) |c_ULTIMATE.start_main_~#t2~0#1.base| v_ArrVal_423))) (= (select (select .cse0 |c_ULTIMATE.start_create_fresh_int_array_~arr~0#1.base|) .cse1) (select (select .cse0 ~queue~0.base) (+ .cse2 ~queue~0.offset))))))) (forall ((~queue~0.base Int) (~queue~0.offset Int) (v_ArrVal_423 (Array Int Int)) (v_ArrVal_422 (Array Int Int))) (let ((.cse4 (store (store |c_#memory_int| |c_ULTIMATE.start_main_~#t1~0#1.base| v_ArrVal_422) |c_ULTIMATE.start_main_~#t2~0#1.base| v_ArrVal_423))) (let ((.cse3 (select .cse4 ~queue~0.base))) (or (< (select (select |c_#memory_int| |c_ULTIMATE.start_create_fresh_int_array_~arr~0#1.base|) |c_ULTIMATE.start_create_fresh_int_array_~arr~0#1.offset|) (+ (select .cse3 (+ (* c_~start~0 4) ~queue~0.offset)) 1)) (not (= (select (select .cse4 |c_ULTIMATE.start_create_fresh_int_array_~arr~0#1.base|) .cse1) (select .cse3 (+ .cse2 ~queue~0.offset)))))))))) is different from false [2023-08-31 03:01:46,763 INFO L321 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-08-31 03:01:46,763 INFO L350 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 2 case distinctions, treesize of input 99 treesize of output 74 [2023-08-31 03:01:46,776 INFO L321 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-08-31 03:01:46,776 INFO L350 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 547 treesize of output 535 [2023-08-31 03:01:46,818 INFO L321 Elim1Store]: treesize reduction 24, result has 65.2 percent of original size [2023-08-31 03:01:46,819 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 667 treesize of output 672 [2023-08-31 03:01:46,872 INFO L321 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-08-31 03:01:46,872 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 652 treesize of output 560 [2023-08-31 03:01:46,922 INFO L321 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-08-31 03:01:46,922 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 449 treesize of output 423 [2023-08-31 03:01:53,003 INFO L321 Elim1Store]: treesize reduction 608, result has 0.2 percent of original size [2023-08-31 03:01:53,004 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 11 select indices, 11 select index equivalence classes, 0 disjoint index pairs (out of 55 index pairs), introduced 11 new quantified variables, introduced 55 case distinctions, treesize of input 284 treesize of output 1 [2023-08-31 03:01:54,203 INFO L321 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-08-31 03:01:54,204 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 13 select indices, 13 select index equivalence classes, 0 disjoint index pairs (out of 78 index pairs), introduced 13 new quantified variables, introduced 78 case distinctions, treesize of input 286 treesize of output 1086 [2023-08-31 03:02:06,526 INFO L321 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-08-31 03:02:06,526 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 52 treesize of output 41 [2023-08-31 03:02:06,529 INFO L173 IndexEqualityManager]: detected equality via solver [2023-08-31 03:02:06,529 INFO L173 IndexEqualityManager]: detected equality via solver [2023-08-31 03:02:06,535 INFO L321 Elim1Store]: treesize reduction 14, result has 6.7 percent of original size [2023-08-31 03:02:06,536 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 186 treesize of output 138 [2023-08-31 03:02:06,718 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 15 trivial. 2 not checked. [2023-08-31 03:02:06,718 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1338768154] provided 0 perfect and 2 imperfect interpolant sequences [2023-08-31 03:02:06,719 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-08-31 03:02:06,719 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 8, 8] total 31 [2023-08-31 03:02:06,719 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1327378486] [2023-08-31 03:02:06,719 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-08-31 03:02:06,719 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 33 states [2023-08-31 03:02:06,720 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-31 03:02:06,720 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2023-08-31 03:02:06,720 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=166, Invalid=769, Unknown=3, NotChecked=118, Total=1056 [2023-08-31 03:02:07,005 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 89 out of 352 [2023-08-31 03:02:07,007 INFO L100 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 418 places, 2050 transitions, 36959 flow. Second operand has 33 states, 33 states have (on average 91.03030303030303) internal successors, (3004), 33 states have internal predecessors, (3004), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 03:02:07,007 INFO L109 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-31 03:02:07,007 INFO L110 encePairwiseOnDemand]: Number of universal subtrahend loopers: 89 of 352 [2023-08-31 03:02:07,007 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-31 03:02:14,981 WARN L222 SmtUtils]: Spent 7.32s on a formula simplification. DAG size of input: 89 DAG size of output: 67 (called from [L 376] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-08-31 03:02:16,591 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.59s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2023-08-31 03:02:18,604 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2023-08-31 03:02:20,634 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2023-08-31 03:02:21,811 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.16s for a HTC check with result VALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2023-08-31 03:02:37,072 INFO L130 PetriNetUnfolder]: 19396/32479 cut-off events. [2023-08-31 03:02:37,073 INFO L131 PetriNetUnfolder]: For 1228586/1228586 co-relation queries the response was YES. [2023-08-31 03:02:37,879 INFO L83 FinitePrefix]: Finished finitePrefix Result has 359547 conditions, 32479 events. 19396/32479 cut-off events. For 1228586/1228586 co-relation queries the response was YES. Maximal size of possible extension queue 1061. Compared 254309 event pairs, 2148 based on Foata normal form. 13/32492 useless extension candidates. Maximal degree in co-relation 359182. Up to 12155 conditions per place. [2023-08-31 03:02:38,112 INFO L137 encePairwiseOnDemand]: 340/352 looper letters, 1716 selfloop transitions, 966 changer transitions 39/2721 dead transitions. [2023-08-31 03:02:38,112 INFO L142 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 406 places, 2721 transitions, 54310 flow [2023-08-31 03:02:38,113 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2023-08-31 03:02:38,113 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 16 states. [2023-08-31 03:02:38,115 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 16 states to 16 states and 1515 transitions. [2023-08-31 03:02:38,116 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.26899857954545453 [2023-08-31 03:02:38,116 INFO L72 ComplementDD]: Start complementDD. Operand 16 states and 1515 transitions. [2023-08-31 03:02:38,116 INFO L73 IsDeterministic]: Start isDeterministic. Operand 16 states and 1515 transitions. [2023-08-31 03:02:38,117 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-31 03:02:38,117 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 16 states and 1515 transitions. [2023-08-31 03:02:38,119 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 17 states, 16 states have (on average 94.6875) internal successors, (1515), 16 states have internal predecessors, (1515), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 03:02:38,123 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 17 states, 17 states have (on average 352.0) internal successors, (5984), 17 states have internal predecessors, (5984), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 03:02:38,123 INFO L81 ComplementDD]: Finished complementDD. Result has 17 states, 17 states have (on average 352.0) internal successors, (5984), 17 states have internal predecessors, (5984), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 03:02:38,124 INFO L175 Difference]: Start difference. First operand has 418 places, 2050 transitions, 36959 flow. Second operand 16 states and 1515 transitions. [2023-08-31 03:02:38,124 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 406 places, 2721 transitions, 54310 flow [2023-08-31 03:02:53,439 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 378 places, 2721 transitions, 50884 flow, removed 1665 selfloop flow, removed 28 redundant places. [2023-08-31 03:02:53,480 INFO L231 Difference]: Finished difference. Result has 385 places, 2441 transitions, 45319 flow [2023-08-31 03:02:53,481 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=352, PETRI_DIFFERENCE_MINUEND_FLOW=34350, PETRI_DIFFERENCE_MINUEND_PLACES=363, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=2050, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=585, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=1118, PETRI_DIFFERENCE_SUBTRAHEND_STATES=16, PETRI_FLOW=45319, PETRI_PLACES=385, PETRI_TRANSITIONS=2441} [2023-08-31 03:02:53,482 INFO L281 CegarLoopForPetriNet]: 25 programPoint places, 360 predicate places. [2023-08-31 03:02:53,482 INFO L495 AbstractCegarLoop]: Abstraction has has 385 places, 2441 transitions, 45319 flow [2023-08-31 03:02:53,482 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 33 states, 33 states have (on average 91.03030303030303) internal successors, (3004), 33 states have internal predecessors, (3004), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 03:02:53,483 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-31 03:02:53,483 INFO L208 CegarLoopForPetriNet]: trace histogram [4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-08-31 03:02:53,488 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2023-08-31 03:02:53,683 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2023-08-31 03:02:53,684 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES, ULTIMATE.startErr1INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES] === [2023-08-31 03:02:53,684 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-31 03:02:53,684 INFO L85 PathProgramCache]: Analyzing trace with hash -173753521, now seen corresponding path program 1 times [2023-08-31 03:02:53,684 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-31 03:02:53,684 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1418534603] [2023-08-31 03:02:53,685 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-31 03:02:53,685 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-31 03:02:53,708 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-31 03:02:53,810 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 3 proven. 2 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2023-08-31 03:02:53,811 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-31 03:02:53,811 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1418534603] [2023-08-31 03:02:53,811 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1418534603] provided 0 perfect and 1 imperfect interpolant sequences [2023-08-31 03:02:53,811 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [884552634] [2023-08-31 03:02:53,811 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-31 03:02:53,812 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-31 03:02:53,812 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-08-31 03:02:53,813 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-08-31 03:02:53,820 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2023-08-31 03:02:53,917 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-31 03:02:53,918 INFO L263 TraceCheckSpWp]: Trace formula consists of 282 conjuncts, 8 conjunts are in the unsatisfiable core [2023-08-31 03:02:53,920 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-08-31 03:02:54,005 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 4 proven. 1 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2023-08-31 03:02:54,005 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-08-31 03:02:54,061 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 4 proven. 1 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2023-08-31 03:02:54,062 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [884552634] provided 0 perfect and 2 imperfect interpolant sequences [2023-08-31 03:02:54,062 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-08-31 03:02:54,062 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 6] total 14 [2023-08-31 03:02:54,062 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1194011506] [2023-08-31 03:02:54,062 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-08-31 03:02:54,063 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2023-08-31 03:02:54,063 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-31 03:02:54,063 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2023-08-31 03:02:54,063 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=66, Invalid=144, Unknown=0, NotChecked=0, Total=210 [2023-08-31 03:02:54,363 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 143 out of 352 [2023-08-31 03:02:54,364 INFO L100 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 385 places, 2441 transitions, 45319 flow. Second operand has 15 states, 15 states have (on average 145.53333333333333) internal successors, (2183), 15 states have internal predecessors, (2183), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 03:02:54,365 INFO L109 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-31 03:02:54,365 INFO L110 encePairwiseOnDemand]: Number of universal subtrahend loopers: 143 of 352 [2023-08-31 03:02:54,365 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-31 03:03:10,457 INFO L130 PetriNetUnfolder]: 17198/29568 cut-off events. [2023-08-31 03:03:10,457 INFO L131 PetriNetUnfolder]: For 1014762/1014988 co-relation queries the response was YES. [2023-08-31 03:03:10,815 INFO L83 FinitePrefix]: Finished finitePrefix Result has 318201 conditions, 29568 events. 17198/29568 cut-off events. For 1014762/1014988 co-relation queries the response was YES. Maximal size of possible extension queue 964. Compared 235484 event pairs, 2793 based on Foata normal form. 479/29977 useless extension candidates. Maximal degree in co-relation 314001. Up to 19182 conditions per place. [2023-08-31 03:03:11,047 INFO L137 encePairwiseOnDemand]: 344/352 looper letters, 1858 selfloop transitions, 191 changer transitions 445/2581 dead transitions. [2023-08-31 03:03:11,047 INFO L142 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 389 places, 2581 transitions, 53141 flow [2023-08-31 03:03:11,047 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2023-08-31 03:03:11,048 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 9 states. [2023-08-31 03:03:11,049 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 9 states to 9 states and 1352 transitions. [2023-08-31 03:03:11,050 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.42676767676767674 [2023-08-31 03:03:11,050 INFO L72 ComplementDD]: Start complementDD. Operand 9 states and 1352 transitions. [2023-08-31 03:03:11,051 INFO L73 IsDeterministic]: Start isDeterministic. Operand 9 states and 1352 transitions. [2023-08-31 03:03:11,051 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-31 03:03:11,051 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 9 states and 1352 transitions. [2023-08-31 03:03:11,054 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 10 states, 9 states have (on average 150.22222222222223) internal successors, (1352), 9 states have internal predecessors, (1352), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 03:03:11,056 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 10 states, 10 states have (on average 352.0) internal successors, (3520), 10 states have internal predecessors, (3520), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 03:03:11,057 INFO L81 ComplementDD]: Finished complementDD. Result has 10 states, 10 states have (on average 352.0) internal successors, (3520), 10 states have internal predecessors, (3520), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 03:03:11,057 INFO L175 Difference]: Start difference. First operand has 385 places, 2441 transitions, 45319 flow. Second operand 9 states and 1352 transitions. [2023-08-31 03:03:11,057 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 389 places, 2581 transitions, 53141 flow [2023-08-31 03:03:21,852 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 378 places, 2581 transitions, 52409 flow, removed 175 selfloop flow, removed 11 redundant places. [2023-08-31 03:03:21,894 INFO L231 Difference]: Finished difference. Result has 380 places, 2064 transitions, 38423 flow [2023-08-31 03:03:21,896 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=352, PETRI_DIFFERENCE_MINUEND_FLOW=40964, PETRI_DIFFERENCE_MINUEND_PLACES=370, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=2234, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=190, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=2043, PETRI_DIFFERENCE_SUBTRAHEND_STATES=9, PETRI_FLOW=38423, PETRI_PLACES=380, PETRI_TRANSITIONS=2064} [2023-08-31 03:03:21,897 INFO L281 CegarLoopForPetriNet]: 25 programPoint places, 355 predicate places. [2023-08-31 03:03:21,897 INFO L495 AbstractCegarLoop]: Abstraction has has 380 places, 2064 transitions, 38423 flow [2023-08-31 03:03:21,897 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 145.53333333333333) internal successors, (2183), 15 states have internal predecessors, (2183), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 03:03:21,897 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-31 03:03:21,898 INFO L208 CegarLoopForPetriNet]: trace histogram [4, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-08-31 03:03:21,903 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2023-08-31 03:03:22,102 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2023-08-31 03:03:22,103 INFO L420 AbstractCegarLoop]: === Iteration 14 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES, ULTIMATE.startErr1INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES] === [2023-08-31 03:03:22,103 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-31 03:03:22,103 INFO L85 PathProgramCache]: Analyzing trace with hash -1129861215, now seen corresponding path program 2 times [2023-08-31 03:03:22,103 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-31 03:03:22,103 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1815627030] [2023-08-31 03:03:22,104 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-31 03:03:22,104 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-31 03:03:22,147 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-31 03:03:22,527 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 3 proven. 3 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-08-31 03:03:22,528 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-31 03:03:22,528 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1815627030] [2023-08-31 03:03:22,528 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1815627030] provided 0 perfect and 1 imperfect interpolant sequences [2023-08-31 03:03:22,528 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [350415619] [2023-08-31 03:03:22,528 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-08-31 03:03:22,528 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-31 03:03:22,528 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-08-31 03:03:22,530 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-08-31 03:03:22,534 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2023-08-31 03:03:22,645 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-08-31 03:03:22,646 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-08-31 03:03:22,648 INFO L263 TraceCheckSpWp]: Trace formula consists of 291 conjuncts, 11 conjunts are in the unsatisfiable core [2023-08-31 03:03:22,649 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-08-31 03:03:22,700 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-08-31 03:03:22,701 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 16 [2023-08-31 03:03:22,726 INFO L350 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 15 treesize of output 7 [2023-08-31 03:03:22,739 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 3 proven. 0 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2023-08-31 03:03:22,739 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-08-31 03:03:22,739 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [350415619] provided 1 perfect and 0 imperfect interpolant sequences [2023-08-31 03:03:22,739 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-08-31 03:03:22,740 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [7] total 10 [2023-08-31 03:03:22,741 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1221510157] [2023-08-31 03:03:22,741 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-08-31 03:03:22,741 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2023-08-31 03:03:22,741 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-31 03:03:22,742 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2023-08-31 03:03:22,742 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=87, Unknown=0, NotChecked=0, Total=110 [2023-08-31 03:03:22,898 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 139 out of 352 [2023-08-31 03:03:22,899 INFO L100 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 380 places, 2064 transitions, 38423 flow. Second operand has 6 states, 6 states have (on average 142.83333333333334) internal successors, (857), 6 states have internal predecessors, (857), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 03:03:22,899 INFO L109 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-31 03:03:22,899 INFO L110 encePairwiseOnDemand]: Number of universal subtrahend loopers: 139 of 352 [2023-08-31 03:03:22,899 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-31 03:03:33,081 INFO L130 PetriNetUnfolder]: 13345/22527 cut-off events. [2023-08-31 03:03:33,081 INFO L131 PetriNetUnfolder]: For 766500/766691 co-relation queries the response was YES. [2023-08-31 03:03:33,561 INFO L83 FinitePrefix]: Finished finitePrefix Result has 243535 conditions, 22527 events. 13345/22527 cut-off events. For 766500/766691 co-relation queries the response was YES. Maximal size of possible extension queue 785. Compared 169444 event pairs, 1330 based on Foata normal form. 83/22562 useless extension candidates. Maximal degree in co-relation 243407. Up to 20337 conditions per place. [2023-08-31 03:03:33,705 INFO L137 encePairwiseOnDemand]: 344/352 looper letters, 1609 selfloop transitions, 214 changer transitions 3/1906 dead transitions. [2023-08-31 03:03:33,705 INFO L142 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 359 places, 1906 transitions, 39251 flow [2023-08-31 03:03:33,706 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-08-31 03:03:33,706 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 6 states. [2023-08-31 03:03:33,706 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 882 transitions. [2023-08-31 03:03:33,707 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.41761363636363635 [2023-08-31 03:03:33,707 INFO L72 ComplementDD]: Start complementDD. Operand 6 states and 882 transitions. [2023-08-31 03:03:33,707 INFO L73 IsDeterministic]: Start isDeterministic. Operand 6 states and 882 transitions. [2023-08-31 03:03:33,707 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-31 03:03:33,707 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 6 states and 882 transitions. [2023-08-31 03:03:33,708 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 7 states, 6 states have (on average 147.0) internal successors, (882), 6 states have internal predecessors, (882), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 03:03:33,709 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 7 states, 7 states have (on average 352.0) internal successors, (2464), 7 states have internal predecessors, (2464), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 03:03:33,709 INFO L81 ComplementDD]: Finished complementDD. Result has 7 states, 7 states have (on average 352.0) internal successors, (2464), 7 states have internal predecessors, (2464), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 03:03:33,709 INFO L175 Difference]: Start difference. First operand has 380 places, 2064 transitions, 38423 flow. Second operand 6 states and 882 transitions. [2023-08-31 03:03:33,709 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 359 places, 1906 transitions, 39251 flow [2023-08-31 03:03:39,285 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 335 places, 1906 transitions, 38368 flow, removed 272 selfloop flow, removed 24 redundant places. [2023-08-31 03:03:39,317 INFO L231 Difference]: Finished difference. Result has 337 places, 1802 transitions, 33458 flow [2023-08-31 03:03:39,318 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=352, PETRI_DIFFERENCE_MINUEND_FLOW=32203, PETRI_DIFFERENCE_MINUEND_PLACES=330, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=1770, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=181, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=1576, PETRI_DIFFERENCE_SUBTRAHEND_STATES=6, PETRI_FLOW=33458, PETRI_PLACES=337, PETRI_TRANSITIONS=1802} [2023-08-31 03:03:39,319 INFO L281 CegarLoopForPetriNet]: 25 programPoint places, 312 predicate places. [2023-08-31 03:03:39,319 INFO L495 AbstractCegarLoop]: Abstraction has has 337 places, 1802 transitions, 33458 flow [2023-08-31 03:03:39,319 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 142.83333333333334) internal successors, (857), 6 states have internal predecessors, (857), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 03:03:39,319 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-31 03:03:39,319 INFO L208 CegarLoopForPetriNet]: trace histogram [2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-08-31 03:03:39,324 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2023-08-31 03:03:39,520 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2023-08-31 03:03:39,520 INFO L420 AbstractCegarLoop]: === Iteration 15 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES, ULTIMATE.startErr1INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES] === [2023-08-31 03:03:39,520 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-31 03:03:39,521 INFO L85 PathProgramCache]: Analyzing trace with hash 946926226, now seen corresponding path program 7 times [2023-08-31 03:03:39,521 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-31 03:03:39,521 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1915319116] [2023-08-31 03:03:39,521 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-31 03:03:39,522 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-31 03:03:39,545 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-31 03:03:39,640 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 4 proven. 3 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2023-08-31 03:03:39,640 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-31 03:03:39,640 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1915319116] [2023-08-31 03:03:39,641 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1915319116] provided 0 perfect and 1 imperfect interpolant sequences [2023-08-31 03:03:39,641 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [615311402] [2023-08-31 03:03:39,641 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2023-08-31 03:03:39,641 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-31 03:03:39,641 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-08-31 03:03:39,642 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-08-31 03:03:39,645 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2023-08-31 03:03:39,756 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-31 03:03:39,758 INFO L263 TraceCheckSpWp]: Trace formula consists of 290 conjuncts, 8 conjunts are in the unsatisfiable core [2023-08-31 03:03:39,759 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-08-31 03:03:39,837 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 6 proven. 1 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2023-08-31 03:03:39,837 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-08-31 03:03:39,909 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 4 proven. 3 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2023-08-31 03:03:39,909 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [615311402] provided 0 perfect and 2 imperfect interpolant sequences [2023-08-31 03:03:39,909 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-08-31 03:03:39,909 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5, 5] total 11 [2023-08-31 03:03:39,909 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1146911391] [2023-08-31 03:03:39,909 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-08-31 03:03:39,910 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2023-08-31 03:03:39,910 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-08-31 03:03:39,910 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2023-08-31 03:03:39,910 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=42, Invalid=90, Unknown=0, NotChecked=0, Total=132 [2023-08-31 03:03:40,094 INFO L471 CegarLoopForPetriNet]: Number of universal loopers: 144 out of 352 [2023-08-31 03:03:40,096 INFO L100 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 337 places, 1802 transitions, 33458 flow. Second operand has 12 states, 12 states have (on average 147.91666666666666) internal successors, (1775), 12 states have internal predecessors, (1775), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 03:03:40,096 INFO L109 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2023-08-31 03:03:40,096 INFO L110 encePairwiseOnDemand]: Number of universal subtrahend loopers: 144 of 352 [2023-08-31 03:03:40,096 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2023-08-31 03:03:46,926 INFO L130 PetriNetUnfolder]: 10325/17651 cut-off events. [2023-08-31 03:03:46,926 INFO L131 PetriNetUnfolder]: For 537066/537256 co-relation queries the response was YES. [2023-08-31 03:03:47,078 INFO L83 FinitePrefix]: Finished finitePrefix Result has 185156 conditions, 17651 events. 10325/17651 cut-off events. For 537066/537256 co-relation queries the response was YES. Maximal size of possible extension queue 555. Compared 128328 event pairs, 3418 based on Foata normal form. 198/17809 useless extension candidates. Maximal degree in co-relation 185048. Up to 15577 conditions per place. [2023-08-31 03:03:47,372 INFO L137 encePairwiseOnDemand]: 348/352 looper letters, 1076 selfloop transitions, 3 changer transitions 421/1554 dead transitions. [2023-08-31 03:03:47,372 INFO L142 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 334 places, 1554 transitions, 31816 flow [2023-08-31 03:03:47,372 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-08-31 03:03:47,372 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 6 states. [2023-08-31 03:03:47,373 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 911 transitions. [2023-08-31 03:03:47,374 INFO L516 CegarLoopForPetriNet]: DFA transition density 0.43134469696969696 [2023-08-31 03:03:47,374 INFO L72 ComplementDD]: Start complementDD. Operand 6 states and 911 transitions. [2023-08-31 03:03:47,374 INFO L73 IsDeterministic]: Start isDeterministic. Operand 6 states and 911 transitions. [2023-08-31 03:03:47,374 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-08-31 03:03:47,374 INFO L117 ReachableStatesCopy]: Start reachableStatesCopy. Operand 6 states and 911 transitions. [2023-08-31 03:03:47,375 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends has 7 states, 6 states have (on average 151.83333333333334) internal successors, (911), 6 states have internal predecessors, (911), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 03:03:47,376 INFO L131 ReachableStatesCopy]: Finished reachableStatesCopy Result has 7 states, 7 states have (on average 352.0) internal successors, (2464), 7 states have internal predecessors, (2464), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 03:03:47,377 INFO L81 ComplementDD]: Finished complementDD. Result has 7 states, 7 states have (on average 352.0) internal successors, (2464), 7 states have internal predecessors, (2464), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 03:03:47,377 INFO L175 Difference]: Start difference. First operand has 337 places, 1802 transitions, 33458 flow. Second operand 6 states and 911 transitions. [2023-08-31 03:03:47,377 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 334 places, 1554 transitions, 31816 flow [2023-08-31 03:03:51,235 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 324 places, 1554 transitions, 30803 flow, removed 287 selfloop flow, removed 10 redundant places. [2023-08-31 03:03:51,254 INFO L231 Difference]: Finished difference. Result has 324 places, 1133 transitions, 20309 flow [2023-08-31 03:03:51,255 INFO L264 CegarLoopForPetriNet]: {PETRI_ALPHABET=352, PETRI_DIFFERENCE_MINUEND_FLOW=27152, PETRI_DIFFERENCE_MINUEND_PLACES=319, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=1510, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=3, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=1507, PETRI_DIFFERENCE_SUBTRAHEND_STATES=6, PETRI_FLOW=20309, PETRI_PLACES=324, PETRI_TRANSITIONS=1133} [2023-08-31 03:03:51,255 INFO L281 CegarLoopForPetriNet]: 25 programPoint places, 299 predicate places. [2023-08-31 03:03:51,255 INFO L495 AbstractCegarLoop]: Abstraction has has 324 places, 1133 transitions, 20309 flow [2023-08-31 03:03:51,256 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 147.91666666666666) internal successors, (1775), 12 states have internal predecessors, (1775), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-08-31 03:03:51,256 INFO L200 CegarLoopForPetriNet]: Found error trace [2023-08-31 03:03:51,256 INFO L208 CegarLoopForPetriNet]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-08-31 03:03:51,262 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2023-08-31 03:03:51,463 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2023-08-31 03:03:51,463 INFO L420 AbstractCegarLoop]: === Iteration 16 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES, ULTIMATE.startErr1INUSE_VIOLATIONSUFFICIENT_THREAD_INSTANCES] === [2023-08-31 03:03:51,463 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-08-31 03:03:51,463 INFO L85 PathProgramCache]: Analyzing trace with hash 933993740, now seen corresponding path program 8 times [2023-08-31 03:03:51,463 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-08-31 03:03:51,464 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [752783206] [2023-08-31 03:03:51,464 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-08-31 03:03:51,464 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-08-31 03:03:51,521 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-08-31 03:03:52,853 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 0 proven. 13 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2023-08-31 03:03:52,854 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-08-31 03:03:52,854 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [752783206] [2023-08-31 03:03:52,854 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [752783206] provided 0 perfect and 1 imperfect interpolant sequences [2023-08-31 03:03:52,854 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1051355301] [2023-08-31 03:03:52,854 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-08-31 03:03:52,854 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-08-31 03:03:52,854 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-08-31 03:03:52,857 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-08-31 03:03:52,864 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2023-08-31 03:03:52,969 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-08-31 03:03:52,969 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-08-31 03:03:52,971 INFO L263 TraceCheckSpWp]: Trace formula consists of 299 conjuncts, 47 conjunts are in the unsatisfiable core [2023-08-31 03:03:52,973 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2023-08-31 03:03:53,543 INFO L321 Elim1Store]: treesize reduction 41, result has 54.9 percent of original size [2023-08-31 03:03:53,544 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 82 treesize of output 65 [2023-08-31 03:03:53,610 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-08-31 03:03:53,610 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2023-08-31 03:03:55,488 INFO L321 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-08-31 03:03:55,489 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 13 select indices, 13 select index equivalence classes, 0 disjoint index pairs (out of 78 index pairs), introduced 13 new quantified variables, introduced 78 case distinctions, treesize of input 235 treesize of output 1259 [2023-08-31 03:11:04,723 WARN L222 SmtUtils]: Spent 6.95s on a formula simplification. DAG size of input: 1016 DAG size of output: 1076 (called from [L 800] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2023-08-31 03:11:12,567 WARN L222 SmtUtils]: Spent 6.92s on a formula simplification. DAG size of input: 1014 DAG size of output: 1087 (called from [L 800] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2023-08-31 03:11:24,278 WARN L222 SmtUtils]: Spent 10.73s on a formula simplification. DAG size of input: 1012 DAG size of output: 1482 (called from [L 800] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) Killed by 15