./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/recursified_nla-digbench/recursified_mannadiv.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version c7c6ca5d Calling Ultimate with: /root/.sdkman/candidates/java/11.0.12-open/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/recursified_nla-digbench/recursified_mannadiv.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 --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 305ef194ca8c72f4da0a6deb18ed40b72305718d65c18a21aa3fcb3830c499e5 --- Real Ultimate output --- This is Ultimate 0.2.5-?-c7c6ca5-m [2024-11-08 15:25:46,769 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-08 15:25:46,851 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-08 15:25:46,856 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-08 15:25:46,859 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-08 15:25:46,887 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-08 15:25:46,890 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-08 15:25:46,890 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-08 15:25:46,891 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-08 15:25:46,894 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-08 15:25:46,894 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-08 15:25:46,895 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-08 15:25:46,895 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-08 15:25:46,895 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-08 15:25:46,896 INFO L153 SettingsManager]: * Use SBE=true [2024-11-08 15:25:46,896 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-08 15:25:46,897 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-08 15:25:46,897 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-08 15:25:46,897 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-08 15:25:46,898 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-08 15:25:46,898 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-08 15:25:46,899 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-08 15:25:46,899 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-08 15:25:46,899 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-08 15:25:46,899 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-08 15:25:46,899 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-08 15:25:46,900 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-08 15:25:46,900 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-08 15:25:46,900 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-08 15:25:46,900 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-08 15:25:46,900 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-08 15:25:46,900 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-08 15:25:46,901 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-08 15:25:46,901 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-08 15:25:46,901 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-08 15:25:46,902 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-08 15:25:46,902 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-08 15:25:46,902 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-08 15:25:46,902 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-08 15:25:46,903 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-08 15:25:46,903 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-08 15:25:46,903 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-08 15:25:46,903 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 305ef194ca8c72f4da0a6deb18ed40b72305718d65c18a21aa3fcb3830c499e5 [2024-11-08 15:25:47,123 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-08 15:25:47,144 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-08 15:25:47,147 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-08 15:25:47,148 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-08 15:25:47,148 INFO L274 PluginConnector]: CDTParser initialized [2024-11-08 15:25:47,149 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursified_nla-digbench/recursified_mannadiv.c [2024-11-08 15:25:48,440 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-08 15:25:48,580 INFO L384 CDTParser]: Found 1 translation units. [2024-11-08 15:25:48,580 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursified_nla-digbench/recursified_mannadiv.c [2024-11-08 15:25:48,587 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/3ae1d6b4a/a5081931eb974aa88d0c9e078be21e3a/FLAGb8d30e7c4 [2024-11-08 15:25:48,598 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/3ae1d6b4a/a5081931eb974aa88d0c9e078be21e3a [2024-11-08 15:25:48,600 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-08 15:25:48,601 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-08 15:25:48,602 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-08 15:25:48,602 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-08 15:25:48,607 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-08 15:25:48,607 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.11 03:25:48" (1/1) ... [2024-11-08 15:25:48,608 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@58f0091c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 03:25:48, skipping insertion in model container [2024-11-08 15:25:48,608 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.11 03:25:48" (1/1) ... [2024-11-08 15:25:48,623 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-08 15:25:48,759 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursified_nla-digbench/recursified_mannadiv.c[1105,1118] [2024-11-08 15:25:48,775 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-08 15:25:48,785 INFO L200 MainTranslator]: Completed pre-run [2024-11-08 15:25:48,795 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursified_nla-digbench/recursified_mannadiv.c[1105,1118] [2024-11-08 15:25:48,810 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-08 15:25:48,826 INFO L204 MainTranslator]: Completed translation [2024-11-08 15:25:48,841 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 03:25:48 WrapperNode [2024-11-08 15:25:48,841 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-08 15:25:48,842 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-08 15:25:48,843 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-08 15:25:48,843 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-08 15:25:48,849 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 03:25:48" (1/1) ... [2024-11-08 15:25:48,858 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 03:25:48" (1/1) ... [2024-11-08 15:25:48,874 INFO L138 Inliner]: procedures = 16, calls = 57, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 65 [2024-11-08 15:25:48,875 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-08 15:25:48,876 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-08 15:25:48,876 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-08 15:25:48,876 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-08 15:25:48,884 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 03:25:48" (1/1) ... [2024-11-08 15:25:48,884 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 03:25:48" (1/1) ... [2024-11-08 15:25:48,887 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 03:25:48" (1/1) ... [2024-11-08 15:25:48,897 INFO L175 MemorySlicer]: Split 31 memory accesses to 6 slices as follows [2, 5, 7, 5, 7, 5]. 23 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2, 0, 0, 0, 0, 0]. The 10 writes are split as follows [0, 1, 3, 1, 3, 2]. [2024-11-08 15:25:48,898 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 03:25:48" (1/1) ... [2024-11-08 15:25:48,898 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 03:25:48" (1/1) ... [2024-11-08 15:25:48,904 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 03:25:48" (1/1) ... [2024-11-08 15:25:48,906 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 03:25:48" (1/1) ... [2024-11-08 15:25:48,907 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 03:25:48" (1/1) ... [2024-11-08 15:25:48,908 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 03:25:48" (1/1) ... [2024-11-08 15:25:48,910 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-08 15:25:48,910 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-08 15:25:48,911 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-08 15:25:48,911 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-08 15:25:48,911 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 03:25:48" (1/1) ... [2024-11-08 15:25:48,916 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-08 15:25:48,929 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 15:25:48,945 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-11-08 15:25:48,949 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-11-08 15:25:48,988 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-08 15:25:48,988 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-11-08 15:25:48,988 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-11-08 15:25:48,988 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-08 15:25:48,988 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2024-11-08 15:25:48,988 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2024-11-08 15:25:48,989 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#3 [2024-11-08 15:25:48,990 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#4 [2024-11-08 15:25:48,990 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#5 [2024-11-08 15:25:48,990 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2024-11-08 15:25:48,991 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2024-11-08 15:25:48,991 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2024-11-08 15:25:48,991 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#2 [2024-11-08 15:25:48,991 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#3 [2024-11-08 15:25:48,991 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#4 [2024-11-08 15:25:48,991 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#5 [2024-11-08 15:25:48,991 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_31_to_42_0 [2024-11-08 15:25:48,991 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_31_to_42_0 [2024-11-08 15:25:48,992 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-08 15:25:48,992 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-08 15:25:48,992 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2024-11-08 15:25:48,992 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2024-11-08 15:25:48,992 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#2 [2024-11-08 15:25:48,992 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#3 [2024-11-08 15:25:48,992 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#4 [2024-11-08 15:25:48,993 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#5 [2024-11-08 15:25:48,993 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-08 15:25:48,993 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-08 15:25:48,993 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2024-11-08 15:25:49,085 INFO L238 CfgBuilder]: Building ICFG [2024-11-08 15:25:49,089 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-08 15:25:49,262 INFO L? ?]: Removed 9 outVars from TransFormulas that were not future-live. [2024-11-08 15:25:49,262 INFO L287 CfgBuilder]: Performing block encoding [2024-11-08 15:25:49,276 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-08 15:25:49,276 INFO L316 CfgBuilder]: Removed 1 assume(true) statements. [2024-11-08 15:25:49,277 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 08.11 03:25:49 BoogieIcfgContainer [2024-11-08 15:25:49,277 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-08 15:25:49,278 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-08 15:25:49,278 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-08 15:25:49,281 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-08 15:25:49,281 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 08.11 03:25:48" (1/3) ... [2024-11-08 15:25:49,282 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@25542c56 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.11 03:25:49, skipping insertion in model container [2024-11-08 15:25:49,282 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 03:25:48" (2/3) ... [2024-11-08 15:25:49,282 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@25542c56 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.11 03:25:49, skipping insertion in model container [2024-11-08 15:25:49,282 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 08.11 03:25:49" (3/3) ... [2024-11-08 15:25:49,283 INFO L112 eAbstractionObserver]: Analyzing ICFG recursified_mannadiv.c [2024-11-08 15:25:49,299 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-08 15:25:49,299 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-08 15:25:49,341 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-08 15:25:49,347 INFO L333 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mAutomataTypeConcurrency=PETRI_NET, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopHeads, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP, mPorIndependenceSettings=[Lde.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings;@437ecb4a, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-08 15:25:49,347 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-08 15:25:49,351 INFO L276 IsEmpty]: Start isEmpty. Operand has 32 states, 21 states have (on average 1.2857142857142858) internal successors, (27), 23 states have internal predecessors, (27), 6 states have call successors, (6), 3 states have call predecessors, (6), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-08 15:25:49,356 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2024-11-08 15:25:49,357 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 15:25:49,357 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 15:25:49,358 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 15:25:49,361 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 15:25:49,361 INFO L85 PathProgramCache]: Analyzing trace with hash 1441555117, now seen corresponding path program 1 times [2024-11-08 15:25:49,368 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 15:25:49,368 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1248830731] [2024-11-08 15:25:49,368 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 15:25:49,369 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 15:25:49,474 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:25:49,540 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 15:25:49,542 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:25:49,549 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-08 15:25:49,554 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:25:49,561 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-08 15:25:49,562 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 15:25:49,562 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1248830731] [2024-11-08 15:25:49,562 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1248830731] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 15:25:49,563 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 15:25:49,563 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-08 15:25:49,564 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1018352840] [2024-11-08 15:25:49,564 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 15:25:49,568 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-08 15:25:49,568 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 15:25:49,583 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-08 15:25:49,584 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-08 15:25:49,585 INFO L87 Difference]: Start difference. First operand has 32 states, 21 states have (on average 1.2857142857142858) internal successors, (27), 23 states have internal predecessors, (27), 6 states have call successors, (6), 3 states have call predecessors, (6), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Second operand has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-08 15:25:49,599 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 15:25:49,600 INFO L93 Difference]: Finished difference Result 61 states and 80 transitions. [2024-11-08 15:25:49,601 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-08 15:25:49,603 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Word has length 21 [2024-11-08 15:25:49,603 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 15:25:49,608 INFO L225 Difference]: With dead ends: 61 [2024-11-08 15:25:49,608 INFO L226 Difference]: Without dead ends: 28 [2024-11-08 15:25:49,610 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-08 15:25:49,613 INFO L432 NwaCegarLoop]: 36 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 36 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-08 15:25:49,613 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 36 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-08 15:25:49,640 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 28 states. [2024-11-08 15:25:49,662 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 28 to 28. [2024-11-08 15:25:49,663 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 28 states, 18 states have (on average 1.1666666666666667) internal successors, (21), 20 states have internal predecessors, (21), 6 states have call successors, (6), 3 states have call predecessors, (6), 3 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2024-11-08 15:25:49,664 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28 states to 28 states and 32 transitions. [2024-11-08 15:25:49,686 INFO L78 Accepts]: Start accepts. Automaton has 28 states and 32 transitions. Word has length 21 [2024-11-08 15:25:49,690 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 15:25:49,690 INFO L471 AbstractCegarLoop]: Abstraction has 28 states and 32 transitions. [2024-11-08 15:25:49,691 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-08 15:25:49,691 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 32 transitions. [2024-11-08 15:25:49,692 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2024-11-08 15:25:49,693 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 15:25:49,693 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 15:25:49,693 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-08 15:25:49,693 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 15:25:49,694 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 15:25:49,694 INFO L85 PathProgramCache]: Analyzing trace with hash 554271793, now seen corresponding path program 1 times [2024-11-08 15:25:49,694 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 15:25:49,694 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [800555492] [2024-11-08 15:25:49,694 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 15:25:49,694 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 15:25:49,774 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 15:25:49,779 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [796319183] [2024-11-08 15:25:49,780 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 15:25:49,780 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 15:25:49,780 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 15:25:49,782 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 15:25:49,783 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-08 15:25:49,894 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:25:49,901 INFO L255 TraceCheckSpWp]: Trace formula consists of 184 conjuncts, 63 conjuncts are in the unsatisfiable core [2024-11-08 15:25:49,909 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 15:25:49,951 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-08 15:25:49,978 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-08 15:25:49,986 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2024-11-08 15:25:49,999 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-08 15:25:50,124 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-11-08 15:25:50,130 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2024-11-08 15:25:50,181 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-08 15:25:50,181 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-08 15:25:50,181 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 15:25:50,182 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [800555492] [2024-11-08 15:25:50,182 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 15:25:50,182 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [796319183] [2024-11-08 15:25:50,184 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [796319183] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 15:25:50,184 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 15:25:50,184 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2024-11-08 15:25:50,185 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [95745227] [2024-11-08 15:25:50,185 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 15:25:50,186 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-08 15:25:50,186 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 15:25:50,187 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-08 15:25:50,188 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2024-11-08 15:25:50,188 INFO L87 Difference]: Start difference. First operand 28 states and 32 transitions. Second operand has 8 states, 6 states have (on average 2.0) internal successors, (12), 6 states have internal predecessors, (12), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-08 15:25:50,362 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 15:25:50,362 INFO L93 Difference]: Finished difference Result 43 states and 49 transitions. [2024-11-08 15:25:50,363 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-11-08 15:25:50,363 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 6 states have (on average 2.0) internal successors, (12), 6 states have internal predecessors, (12), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 21 [2024-11-08 15:25:50,363 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 15:25:50,364 INFO L225 Difference]: With dead ends: 43 [2024-11-08 15:25:50,364 INFO L226 Difference]: Without dead ends: 41 [2024-11-08 15:25:50,365 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 23 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2024-11-08 15:25:50,367 INFO L432 NwaCegarLoop]: 21 mSDtfsCounter, 14 mSDsluCounter, 114 mSDsCounter, 0 mSdLazyCounter, 87 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 135 SdHoareTripleChecker+Invalid, 91 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 87 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-08 15:25:50,368 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 135 Invalid, 91 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 87 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-08 15:25:50,369 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2024-11-08 15:25:50,377 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 39. [2024-11-08 15:25:50,378 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 39 states, 26 states have (on average 1.1538461538461537) internal successors, (30), 28 states have internal predecessors, (30), 7 states have call successors, (7), 5 states have call predecessors, (7), 5 states have return successors, (7), 6 states have call predecessors, (7), 6 states have call successors, (7) [2024-11-08 15:25:50,379 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 44 transitions. [2024-11-08 15:25:50,380 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 44 transitions. Word has length 21 [2024-11-08 15:25:50,380 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 15:25:50,382 INFO L471 AbstractCegarLoop]: Abstraction has 39 states and 44 transitions. [2024-11-08 15:25:50,382 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 6 states have (on average 2.0) internal successors, (12), 6 states have internal predecessors, (12), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-08 15:25:50,382 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 44 transitions. [2024-11-08 15:25:50,383 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2024-11-08 15:25:50,383 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 15:25:50,383 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 15:25:50,396 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-08 15:25:50,584 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 15:25:50,584 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 15:25:50,585 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 15:25:50,585 INFO L85 PathProgramCache]: Analyzing trace with hash -730437634, now seen corresponding path program 1 times [2024-11-08 15:25:50,585 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 15:25:50,585 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1306857290] [2024-11-08 15:25:50,585 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 15:25:50,585 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 15:25:50,616 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 15:25:50,618 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [831518016] [2024-11-08 15:25:50,618 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 15:25:50,618 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 15:25:50,618 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 15:25:50,623 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 15:25:50,625 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-08 15:25:50,714 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:25:50,716 INFO L255 TraceCheckSpWp]: Trace formula consists of 207 conjuncts, 43 conjuncts are in the unsatisfiable core [2024-11-08 15:25:50,719 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 15:25:50,732 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-08 15:25:50,738 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-08 15:25:50,746 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2024-11-08 15:25:50,768 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-08 15:25:50,913 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2024-11-08 15:25:50,951 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-08 15:25:50,952 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-08 15:25:50,952 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 15:25:50,952 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1306857290] [2024-11-08 15:25:50,952 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 15:25:50,952 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [831518016] [2024-11-08 15:25:50,952 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [831518016] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 15:25:50,952 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 15:25:50,966 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [11] imperfect sequences [] total 11 [2024-11-08 15:25:50,966 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1727024176] [2024-11-08 15:25:50,966 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 15:25:50,967 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2024-11-08 15:25:50,967 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 15:25:50,967 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-11-08 15:25:50,967 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=88, Unknown=0, NotChecked=0, Total=110 [2024-11-08 15:25:50,968 INFO L87 Difference]: Start difference. First operand 39 states and 44 transitions. Second operand has 11 states, 9 states have (on average 2.111111111111111) internal successors, (19), 8 states have internal predecessors, (19), 4 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-08 15:25:51,212 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 15:25:51,212 INFO L93 Difference]: Finished difference Result 49 states and 53 transitions. [2024-11-08 15:25:51,213 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-08 15:25:51,213 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 9 states have (on average 2.111111111111111) internal successors, (19), 8 states have internal predecessors, (19), 4 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) Word has length 31 [2024-11-08 15:25:51,213 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 15:25:51,215 INFO L225 Difference]: With dead ends: 49 [2024-11-08 15:25:51,215 INFO L226 Difference]: Without dead ends: 39 [2024-11-08 15:25:51,215 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 36 GetRequests, 22 SyntacticMatches, 0 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 24 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=46, Invalid=194, Unknown=0, NotChecked=0, Total=240 [2024-11-08 15:25:51,216 INFO L432 NwaCegarLoop]: 14 mSDtfsCounter, 15 mSDsluCounter, 61 mSDsCounter, 0 mSdLazyCounter, 227 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 75 SdHoareTripleChecker+Invalid, 234 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 227 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-08 15:25:51,216 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 75 Invalid, 234 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 227 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-08 15:25:51,217 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2024-11-08 15:25:51,221 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 39. [2024-11-08 15:25:51,222 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 39 states, 26 states have (on average 1.1153846153846154) internal successors, (29), 27 states have internal predecessors, (29), 7 states have call successors, (7), 5 states have call predecessors, (7), 5 states have return successors, (7), 6 states have call predecessors, (7), 6 states have call successors, (7) [2024-11-08 15:25:51,223 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 43 transitions. [2024-11-08 15:25:51,223 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 43 transitions. Word has length 31 [2024-11-08 15:25:51,223 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 15:25:51,223 INFO L471 AbstractCegarLoop]: Abstraction has 39 states and 43 transitions. [2024-11-08 15:25:51,223 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 9 states have (on average 2.111111111111111) internal successors, (19), 8 states have internal predecessors, (19), 4 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-08 15:25:51,223 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 43 transitions. [2024-11-08 15:25:51,224 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2024-11-08 15:25:51,224 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 15:25:51,224 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 15:25:51,237 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-11-08 15:25:51,424 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2024-11-08 15:25:51,425 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 15:25:51,425 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 15:25:51,425 INFO L85 PathProgramCache]: Analyzing trace with hash 1523322128, now seen corresponding path program 1 times [2024-11-08 15:25:51,425 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 15:25:51,426 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [613254909] [2024-11-08 15:25:51,426 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 15:25:51,426 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 15:25:51,471 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 15:25:51,478 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [436476493] [2024-11-08 15:25:51,478 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 15:25:51,478 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 15:25:51,479 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 15:25:51,482 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 15:25:51,490 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-08 15:25:51,573 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:25:51,581 WARN L253 TraceCheckSpWp]: Trace formula consists of 270 conjuncts, 137 conjuncts are in the unsatisfiable core [2024-11-08 15:25:51,585 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 15:25:51,589 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-08 15:25:51,595 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-08 15:25:51,600 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-08 15:25:51,604 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-08 15:25:51,608 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2024-11-08 15:25:51,788 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 17 [2024-11-08 15:25:51,794 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-11-08 15:25:51,802 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-11-08 15:25:51,905 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 21 treesize of output 13 [2024-11-08 15:25:51,909 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 9 [2024-11-08 15:25:51,957 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-08 15:25:51,957 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 15:25:52,258 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 4 proven. 1 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-08 15:25:52,258 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 15:25:52,258 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [613254909] [2024-11-08 15:25:52,259 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 15:25:52,259 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [436476493] [2024-11-08 15:25:52,259 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [436476493] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 15:25:52,259 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-08 15:25:52,259 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11] total 19 [2024-11-08 15:25:52,259 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1477116215] [2024-11-08 15:25:52,259 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-08 15:25:52,260 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2024-11-08 15:25:52,260 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 15:25:52,260 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2024-11-08 15:25:52,260 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=56, Invalid=286, Unknown=0, NotChecked=0, Total=342 [2024-11-08 15:25:52,261 INFO L87 Difference]: Start difference. First operand 39 states and 43 transitions. Second operand has 19 states, 15 states have (on average 2.066666666666667) internal successors, (31), 14 states have internal predecessors, (31), 9 states have call successors, (10), 7 states have call predecessors, (10), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-08 15:25:52,783 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 15:25:52,784 INFO L93 Difference]: Finished difference Result 60 states and 73 transitions. [2024-11-08 15:25:52,784 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2024-11-08 15:25:52,784 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 15 states have (on average 2.066666666666667) internal successors, (31), 14 states have internal predecessors, (31), 9 states have call successors, (10), 7 states have call predecessors, (10), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) Word has length 32 [2024-11-08 15:25:52,784 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 15:25:52,785 INFO L225 Difference]: With dead ends: 60 [2024-11-08 15:25:52,785 INFO L226 Difference]: Without dead ends: 56 [2024-11-08 15:25:52,786 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 74 GetRequests, 42 SyntacticMatches, 3 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 127 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=167, Invalid=763, Unknown=0, NotChecked=0, Total=930 [2024-11-08 15:25:52,790 INFO L432 NwaCegarLoop]: 22 mSDtfsCounter, 63 mSDsluCounter, 158 mSDsCounter, 0 mSdLazyCounter, 198 mSolverCounterSat, 24 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 63 SdHoareTripleChecker+Valid, 180 SdHoareTripleChecker+Invalid, 222 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 24 IncrementalHoareTripleChecker+Valid, 198 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-08 15:25:52,792 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [63 Valid, 180 Invalid, 222 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [24 Valid, 198 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-08 15:25:52,792 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 56 states. [2024-11-08 15:25:52,800 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 56 to 52. [2024-11-08 15:25:52,800 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 52 states, 35 states have (on average 1.1142857142857143) internal successors, (39), 36 states have internal predecessors, (39), 9 states have call successors, (9), 7 states have call predecessors, (9), 7 states have return successors, (11), 8 states have call predecessors, (11), 8 states have call successors, (11) [2024-11-08 15:25:52,801 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52 states to 52 states and 59 transitions. [2024-11-08 15:25:52,801 INFO L78 Accepts]: Start accepts. Automaton has 52 states and 59 transitions. Word has length 32 [2024-11-08 15:25:52,801 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 15:25:52,801 INFO L471 AbstractCegarLoop]: Abstraction has 52 states and 59 transitions. [2024-11-08 15:25:52,801 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 15 states have (on average 2.066666666666667) internal successors, (31), 14 states have internal predecessors, (31), 9 states have call successors, (10), 7 states have call predecessors, (10), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-08 15:25:52,802 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 59 transitions. [2024-11-08 15:25:52,802 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2024-11-08 15:25:52,802 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 15:25:52,803 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 15:25:52,816 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2024-11-08 15:25:53,006 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 15:25:53,007 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 15:25:53,007 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 15:25:53,007 INFO L85 PathProgramCache]: Analyzing trace with hash -1572646312, now seen corresponding path program 1 times [2024-11-08 15:25:53,008 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 15:25:53,008 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [840543275] [2024-11-08 15:25:53,008 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 15:25:53,008 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 15:25:53,052 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 15:25:53,054 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [953597301] [2024-11-08 15:25:53,054 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 15:25:53,054 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 15:25:53,054 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 15:25:53,055 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 15:25:53,056 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-08 15:25:53,146 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:25:53,150 WARN L253 TraceCheckSpWp]: Trace formula consists of 295 conjuncts, 148 conjuncts are in the unsatisfiable core [2024-11-08 15:25:53,154 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 15:25:53,159 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-08 15:25:53,163 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-08 15:25:53,211 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-08 15:25:53,215 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-08 15:25:53,221 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2024-11-08 15:25:53,244 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-08 15:25:53,728 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 9 [2024-11-08 15:25:54,261 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-11-08 15:25:54,268 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 20 treesize of output 12 [2024-11-08 15:25:54,274 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-11-08 15:25:54,281 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 21 treesize of output 13 [2024-11-08 15:25:54,365 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-08 15:25:54,365 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 44 treesize of output 56 [2024-11-08 15:25:54,465 INFO L134 CoverageAnalysis]: Checked inductivity of 19 backedges. 4 proven. 14 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-08 15:25:54,465 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 15:25:55,295 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 36 treesize of output 28 [2024-11-08 15:25:55,740 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 36 treesize of output 28 [2024-11-08 15:25:55,914 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 69 treesize of output 61 [2024-11-08 15:25:55,920 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 61 treesize of output 57 [2024-11-08 15:25:55,929 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 57 treesize of output 53 [2024-11-08 15:25:59,955 WARN L851 $PredicateComparison]: unable to prove that (and (forall ((|v_func_to_recursive_line_31_to_42_0_#in~x2.offset_BEFORE_CALL_4| Int) (|v_func_to_recursive_line_31_to_42_0_#in~x1.base_BEFORE_CALL_4| Int) (|v_func_to_recursive_line_31_to_42_0_#in~x2.base_BEFORE_CALL_4| Int) (|v_func_to_recursive_line_31_to_42_0_#in~y2.offset_BEFORE_CALL_4| Int) (|v_func_to_recursive_line_31_to_42_0_#in~y1.base_BEFORE_CALL_4| Int) (|v_func_to_recursive_line_31_to_42_0_#in~y2.base_BEFORE_CALL_4| Int) (|v_func_to_recursive_line_31_to_42_0_#in~x1.offset_BEFORE_CALL_4| Int) (|v_func_to_recursive_line_31_to_42_0_#in~y1.offset_BEFORE_CALL_4| Int)) (let ((.cse1 (select (select |c_#memory_int#3| |v_func_to_recursive_line_31_to_42_0_#in~x1.base_BEFORE_CALL_4|) |v_func_to_recursive_line_31_to_42_0_#in~x1.offset_BEFORE_CALL_4|)) (.cse0 (select (select |c_#memory_int#1| |v_func_to_recursive_line_31_to_42_0_#in~x2.base_BEFORE_CALL_4|) |v_func_to_recursive_line_31_to_42_0_#in~x2.offset_BEFORE_CALL_4|))) (or (= (+ (select (select |c_#memory_int#4| |v_func_to_recursive_line_31_to_42_0_#in~y2.base_BEFORE_CALL_4|) |v_func_to_recursive_line_31_to_42_0_#in~y2.offset_BEFORE_CALL_4|) (* .cse0 (select (select |c_#memory_int#5| |v_func_to_recursive_line_31_to_42_0_#in~y1.base_BEFORE_CALL_4|) |v_func_to_recursive_line_31_to_42_0_#in~y1.offset_BEFORE_CALL_4|))) .cse1) (not (= .cse1 (+ (select (select |c_old(#memory_int#4)| |v_func_to_recursive_line_31_to_42_0_#in~y2.base_BEFORE_CALL_4|) |v_func_to_recursive_line_31_to_42_0_#in~y2.offset_BEFORE_CALL_4|) (* .cse0 (select (select |c_old(#memory_int#5)| |v_func_to_recursive_line_31_to_42_0_#in~y1.base_BEFORE_CALL_4|) |v_func_to_recursive_line_31_to_42_0_#in~y1.offset_BEFORE_CALL_4|)))))))) (or (forall ((|v_func_to_recursive_line_31_to_42_0_#in~x2.offset_BEFORE_CALL_4| Int) (|v_func_to_recursive_line_31_to_42_0_#in~x1.base_BEFORE_CALL_4| Int) (|v_func_to_recursive_line_31_to_42_0_#in~x2.base_BEFORE_CALL_4| Int) (|v_func_to_recursive_line_31_to_42_0_#in~y2.offset_BEFORE_CALL_4| Int) (|v_func_to_recursive_line_31_to_42_0_#in~y1.base_BEFORE_CALL_4| Int) (|v_func_to_recursive_line_31_to_42_0_#in~y2.base_BEFORE_CALL_4| Int) (|v_func_to_recursive_line_31_to_42_0_#in~x1.offset_BEFORE_CALL_4| Int) (|v_func_to_recursive_line_31_to_42_0_#in~y1.offset_BEFORE_CALL_4| Int)) (= (+ (select (select |c_#memory_int#4| |v_func_to_recursive_line_31_to_42_0_#in~y2.base_BEFORE_CALL_4|) |v_func_to_recursive_line_31_to_42_0_#in~y2.offset_BEFORE_CALL_4|) (* (select (select |c_#memory_int#1| |v_func_to_recursive_line_31_to_42_0_#in~x2.base_BEFORE_CALL_4|) |v_func_to_recursive_line_31_to_42_0_#in~x2.offset_BEFORE_CALL_4|) (select (select |c_#memory_int#5| |v_func_to_recursive_line_31_to_42_0_#in~y1.base_BEFORE_CALL_4|) |v_func_to_recursive_line_31_to_42_0_#in~y1.offset_BEFORE_CALL_4|))) (select (select |c_#memory_int#3| |v_func_to_recursive_line_31_to_42_0_#in~x1.base_BEFORE_CALL_4|) |v_func_to_recursive_line_31_to_42_0_#in~x1.offset_BEFORE_CALL_4|))) (< (select (select |c_#memory_int#3| |c_func_to_recursive_line_31_to_42_0_#in~x1.base|) |c_func_to_recursive_line_31_to_42_0_#in~x1.offset|) (+ (* (select (select |c_#memory_int#1| |c_func_to_recursive_line_31_to_42_0_#in~x2.base|) |c_func_to_recursive_line_31_to_42_0_#in~x2.offset|) (select (select |c_old(#memory_int#5)| |c_func_to_recursive_line_31_to_42_0_#in~y1.base|) |c_func_to_recursive_line_31_to_42_0_#in~y1.offset|)) (select (select |c_old(#memory_int#4)| |c_func_to_recursive_line_31_to_42_0_#in~y2.base|) |c_func_to_recursive_line_31_to_42_0_#in~y2.offset|) 1)))) is different from false [2024-11-08 15:26:00,337 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 15:26:00,337 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [840543275] [2024-11-08 15:26:00,337 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 15:26:00,337 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [953597301] [2024-11-08 15:26:00,337 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [953597301] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 15:26:00,337 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-08 15:26:00,337 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [26] total 26 [2024-11-08 15:26:00,337 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1877899139] [2024-11-08 15:26:00,337 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-08 15:26:00,338 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2024-11-08 15:26:00,338 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 15:26:00,338 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2024-11-08 15:26:00,339 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=114, Invalid=1011, Unknown=1, NotChecked=64, Total=1190 [2024-11-08 15:26:00,339 INFO L87 Difference]: Start difference. First operand 52 states and 59 transitions. Second operand has 26 states, 21 states have (on average 1.4761904761904763) internal successors, (31), 21 states have internal predecessors, (31), 7 states have call successors, (7), 5 states have call predecessors, (7), 5 states have return successors, (6), 5 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-08 15:26:04,369 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-08 15:26:05,873 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 15:26:05,874 INFO L93 Difference]: Finished difference Result 65 states and 74 transitions. [2024-11-08 15:26:05,874 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2024-11-08 15:26:05,874 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 21 states have (on average 1.4761904761904763) internal successors, (31), 21 states have internal predecessors, (31), 7 states have call successors, (7), 5 states have call predecessors, (7), 5 states have return successors, (6), 5 states have call predecessors, (6), 6 states have call successors, (6) Word has length 44 [2024-11-08 15:26:05,875 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 15:26:05,876 INFO L225 Difference]: With dead ends: 65 [2024-11-08 15:26:05,876 INFO L226 Difference]: Without dead ends: 55 [2024-11-08 15:26:05,877 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 71 GetRequests, 18 SyntacticMatches, 6 SemanticMatches, 47 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 497 ImplicationChecksByTransitivity, 6.0s TimeCoverageRelationStatistics Valid=232, Invalid=2027, Unknown=1, NotChecked=92, Total=2352 [2024-11-08 15:26:05,878 INFO L432 NwaCegarLoop]: 14 mSDtfsCounter, 31 mSDsluCounter, 110 mSDsCounter, 0 mSdLazyCounter, 578 mSolverCounterSat, 10 mSolverCounterUnsat, 6 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 33 SdHoareTripleChecker+Valid, 124 SdHoareTripleChecker+Invalid, 594 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 578 IncrementalHoareTripleChecker+Invalid, 6 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.7s IncrementalHoareTripleChecker+Time [2024-11-08 15:26:05,878 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [33 Valid, 124 Invalid, 594 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 578 Invalid, 6 Unknown, 0 Unchecked, 4.7s Time] [2024-11-08 15:26:05,878 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2024-11-08 15:26:05,887 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 55. [2024-11-08 15:26:05,887 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 55 states, 37 states have (on average 1.0810810810810811) internal successors, (40), 38 states have internal predecessors, (40), 10 states have call successors, (10), 8 states have call predecessors, (10), 7 states have return successors, (14), 8 states have call predecessors, (14), 9 states have call successors, (14) [2024-11-08 15:26:05,888 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 64 transitions. [2024-11-08 15:26:05,888 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 64 transitions. Word has length 44 [2024-11-08 15:26:05,888 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 15:26:05,888 INFO L471 AbstractCegarLoop]: Abstraction has 55 states and 64 transitions. [2024-11-08 15:26:05,888 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 21 states have (on average 1.4761904761904763) internal successors, (31), 21 states have internal predecessors, (31), 7 states have call successors, (7), 5 states have call predecessors, (7), 5 states have return successors, (6), 5 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-08 15:26:05,888 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 64 transitions. [2024-11-08 15:26:05,889 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2024-11-08 15:26:05,889 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 15:26:05,889 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 15:26:05,902 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2024-11-08 15:26:06,092 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 15:26:06,092 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 15:26:06,093 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 15:26:06,093 INFO L85 PathProgramCache]: Analyzing trace with hash 1904672534, now seen corresponding path program 1 times [2024-11-08 15:26:06,093 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 15:26:06,093 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [9371993] [2024-11-08 15:26:06,093 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 15:26:06,093 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 15:26:06,122 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 15:26:06,128 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [941726547] [2024-11-08 15:26:06,128 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 15:26:06,128 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 15:26:06,128 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 15:26:06,131 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 15:26:06,132 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-08 15:26:06,223 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:26:06,226 INFO L255 TraceCheckSpWp]: Trace formula consists of 290 conjuncts, 144 conjuncts are in the unsatisfiable core [2024-11-08 15:26:06,230 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 15:26:06,235 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-08 15:26:06,237 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-08 15:26:06,241 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-08 15:26:06,245 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-08 15:26:06,249 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2024-11-08 15:26:06,261 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-08 15:26:06,952 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-11-08 15:26:06,983 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2024-11-08 15:26:07,039 INFO L134 CoverageAnalysis]: Checked inductivity of 19 backedges. 6 proven. 6 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2024-11-08 15:26:07,039 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 15:26:08,399 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 57 treesize of output 49 [2024-11-08 15:26:08,408 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 49 treesize of output 41 [2024-11-08 15:26:08,415 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 41 treesize of output 37 [2024-11-08 15:26:50,377 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 15:26:50,377 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [9371993] [2024-11-08 15:26:50,377 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 15:26:50,378 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [941726547] [2024-11-08 15:26:50,378 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [941726547] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 15:26:50,378 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-08 15:26:50,378 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19] total 19 [2024-11-08 15:26:50,378 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1418905764] [2024-11-08 15:26:50,378 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-08 15:26:50,378 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2024-11-08 15:26:50,378 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 15:26:50,379 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2024-11-08 15:26:50,379 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=85, Invalid=666, Unknown=5, NotChecked=0, Total=756 [2024-11-08 15:26:50,379 INFO L87 Difference]: Start difference. First operand 55 states and 64 transitions. Second operand has 19 states, 15 states have (on average 1.8) internal successors, (27), 15 states have internal predecessors, (27), 6 states have call successors, (7), 3 states have call predecessors, (7), 4 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) [2024-11-08 15:26:51,564 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 15:26:51,564 INFO L93 Difference]: Finished difference Result 63 states and 74 transitions. [2024-11-08 15:26:51,565 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2024-11-08 15:26:51,565 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 15 states have (on average 1.8) internal successors, (27), 15 states have internal predecessors, (27), 6 states have call successors, (7), 3 states have call predecessors, (7), 4 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) Word has length 44 [2024-11-08 15:26:51,565 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 15:26:51,566 INFO L225 Difference]: With dead ends: 63 [2024-11-08 15:26:51,566 INFO L226 Difference]: Without dead ends: 57 [2024-11-08 15:26:51,566 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 67 GetRequests, 29 SyntacticMatches, 2 SemanticMatches, 36 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 237 ImplicationChecksByTransitivity, 42.9s TimeCoverageRelationStatistics Valid=159, Invalid=1242, Unknown=5, NotChecked=0, Total=1406 [2024-11-08 15:26:51,567 INFO L432 NwaCegarLoop]: 16 mSDtfsCounter, 16 mSDsluCounter, 100 mSDsCounter, 0 mSdLazyCounter, 408 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 116 SdHoareTripleChecker+Invalid, 416 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 408 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2024-11-08 15:26:51,567 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 116 Invalid, 416 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 408 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2024-11-08 15:26:51,570 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 57 states. [2024-11-08 15:26:51,582 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 57 to 54. [2024-11-08 15:26:51,582 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 37 states have (on average 1.0810810810810811) internal successors, (40), 37 states have internal predecessors, (40), 9 states have call successors, (9), 8 states have call predecessors, (9), 7 states have return successors, (11), 8 states have call predecessors, (11), 8 states have call successors, (11) [2024-11-08 15:26:51,582 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 60 transitions. [2024-11-08 15:26:51,583 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 60 transitions. Word has length 44 [2024-11-08 15:26:51,583 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 15:26:51,583 INFO L471 AbstractCegarLoop]: Abstraction has 54 states and 60 transitions. [2024-11-08 15:26:51,583 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 15 states have (on average 1.8) internal successors, (27), 15 states have internal predecessors, (27), 6 states have call successors, (7), 3 states have call predecessors, (7), 4 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) [2024-11-08 15:26:51,583 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 60 transitions. [2024-11-08 15:26:51,583 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 58 [2024-11-08 15:26:51,584 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 15:26:51,584 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 15:26:51,598 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2024-11-08 15:26:51,784 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 15:26:51,784 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 15:26:51,785 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 15:26:51,785 INFO L85 PathProgramCache]: Analyzing trace with hash 449524694, now seen corresponding path program 1 times [2024-11-08 15:26:51,785 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 15:26:51,785 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [935103240] [2024-11-08 15:26:51,785 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 15:26:51,785 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 15:26:51,825 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 15:26:51,827 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1280321622] [2024-11-08 15:26:51,828 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 15:26:51,829 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 15:26:51,829 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 15:26:51,830 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 15:26:51,831 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-08 15:26:51,945 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:26:51,949 WARN L253 TraceCheckSpWp]: Trace formula consists of 378 conjuncts, 200 conjuncts are in the unsatisfiable core [2024-11-08 15:26:51,953 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 15:26:51,961 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-08 15:26:51,963 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-08 15:26:52,034 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-08 15:26:52,042 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-08 15:26:52,049 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2024-11-08 15:26:52,080 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-08 15:26:53,171 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 9 [2024-11-08 15:26:54,179 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 28 treesize of output 16 [2024-11-08 15:26:54,188 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 3 [2024-11-08 15:26:54,192 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-11-08 15:26:54,208 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 26 treesize of output 18 [2024-11-08 15:26:54,328 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-08 15:26:54,329 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 58 treesize of output 66 [2024-11-08 15:26:54,335 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 12 [2024-11-08 15:26:54,508 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 7 proven. 28 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2024-11-08 15:26:54,508 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 15:26:56,753 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 36 treesize of output 28 [2024-11-08 15:26:58,107 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 37 treesize of output 29 [2024-11-08 15:26:58,343 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 15:26:58,343 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [935103240] [2024-11-08 15:26:58,343 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 15:26:58,343 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1280321622] [2024-11-08 15:26:58,343 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1280321622] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 15:26:58,344 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-08 15:26:58,344 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [30] total 30 [2024-11-08 15:26:58,344 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [872615103] [2024-11-08 15:26:58,344 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-08 15:26:58,344 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 30 states [2024-11-08 15:26:58,344 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 15:26:58,345 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2024-11-08 15:26:58,346 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=117, Invalid=1073, Unknown=0, NotChecked=0, Total=1190 [2024-11-08 15:26:58,346 INFO L87 Difference]: Start difference. First operand 54 states and 60 transitions. Second operand has 30 states, 24 states have (on average 1.4583333333333333) internal successors, (35), 25 states have internal predecessors, (35), 8 states have call successors, (8), 5 states have call predecessors, (8), 6 states have return successors, (7), 6 states have call predecessors, (7), 7 states have call successors, (7) [2024-11-08 15:27:02,350 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-08 15:27:04,930 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 15:27:04,930 INFO L93 Difference]: Finished difference Result 65 states and 78 transitions. [2024-11-08 15:27:04,930 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2024-11-08 15:27:04,930 INFO L78 Accepts]: Start accepts. Automaton has has 30 states, 24 states have (on average 1.4583333333333333) internal successors, (35), 25 states have internal predecessors, (35), 8 states have call successors, (8), 5 states have call predecessors, (8), 6 states have return successors, (7), 6 states have call predecessors, (7), 7 states have call successors, (7) Word has length 57 [2024-11-08 15:27:04,930 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 15:27:04,931 INFO L225 Difference]: With dead ends: 65 [2024-11-08 15:27:04,931 INFO L226 Difference]: Without dead ends: 59 [2024-11-08 15:27:04,932 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 79 GetRequests, 24 SyntacticMatches, 8 SemanticMatches, 47 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 568 ImplicationChecksByTransitivity, 3.0s TimeCoverageRelationStatistics Valid=224, Invalid=2128, Unknown=0, NotChecked=0, Total=2352 [2024-11-08 15:27:04,932 INFO L432 NwaCegarLoop]: 18 mSDtfsCounter, 27 mSDsluCounter, 144 mSDsCounter, 0 mSdLazyCounter, 823 mSolverCounterSat, 12 mSolverCounterUnsat, 3 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 5.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 28 SdHoareTripleChecker+Valid, 162 SdHoareTripleChecker+Invalid, 838 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 823 IncrementalHoareTripleChecker+Invalid, 3 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 5.5s IncrementalHoareTripleChecker+Time [2024-11-08 15:27:04,932 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [28 Valid, 162 Invalid, 838 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 823 Invalid, 3 Unknown, 0 Unchecked, 5.5s Time] [2024-11-08 15:27:04,932 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 59 states. [2024-11-08 15:27:04,941 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 59 to 57. [2024-11-08 15:27:04,942 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 57 states, 38 states have (on average 1.0789473684210527) internal successors, (41), 39 states have internal predecessors, (41), 10 states have call successors, (10), 8 states have call predecessors, (10), 8 states have return successors, (17), 9 states have call predecessors, (17), 9 states have call successors, (17) [2024-11-08 15:27:04,943 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 68 transitions. [2024-11-08 15:27:04,944 INFO L78 Accepts]: Start accepts. Automaton has 57 states and 68 transitions. Word has length 57 [2024-11-08 15:27:04,944 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 15:27:04,944 INFO L471 AbstractCegarLoop]: Abstraction has 57 states and 68 transitions. [2024-11-08 15:27:04,944 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 30 states, 24 states have (on average 1.4583333333333333) internal successors, (35), 25 states have internal predecessors, (35), 8 states have call successors, (8), 5 states have call predecessors, (8), 6 states have return successors, (7), 6 states have call predecessors, (7), 7 states have call successors, (7) [2024-11-08 15:27:04,944 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 68 transitions. [2024-11-08 15:27:04,945 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 58 [2024-11-08 15:27:04,945 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 15:27:04,945 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 15:27:04,959 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-11-08 15:27:05,145 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 15:27:05,146 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 15:27:05,146 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 15:27:05,146 INFO L85 PathProgramCache]: Analyzing trace with hash 668379412, now seen corresponding path program 2 times [2024-11-08 15:27:05,146 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 15:27:05,147 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1313712695] [2024-11-08 15:27:05,147 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 15:27:05,147 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 15:27:05,171 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 15:27:05,174 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1622218301] [2024-11-08 15:27:05,174 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-08 15:27:05,175 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 15:27:05,175 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 15:27:05,176 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 15:27:05,177 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-08 15:27:05,285 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-08 15:27:05,285 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 15:27:05,287 INFO L255 TraceCheckSpWp]: Trace formula consists of 373 conjuncts, 117 conjuncts are in the unsatisfiable core [2024-11-08 15:27:05,291 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 15:27:05,300 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 75 treesize of output 73 [2024-11-08 15:27:05,307 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-08 15:27:05,397 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2024-11-08 15:27:05,404 INFO L378 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 11 treesize of output 7 [2024-11-08 15:27:05,411 INFO L378 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 11 treesize of output 7 [2024-11-08 15:27:05,440 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-08 15:27:06,517 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-11-08 15:27:06,659 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 1 proven. 24 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2024-11-08 15:27:06,659 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 15:27:07,391 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 15:27:07,392 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1313712695] [2024-11-08 15:27:07,392 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 15:27:07,392 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1622218301] [2024-11-08 15:27:07,392 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1622218301] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 15:27:07,392 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-08 15:27:07,392 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [23] total 23 [2024-11-08 15:27:07,392 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [492758253] [2024-11-08 15:27:07,392 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-08 15:27:07,392 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2024-11-08 15:27:07,392 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 15:27:07,393 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-11-08 15:27:07,393 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=87, Invalid=669, Unknown=0, NotChecked=0, Total=756 [2024-11-08 15:27:07,393 INFO L87 Difference]: Start difference. First operand 57 states and 68 transitions. Second operand has 23 states, 18 states have (on average 1.6666666666666667) internal successors, (30), 20 states have internal predecessors, (30), 8 states have call successors, (8), 4 states have call predecessors, (8), 5 states have return successors, (7), 6 states have call predecessors, (7), 7 states have call successors, (7) [2024-11-08 15:27:11,430 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-08 15:27:12,697 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 15:27:12,698 INFO L93 Difference]: Finished difference Result 67 states and 82 transitions. [2024-11-08 15:27:12,698 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2024-11-08 15:27:12,698 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 18 states have (on average 1.6666666666666667) internal successors, (30), 20 states have internal predecessors, (30), 8 states have call successors, (8), 4 states have call predecessors, (8), 5 states have return successors, (7), 6 states have call predecessors, (7), 7 states have call successors, (7) Word has length 57 [2024-11-08 15:27:12,699 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 15:27:12,699 INFO L225 Difference]: With dead ends: 67 [2024-11-08 15:27:12,699 INFO L226 Difference]: Without dead ends: 61 [2024-11-08 15:27:12,700 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 70 GetRequests, 29 SyntacticMatches, 7 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 320 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=135, Invalid=1125, Unknown=0, NotChecked=0, Total=1260 [2024-11-08 15:27:12,700 INFO L432 NwaCegarLoop]: 16 mSDtfsCounter, 21 mSDsluCounter, 110 mSDsCounter, 0 mSdLazyCounter, 458 mSolverCounterSat, 9 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 126 SdHoareTripleChecker+Invalid, 468 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 458 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.9s IncrementalHoareTripleChecker+Time [2024-11-08 15:27:12,700 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [24 Valid, 126 Invalid, 468 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 458 Invalid, 1 Unknown, 0 Unchecked, 4.9s Time] [2024-11-08 15:27:12,701 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 61 states. [2024-11-08 15:27:12,714 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 61 to 57. [2024-11-08 15:27:12,715 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 57 states, 38 states have (on average 1.0789473684210527) internal successors, (41), 39 states have internal predecessors, (41), 10 states have call successors, (10), 8 states have call predecessors, (10), 8 states have return successors, (17), 9 states have call predecessors, (17), 9 states have call successors, (17) [2024-11-08 15:27:12,717 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 68 transitions. [2024-11-08 15:27:12,717 INFO L78 Accepts]: Start accepts. Automaton has 57 states and 68 transitions. Word has length 57 [2024-11-08 15:27:12,718 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 15:27:12,718 INFO L471 AbstractCegarLoop]: Abstraction has 57 states and 68 transitions. [2024-11-08 15:27:12,718 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 18 states have (on average 1.6666666666666667) internal successors, (30), 20 states have internal predecessors, (30), 8 states have call successors, (8), 4 states have call predecessors, (8), 5 states have return successors, (7), 6 states have call predecessors, (7), 7 states have call successors, (7) [2024-11-08 15:27:12,719 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 68 transitions. [2024-11-08 15:27:12,719 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 58 [2024-11-08 15:27:12,722 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 15:27:12,722 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 15:27:12,739 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2024-11-08 15:27:12,926 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 15:27:12,926 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 15:27:12,927 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 15:27:12,927 INFO L85 PathProgramCache]: Analyzing trace with hash 740765970, now seen corresponding path program 2 times [2024-11-08 15:27:12,927 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 15:27:12,927 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1318572402] [2024-11-08 15:27:12,927 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 15:27:12,927 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 15:27:12,948 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:27:13,378 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 15:27:13,380 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:27:13,381 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-08 15:27:13,382 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:27:13,400 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-11-08 15:27:13,413 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:27:13,947 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 15:27:13,949 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:27:13,953 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-11-08 15:27:13,959 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:27:14,517 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 15:27:14,519 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:27:14,525 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-11-08 15:27:14,528 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:27:14,707 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 15:27:14,708 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:27:14,712 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 9 proven. 17 refuted. 0 times theorem prover too weak. 19 trivial. 0 not checked. [2024-11-08 15:27:14,712 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 15:27:14,712 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1318572402] [2024-11-08 15:27:14,712 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1318572402] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 15:27:14,712 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1246244780] [2024-11-08 15:27:14,712 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-08 15:27:14,712 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 15:27:14,712 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 15:27:14,715 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 15:27:14,717 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-11-08 15:27:14,836 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-08 15:27:14,836 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 15:27:14,838 INFO L255 TraceCheckSpWp]: Trace formula consists of 378 conjuncts, 61 conjuncts are in the unsatisfiable core [2024-11-08 15:27:14,846 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 15:27:14,854 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-08 15:27:14,859 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-08 15:27:15,093 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 9 [2024-11-08 15:27:15,249 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 10 [2024-11-08 15:27:15,353 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 10 proven. 14 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2024-11-08 15:27:15,353 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 15:27:15,824 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 9 [2024-11-08 15:27:16,455 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 10 proven. 19 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2024-11-08 15:27:16,455 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1246244780] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 15:27:16,455 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 15:27:16,455 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 11, 12] total 34 [2024-11-08 15:27:16,455 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [358622685] [2024-11-08 15:27:16,455 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 15:27:16,455 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 34 states [2024-11-08 15:27:16,456 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 15:27:16,456 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 34 interpolants. [2024-11-08 15:27:16,456 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=122, Invalid=1000, Unknown=0, NotChecked=0, Total=1122 [2024-11-08 15:27:16,456 INFO L87 Difference]: Start difference. First operand 57 states and 68 transitions. Second operand has 34 states, 25 states have (on average 2.24) internal successors, (56), 30 states have internal predecessors, (56), 16 states have call successors, (19), 6 states have call predecessors, (19), 6 states have return successors, (18), 12 states have call predecessors, (18), 15 states have call successors, (18) [2024-11-08 15:27:18,272 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 15:27:18,273 INFO L93 Difference]: Finished difference Result 76 states and 102 transitions. [2024-11-08 15:27:18,273 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2024-11-08 15:27:18,273 INFO L78 Accepts]: Start accepts. Automaton has has 34 states, 25 states have (on average 2.24) internal successors, (56), 30 states have internal predecessors, (56), 16 states have call successors, (19), 6 states have call predecessors, (19), 6 states have return successors, (18), 12 states have call predecessors, (18), 15 states have call successors, (18) Word has length 57 [2024-11-08 15:27:18,273 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 15:27:18,274 INFO L225 Difference]: With dead ends: 76 [2024-11-08 15:27:18,274 INFO L226 Difference]: Without dead ends: 68 [2024-11-08 15:27:18,275 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 161 GetRequests, 117 SyntacticMatches, 0 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 304 ImplicationChecksByTransitivity, 2.1s TimeCoverageRelationStatistics Valid=285, Invalid=1785, Unknown=0, NotChecked=0, Total=2070 [2024-11-08 15:27:18,275 INFO L432 NwaCegarLoop]: 22 mSDtfsCounter, 47 mSDsluCounter, 165 mSDsCounter, 0 mSdLazyCounter, 860 mSolverCounterSat, 51 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 47 SdHoareTripleChecker+Valid, 187 SdHoareTripleChecker+Invalid, 911 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 51 IncrementalHoareTripleChecker+Valid, 860 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.1s IncrementalHoareTripleChecker+Time [2024-11-08 15:27:18,275 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [47 Valid, 187 Invalid, 911 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [51 Valid, 860 Invalid, 0 Unknown, 0 Unchecked, 1.1s Time] [2024-11-08 15:27:18,276 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 68 states. [2024-11-08 15:27:18,291 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 68 to 63. [2024-11-08 15:27:18,292 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 63 states, 41 states have (on average 1.0731707317073171) internal successors, (44), 42 states have internal predecessors, (44), 10 states have call successors, (10), 8 states have call predecessors, (10), 11 states have return successors, (22), 12 states have call predecessors, (22), 9 states have call successors, (22) [2024-11-08 15:27:18,292 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 76 transitions. [2024-11-08 15:27:18,292 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 76 transitions. Word has length 57 [2024-11-08 15:27:18,293 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 15:27:18,293 INFO L471 AbstractCegarLoop]: Abstraction has 63 states and 76 transitions. [2024-11-08 15:27:18,293 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 34 states, 25 states have (on average 2.24) internal successors, (56), 30 states have internal predecessors, (56), 16 states have call successors, (19), 6 states have call predecessors, (19), 6 states have return successors, (18), 12 states have call predecessors, (18), 15 states have call successors, (18) [2024-11-08 15:27:18,293 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 76 transitions. [2024-11-08 15:27:18,294 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 71 [2024-11-08 15:27:18,294 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 15:27:18,294 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 15:27:18,307 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2024-11-08 15:27:18,494 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2024-11-08 15:27:18,495 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 15:27:18,495 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 15:27:18,495 INFO L85 PathProgramCache]: Analyzing trace with hash 2124511340, now seen corresponding path program 3 times [2024-11-08 15:27:18,495 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 15:27:18,495 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1944307155] [2024-11-08 15:27:18,495 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 15:27:18,495 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 15:27:18,516 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 15:27:18,519 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [888898718] [2024-11-08 15:27:18,519 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-08 15:27:18,519 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 15:27:18,519 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 15:27:18,521 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) [2024-11-08 15:27:18,526 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-11-08 15:27:18,695 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2024-11-08 15:27:18,695 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 15:27:18,706 WARN L253 TraceCheckSpWp]: Trace formula consists of 454 conjuncts, 229 conjuncts are in the unsatisfiable core [2024-11-08 15:27:18,712 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 15:27:18,726 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-08 15:27:18,730 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-08 15:27:18,774 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-08 15:27:18,782 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-08 15:27:18,792 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-08 15:27:18,836 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-08 15:27:20,026 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 28 treesize of output 24 [2024-11-08 15:27:20,032 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 20 [2024-11-08 15:27:20,925 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 38 treesize of output 22 [2024-11-08 15:27:21,016 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 26 treesize of output 14 [2024-11-08 15:27:21,025 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 10 [2024-11-08 15:27:21,038 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2024-11-08 15:27:21,194 INFO L134 CoverageAnalysis]: Checked inductivity of 84 backedges. 12 proven. 49 refuted. 0 times theorem prover too weak. 23 trivial. 0 not checked. [2024-11-08 15:27:21,195 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 15:27:26,016 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 57 treesize of output 49 [2024-11-08 15:27:26,024 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 49 treesize of output 41 [2024-11-08 15:27:26,032 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 41 treesize of output 37