./Ultimate.py --spec /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/properties/unreach-call.prp --file /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursified_nla-digbench/recursified_cohencu-ll.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 84cfde4a Calling Ultimate with: /root/.sdkman/candidates/java/current/bin/java -Dosgi.configuration.area=/storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursified_nla-digbench/recursified_cohencu-ll.c -s /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate-clean/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 260777f6a7be1f16cc330a008300c11ebdea8f1cf9d8e96a0325274fd8fd5b2a --- Real Ultimate output --- This is Ultimate 0.2.5-dev-84cfde4 [2024-10-11 03:07:34,764 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-10-11 03:07:34,844 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-10-11 03:07:34,850 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-10-11 03:07:34,851 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-10-11 03:07:34,880 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-10-11 03:07:34,881 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-10-11 03:07:34,881 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-10-11 03:07:34,882 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-10-11 03:07:34,882 INFO L153 SettingsManager]: * Use memory slicer=true [2024-10-11 03:07:34,882 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-10-11 03:07:34,883 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-10-11 03:07:34,883 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-10-11 03:07:34,883 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-10-11 03:07:34,884 INFO L153 SettingsManager]: * Use SBE=true [2024-10-11 03:07:34,886 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-10-11 03:07:34,888 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-10-11 03:07:34,889 INFO L153 SettingsManager]: * sizeof long=4 [2024-10-11 03:07:34,889 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-10-11 03:07:34,889 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-10-11 03:07:34,890 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-10-11 03:07:34,891 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-10-11 03:07:34,892 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-10-11 03:07:34,894 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-10-11 03:07:34,895 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-10-11 03:07:34,895 INFO L153 SettingsManager]: * sizeof long double=12 [2024-10-11 03:07:34,895 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-10-11 03:07:34,896 INFO L153 SettingsManager]: * Use constant arrays=true [2024-10-11 03:07:34,896 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-10-11 03:07:34,896 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-10-11 03:07:34,897 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-10-11 03:07:34,897 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-10-11 03:07:34,897 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-10-11 03:07:34,898 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-10-11 03:07:34,898 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-10-11 03:07:34,898 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-10-11 03:07:34,898 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-10-11 03:07:34,899 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-10-11 03:07:34,899 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-10-11 03:07:34,899 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-10-11 03:07:34,899 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-10-11 03:07:34,901 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-10-11 03:07:34,901 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-clean/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-clean/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 -> 260777f6a7be1f16cc330a008300c11ebdea8f1cf9d8e96a0325274fd8fd5b2a [2024-10-11 03:07:35,140 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-10-11 03:07:35,165 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-10-11 03:07:35,169 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-10-11 03:07:35,170 INFO L270 PluginConnector]: Initializing CDTParser... [2024-10-11 03:07:35,171 INFO L274 PluginConnector]: CDTParser initialized [2024-10-11 03:07:35,172 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursified_nla-digbench/recursified_cohencu-ll.c [2024-10-11 03:07:36,686 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-10-11 03:07:36,874 INFO L384 CDTParser]: Found 1 translation units. [2024-10-11 03:07:36,875 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursified_nla-digbench/recursified_cohencu-ll.c [2024-10-11 03:07:36,883 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/data/ed37533d7/d5394c7657e442c4b9594bb9dacefec0/FLAGbb1e417ec [2024-10-11 03:07:36,895 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/data/ed37533d7/d5394c7657e442c4b9594bb9dacefec0 [2024-10-11 03:07:36,898 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-10-11 03:07:36,899 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-10-11 03:07:36,900 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-10-11 03:07:36,900 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-10-11 03:07:36,907 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-10-11 03:07:36,907 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 11.10 03:07:36" (1/1) ... [2024-10-11 03:07:36,908 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@59f33d65 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 03:07:36, skipping insertion in model container [2024-10-11 03:07:36,910 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 11.10 03:07:36" (1/1) ... [2024-10-11 03:07:36,929 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-10-11 03:07:37,088 WARN L248 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_cohencu-ll.c[1124,1137] [2024-10-11 03:07:37,110 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-11 03:07:37,120 INFO L200 MainTranslator]: Completed pre-run [2024-10-11 03:07:37,130 WARN L248 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_cohencu-ll.c[1124,1137] [2024-10-11 03:07:37,145 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-11 03:07:37,161 INFO L204 MainTranslator]: Completed translation [2024-10-11 03:07:37,161 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 03:07:37 WrapperNode [2024-10-11 03:07:37,161 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-10-11 03:07:37,162 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-10-11 03:07:37,162 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-10-11 03:07:37,162 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-10-11 03:07:37,170 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 03:07:37" (1/1) ... [2024-10-11 03:07:37,178 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 03:07:37" (1/1) ... [2024-10-11 03:07:37,199 INFO L138 Inliner]: procedures = 16, calls = 99, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 106 [2024-10-11 03:07:37,199 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-10-11 03:07:37,200 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-10-11 03:07:37,200 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-10-11 03:07:37,200 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-10-11 03:07:37,209 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 03:07:37" (1/1) ... [2024-10-11 03:07:37,210 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 03:07:37" (1/1) ... [2024-10-11 03:07:37,212 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 03:07:37" (1/1) ... [2024-10-11 03:07:37,227 INFO L175 MemorySlicer]: Split 66 memory accesses to 6 slices as follows [2, 15, 11, 21, 12, 5]. 32 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2, 0, 0, 0, 0, 0]. The 9 writes are split as follows [0, 2, 2, 2, 2, 1]. [2024-10-11 03:07:37,227 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 03:07:37" (1/1) ... [2024-10-11 03:07:37,227 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 03:07:37" (1/1) ... [2024-10-11 03:07:37,234 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 03:07:37" (1/1) ... [2024-10-11 03:07:37,236 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 03:07:37" (1/1) ... [2024-10-11 03:07:37,238 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 03:07:37" (1/1) ... [2024-10-11 03:07:37,239 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 03:07:37" (1/1) ... [2024-10-11 03:07:37,242 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-10-11 03:07:37,243 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-10-11 03:07:37,243 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-10-11 03:07:37,243 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-10-11 03:07:37,244 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 03:07:37" (1/1) ... [2024-10-11 03:07:37,254 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-10-11 03:07:37,272 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 03:07:37,288 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-10-11 03:07:37,291 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-10-11 03:07:37,346 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-10-11 03:07:37,347 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-10-11 03:07:37,347 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2024-10-11 03:07:37,347 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2024-10-11 03:07:37,347 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#3 [2024-10-11 03:07:37,347 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#4 [2024-10-11 03:07:37,348 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#5 [2024-10-11 03:07:37,348 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2024-10-11 03:07:37,348 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2024-10-11 03:07:37,348 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2024-10-11 03:07:37,348 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#2 [2024-10-11 03:07:37,348 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#3 [2024-10-11 03:07:37,349 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#4 [2024-10-11 03:07:37,349 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#5 [2024-10-11 03:07:37,349 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_29_to_41_0 [2024-10-11 03:07:37,349 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_29_to_41_0 [2024-10-11 03:07:37,349 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-10-11 03:07:37,350 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-10-11 03:07:37,350 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2024-10-11 03:07:37,350 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2024-10-11 03:07:37,350 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#2 [2024-10-11 03:07:37,350 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#3 [2024-10-11 03:07:37,350 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#4 [2024-10-11 03:07:37,351 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#5 [2024-10-11 03:07:37,351 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-10-11 03:07:37,351 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-10-11 03:07:37,351 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2024-10-11 03:07:37,453 INFO L238 CfgBuilder]: Building ICFG [2024-10-11 03:07:37,456 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-10-11 03:07:37,720 INFO L? ?]: Removed 9 outVars from TransFormulas that were not future-live. [2024-10-11 03:07:37,720 INFO L287 CfgBuilder]: Performing block encoding [2024-10-11 03:07:37,774 INFO L309 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-10-11 03:07:37,774 INFO L314 CfgBuilder]: Removed 1 assume(true) statements. [2024-10-11 03:07:37,774 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 11.10 03:07:37 BoogieIcfgContainer [2024-10-11 03:07:37,774 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-10-11 03:07:37,777 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-10-11 03:07:37,780 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-10-11 03:07:37,783 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-10-11 03:07:37,784 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 11.10 03:07:36" (1/3) ... [2024-10-11 03:07:37,785 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6cede1e9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 11.10 03:07:37, skipping insertion in model container [2024-10-11 03:07:37,785 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 03:07:37" (2/3) ... [2024-10-11 03:07:37,786 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6cede1e9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 11.10 03:07:37, skipping insertion in model container [2024-10-11 03:07:37,786 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 11.10 03:07:37" (3/3) ... [2024-10-11 03:07:37,788 INFO L112 eAbstractionObserver]: Analyzing ICFG recursified_cohencu-ll.c [2024-10-11 03:07:37,806 INFO L209 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-10-11 03:07:37,807 INFO L149 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-10-11 03:07:37,871 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-10-11 03:07:37,877 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;@2df3842f, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-10-11 03:07:37,877 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-10-11 03:07:37,881 INFO L276 IsEmpty]: Start isEmpty. Operand has 38 states, 21 states have (on average 1.1904761904761905) internal successors, (25), 23 states have internal predecessors, (25), 13 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2024-10-11 03:07:37,886 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2024-10-11 03:07:37,886 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 03:07:37,887 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 03:07:37,887 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 03:07:37,891 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 03:07:37,891 INFO L85 PathProgramCache]: Analyzing trace with hash -1371458259, now seen corresponding path program 1 times [2024-10-11 03:07:37,898 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 03:07:37,898 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1599694849] [2024-10-11 03:07:37,898 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 03:07:37,899 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 03:07:38,044 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 03:07:38,703 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-11 03:07:38,703 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 03:07:38,704 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1599694849] [2024-10-11 03:07:38,704 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1599694849] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-11 03:07:38,705 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-11 03:07:38,705 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2024-10-11 03:07:38,707 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [132706399] [2024-10-11 03:07:38,708 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-11 03:07:38,712 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-10-11 03:07:38,712 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 03:07:38,735 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-10-11 03:07:38,736 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2024-10-11 03:07:38,738 INFO L87 Difference]: Start difference. First operand has 38 states, 21 states have (on average 1.1904761904761905) internal successors, (25), 23 states have internal predecessors, (25), 13 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) Second operand has 8 states, 6 states have (on average 1.0) internal successors, (6), 5 states have internal predecessors, (6), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-10-11 03:07:39,068 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 03:07:39,068 INFO L93 Difference]: Finished difference Result 94 states and 144 transitions. [2024-10-11 03:07:39,070 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-10-11 03:07:39,072 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 6 states have (on average 1.0) internal successors, (6), 5 states have internal predecessors, (6), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 8 [2024-10-11 03:07:39,072 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 03:07:39,080 INFO L225 Difference]: With dead ends: 94 [2024-10-11 03:07:39,080 INFO L226 Difference]: Without dead ends: 56 [2024-10-11 03:07:39,085 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 1 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-10-11 03:07:39,089 INFO L432 NwaCegarLoop]: 34 mSDtfsCounter, 20 mSDsluCounter, 158 mSDsCounter, 0 mSdLazyCounter, 149 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 20 SdHoareTripleChecker+Valid, 192 SdHoareTripleChecker+Invalid, 161 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 149 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-10-11 03:07:39,089 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [20 Valid, 192 Invalid, 161 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 149 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-10-11 03:07:39,104 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 56 states. [2024-10-11 03:07:39,140 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 56 to 55. [2024-10-11 03:07:39,142 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 55 states, 32 states have (on average 1.09375) internal successors, (35), 34 states have internal predecessors, (35), 18 states have call successors, (18), 4 states have call predecessors, (18), 4 states have return successors, (18), 17 states have call predecessors, (18), 17 states have call successors, (18) [2024-10-11 03:07:39,144 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 71 transitions. [2024-10-11 03:07:39,145 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 71 transitions. Word has length 8 [2024-10-11 03:07:39,146 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 03:07:39,146 INFO L471 AbstractCegarLoop]: Abstraction has 55 states and 71 transitions. [2024-10-11 03:07:39,146 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 6 states have (on average 1.0) internal successors, (6), 5 states have internal predecessors, (6), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-10-11 03:07:39,146 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 71 transitions. [2024-10-11 03:07:39,148 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2024-10-11 03:07:39,150 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 03:07:39,150 INFO L215 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 03:07:39,150 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-10-11 03:07:39,151 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 03:07:39,151 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 03:07:39,152 INFO L85 PathProgramCache]: Analyzing trace with hash -1638005840, now seen corresponding path program 1 times [2024-10-11 03:07:39,152 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 03:07:39,152 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [675691073] [2024-10-11 03:07:39,152 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 03:07:39,152 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 03:07:39,193 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-11 03:07:39,197 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [687155431] [2024-10-11 03:07:39,197 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 03:07:39,198 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 03:07:39,198 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 03:07:39,200 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 03:07:39,202 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-10-11 03:07:39,311 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 03:07:39,315 INFO L255 TraceCheckSpWp]: Trace formula consists of 171 conjuncts, 33 conjuncts are in the unsatisfiable core [2024-10-11 03:07:39,322 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 03:07:39,373 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-10-11 03:07:39,381 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-10-11 03:07:39,631 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-11 03:07:39,631 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 03:07:39,784 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-11 03:07:39,785 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 03:07:39,785 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [675691073] [2024-10-11 03:07:39,786 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-11 03:07:39,786 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [687155431] [2024-10-11 03:07:39,786 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [687155431] provided 1 perfect and 1 imperfect interpolant sequences [2024-10-11 03:07:39,786 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-10-11 03:07:39,786 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [8] total 10 [2024-10-11 03:07:39,787 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1793783524] [2024-10-11 03:07:39,789 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-11 03:07:39,790 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-10-11 03:07:39,790 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 03:07:39,791 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-10-11 03:07:39,791 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2024-10-11 03:07:39,791 INFO L87 Difference]: Start difference. First operand 55 states and 71 transitions. Second operand has 8 states, 6 states have (on average 1.6666666666666667) internal successors, (10), 6 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-11 03:07:40,396 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 03:07:40,397 INFO L93 Difference]: Finished difference Result 62 states and 77 transitions. [2024-10-11 03:07:40,398 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-10-11 03:07:40,398 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 6 states have (on average 1.6666666666666667) internal successors, (10), 6 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 14 [2024-10-11 03:07:40,399 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 03:07:40,399 INFO L225 Difference]: With dead ends: 62 [2024-10-11 03:07:40,400 INFO L226 Difference]: Without dead ends: 60 [2024-10-11 03:07:40,400 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 14 SyntacticMatches, 4 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=37, Invalid=119, Unknown=0, NotChecked=0, Total=156 [2024-10-11 03:07:40,401 INFO L432 NwaCegarLoop]: 36 mSDtfsCounter, 19 mSDsluCounter, 168 mSDsCounter, 0 mSdLazyCounter, 140 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 204 SdHoareTripleChecker+Invalid, 151 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 140 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-10-11 03:07:40,403 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 204 Invalid, 151 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 140 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-10-11 03:07:40,404 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 60 states. [2024-10-11 03:07:40,415 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 60 to 59. [2024-10-11 03:07:40,416 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 59 states, 35 states have (on average 1.0857142857142856) internal successors, (38), 37 states have internal predecessors, (38), 18 states have call successors, (18), 5 states have call predecessors, (18), 5 states have return successors, (18), 17 states have call predecessors, (18), 17 states have call successors, (18) [2024-10-11 03:07:40,420 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 59 states to 59 states and 74 transitions. [2024-10-11 03:07:40,420 INFO L78 Accepts]: Start accepts. Automaton has 59 states and 74 transitions. Word has length 14 [2024-10-11 03:07:40,420 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 03:07:40,420 INFO L471 AbstractCegarLoop]: Abstraction has 59 states and 74 transitions. [2024-10-11 03:07:40,420 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 6 states have (on average 1.6666666666666667) internal successors, (10), 6 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-11 03:07:40,421 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 74 transitions. [2024-10-11 03:07:40,421 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2024-10-11 03:07:40,421 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 03:07:40,421 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 03:07:40,442 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-10-11 03:07:40,622 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 03:07:40,623 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 03:07:40,623 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 03:07:40,623 INFO L85 PathProgramCache]: Analyzing trace with hash 1652518129, now seen corresponding path program 1 times [2024-10-11 03:07:40,624 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 03:07:40,624 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [475321567] [2024-10-11 03:07:40,624 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 03:07:40,624 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 03:07:40,649 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-11 03:07:40,650 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [279920499] [2024-10-11 03:07:40,650 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 03:07:40,651 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 03:07:40,651 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 03:07:40,653 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 03:07:40,654 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-10-11 03:07:40,744 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 03:07:40,747 INFO L255 TraceCheckSpWp]: Trace formula consists of 188 conjuncts, 42 conjuncts are in the unsatisfiable core [2024-10-11 03:07:40,751 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 03:07:40,760 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-10-11 03:07:40,766 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-10-11 03:07:41,104 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 1 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-11 03:07:41,104 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 03:07:41,349 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 32 treesize of output 24 [2024-10-11 03:07:41,462 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 3 proven. 4 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-10-11 03:07:41,462 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 03:07:41,462 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [475321567] [2024-10-11 03:07:41,462 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-11 03:07:41,462 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [279920499] [2024-10-11 03:07:41,462 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [279920499] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-11 03:07:41,463 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-11 03:07:41,463 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 12] total 21 [2024-10-11 03:07:41,463 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [412249161] [2024-10-11 03:07:41,463 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-11 03:07:41,463 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-10-11 03:07:41,464 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 03:07:41,464 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-10-11 03:07:41,465 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=64, Invalid=356, Unknown=0, NotChecked=0, Total=420 [2024-10-11 03:07:41,465 INFO L87 Difference]: Start difference. First operand 59 states and 74 transitions. Second operand has 21 states, 16 states have (on average 1.5625) internal successors, (25), 17 states have internal predecessors, (25), 7 states have call successors, (7), 6 states have call predecessors, (7), 4 states have return successors, (4), 2 states have call predecessors, (4), 4 states have call successors, (4) [2024-10-11 03:07:42,360 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 03:07:42,360 INFO L93 Difference]: Finished difference Result 83 states and 101 transitions. [2024-10-11 03:07:42,361 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2024-10-11 03:07:42,361 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 16 states have (on average 1.5625) internal successors, (25), 17 states have internal predecessors, (25), 7 states have call successors, (7), 6 states have call predecessors, (7), 4 states have return successors, (4), 2 states have call predecessors, (4), 4 states have call successors, (4) Word has length 20 [2024-10-11 03:07:42,361 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 03:07:42,363 INFO L225 Difference]: With dead ends: 83 [2024-10-11 03:07:42,365 INFO L226 Difference]: Without dead ends: 81 [2024-10-11 03:07:42,366 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 50 GetRequests, 16 SyntacticMatches, 4 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 1 DeprecatedPredicates, 153 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=176, Invalid=816, Unknown=0, NotChecked=0, Total=992 [2024-10-11 03:07:42,367 INFO L432 NwaCegarLoop]: 20 mSDtfsCounter, 60 mSDsluCounter, 164 mSDsCounter, 0 mSdLazyCounter, 506 mSolverCounterSat, 49 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 60 SdHoareTripleChecker+Valid, 184 SdHoareTripleChecker+Invalid, 555 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 49 IncrementalHoareTripleChecker+Valid, 506 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2024-10-11 03:07:42,367 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [60 Valid, 184 Invalid, 555 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [49 Valid, 506 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2024-10-11 03:07:42,368 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 81 states. [2024-10-11 03:07:42,389 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 81 to 79. [2024-10-11 03:07:42,390 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 79 states, 47 states have (on average 1.0851063829787233) internal successors, (51), 49 states have internal predecessors, (51), 24 states have call successors, (24), 7 states have call predecessors, (24), 7 states have return successors, (23), 23 states have call predecessors, (23), 22 states have call successors, (23) [2024-10-11 03:07:42,391 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 79 states to 79 states and 98 transitions. [2024-10-11 03:07:42,392 INFO L78 Accepts]: Start accepts. Automaton has 79 states and 98 transitions. Word has length 20 [2024-10-11 03:07:42,392 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 03:07:42,392 INFO L471 AbstractCegarLoop]: Abstraction has 79 states and 98 transitions. [2024-10-11 03:07:42,392 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 16 states have (on average 1.5625) internal successors, (25), 17 states have internal predecessors, (25), 7 states have call successors, (7), 6 states have call predecessors, (7), 4 states have return successors, (4), 2 states have call predecessors, (4), 4 states have call successors, (4) [2024-10-11 03:07:42,392 INFO L276 IsEmpty]: Start isEmpty. Operand 79 states and 98 transitions. [2024-10-11 03:07:42,393 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2024-10-11 03:07:42,393 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 03:07:42,393 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 03:07:42,410 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-10-11 03:07:42,597 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,3 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 03:07:42,598 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 03:07:42,598 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 03:07:42,599 INFO L85 PathProgramCache]: Analyzing trace with hash -1440093584, now seen corresponding path program 1 times [2024-10-11 03:07:42,599 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 03:07:42,599 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2043839020] [2024-10-11 03:07:42,599 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 03:07:42,599 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 03:07:42,646 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-11 03:07:42,650 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1375115229] [2024-10-11 03:07:42,650 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 03:07:42,650 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 03:07:42,650 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 03:07:42,652 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 03:07:42,654 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-10-11 03:07:42,749 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 03:07:42,751 INFO L255 TraceCheckSpWp]: Trace formula consists of 207 conjuncts, 60 conjuncts are in the unsatisfiable core [2024-10-11 03:07:42,755 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 03:07:42,759 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-10-11 03:07:42,765 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-10-11 03:07:42,770 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-10-11 03:07:43,271 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 2 proven. 12 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-11 03:07:43,271 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 03:07:43,528 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 53 treesize of output 41 [2024-10-11 03:07:43,626 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 5 proven. 7 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-10-11 03:07:43,626 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 03:07:43,627 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2043839020] [2024-10-11 03:07:43,627 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-11 03:07:43,627 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1375115229] [2024-10-11 03:07:43,627 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1375115229] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-11 03:07:43,627 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-11 03:07:43,627 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 12] total 22 [2024-10-11 03:07:43,628 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1121927736] [2024-10-11 03:07:43,628 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-11 03:07:43,628 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2024-10-11 03:07:43,629 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 03:07:43,629 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-10-11 03:07:43,630 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=64, Invalid=398, Unknown=0, NotChecked=0, Total=462 [2024-10-11 03:07:43,630 INFO L87 Difference]: Start difference. First operand 79 states and 98 transitions. Second operand has 22 states, 16 states have (on average 1.6875) internal successors, (27), 18 states have internal predecessors, (27), 8 states have call successors, (10), 6 states have call predecessors, (10), 4 states have return successors, (6), 2 states have call predecessors, (6), 4 states have call successors, (6) [2024-10-11 03:07:51,751 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [1] [2024-10-11 03:07:52,349 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 03:07:52,349 INFO L93 Difference]: Finished difference Result 109 states and 133 transitions. [2024-10-11 03:07:52,350 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2024-10-11 03:07:52,350 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 16 states have (on average 1.6875) internal successors, (27), 18 states have internal predecessors, (27), 8 states have call successors, (10), 6 states have call predecessors, (10), 4 states have return successors, (6), 2 states have call predecessors, (6), 4 states have call successors, (6) Word has length 26 [2024-10-11 03:07:52,350 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 03:07:52,353 INFO L225 Difference]: With dead ends: 109 [2024-10-11 03:07:52,353 INFO L226 Difference]: Without dead ends: 107 [2024-10-11 03:07:52,354 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 68 GetRequests, 26 SyntacticMatches, 5 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 256 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=235, Invalid=1247, Unknown=0, NotChecked=0, Total=1482 [2024-10-11 03:07:52,355 INFO L432 NwaCegarLoop]: 19 mSDtfsCounter, 77 mSDsluCounter, 158 mSDsCounter, 0 mSdLazyCounter, 779 mSolverCounterSat, 44 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 7.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 82 SdHoareTripleChecker+Valid, 177 SdHoareTripleChecker+Invalid, 824 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 44 IncrementalHoareTripleChecker+Valid, 779 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 7.8s IncrementalHoareTripleChecker+Time [2024-10-11 03:07:52,355 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [82 Valid, 177 Invalid, 824 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [44 Valid, 779 Invalid, 1 Unknown, 0 Unchecked, 7.8s Time] [2024-10-11 03:07:52,356 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 107 states. [2024-10-11 03:07:52,378 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 107 to 105. [2024-10-11 03:07:52,378 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 105 states, 63 states have (on average 1.0793650793650793) internal successors, (68), 66 states have internal predecessors, (68), 30 states have call successors, (30), 10 states have call predecessors, (30), 11 states have return successors, (31), 29 states have call predecessors, (31), 28 states have call successors, (31) [2024-10-11 03:07:52,380 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 105 states to 105 states and 129 transitions. [2024-10-11 03:07:52,380 INFO L78 Accepts]: Start accepts. Automaton has 105 states and 129 transitions. Word has length 26 [2024-10-11 03:07:52,380 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 03:07:52,382 INFO L471 AbstractCegarLoop]: Abstraction has 105 states and 129 transitions. [2024-10-11 03:07:52,382 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 16 states have (on average 1.6875) internal successors, (27), 18 states have internal predecessors, (27), 8 states have call successors, (10), 6 states have call predecessors, (10), 4 states have return successors, (6), 2 states have call predecessors, (6), 4 states have call successors, (6) [2024-10-11 03:07:52,383 INFO L276 IsEmpty]: Start isEmpty. Operand 105 states and 129 transitions. [2024-10-11 03:07:52,383 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2024-10-11 03:07:52,383 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 03:07:52,383 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 03:07:52,401 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-10-11 03:07:52,584 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 03:07:52,585 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 03:07:52,585 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 03:07:52,585 INFO L85 PathProgramCache]: Analyzing trace with hash -1224682067, now seen corresponding path program 1 times [2024-10-11 03:07:52,585 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 03:07:52,586 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1598831559] [2024-10-11 03:07:52,586 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 03:07:52,586 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 03:07:52,608 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-11 03:07:52,610 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1651380787] [2024-10-11 03:07:52,610 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 03:07:52,611 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 03:07:52,611 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 03:07:52,614 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 03:07:52,616 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-10-11 03:07:52,716 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 03:07:52,718 INFO L255 TraceCheckSpWp]: Trace formula consists of 224 conjuncts, 35 conjuncts are in the unsatisfiable core [2024-10-11 03:07:52,721 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 03:07:52,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 11 treesize of output 7 [2024-10-11 03:07:52,741 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-10-11 03:07:53,765 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 0 proven. 8 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-10-11 03:07:53,765 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 03:07:54,336 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-10-11 03:07:54,336 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 03:07:54,336 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1598831559] [2024-10-11 03:07:54,337 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-11 03:07:54,337 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1651380787] [2024-10-11 03:07:54,337 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1651380787] provided 1 perfect and 1 imperfect interpolant sequences [2024-10-11 03:07:54,337 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-10-11 03:07:54,337 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [8] total 13 [2024-10-11 03:07:54,337 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1252791600] [2024-10-11 03:07:54,337 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-11 03:07:54,337 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-10-11 03:07:54,338 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 03:07:54,338 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-10-11 03:07:54,338 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=126, Unknown=0, NotChecked=0, Total=156 [2024-10-11 03:07:54,339 INFO L87 Difference]: Start difference. First operand 105 states and 129 transitions. Second operand has 8 states, 6 states have (on average 2.1666666666666665) internal successors, (13), 6 states have internal predecessors, (13), 3 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-10-11 03:07:55,297 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 03:07:55,297 INFO L93 Difference]: Finished difference Result 119 states and 143 transitions. [2024-10-11 03:07:55,298 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-10-11 03:07:55,298 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 6 states have (on average 2.1666666666666665) internal successors, (13), 6 states have internal predecessors, (13), 3 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 32 [2024-10-11 03:07:55,298 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 03:07:55,299 INFO L225 Difference]: With dead ends: 119 [2024-10-11 03:07:55,299 INFO L226 Difference]: Without dead ends: 117 [2024-10-11 03:07:55,300 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 65 GetRequests, 42 SyntacticMatches, 9 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 25 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=44, Invalid=196, Unknown=0, NotChecked=0, Total=240 [2024-10-11 03:07:55,300 INFO L432 NwaCegarLoop]: 32 mSDtfsCounter, 22 mSDsluCounter, 111 mSDsCounter, 0 mSdLazyCounter, 170 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 143 SdHoareTripleChecker+Invalid, 181 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 170 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2024-10-11 03:07:55,301 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [27 Valid, 143 Invalid, 181 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 170 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2024-10-11 03:07:55,303 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 117 states. [2024-10-11 03:07:55,337 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 117 to 117. [2024-10-11 03:07:55,337 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 117 states, 71 states have (on average 1.0704225352112675) internal successors, (76), 74 states have internal predecessors, (76), 30 states have call successors, (30), 12 states have call predecessors, (30), 15 states have return successors, (34), 30 states have call predecessors, (34), 28 states have call successors, (34) [2024-10-11 03:07:55,338 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 117 states to 117 states and 140 transitions. [2024-10-11 03:07:55,339 INFO L78 Accepts]: Start accepts. Automaton has 117 states and 140 transitions. Word has length 32 [2024-10-11 03:07:55,339 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 03:07:55,339 INFO L471 AbstractCegarLoop]: Abstraction has 117 states and 140 transitions. [2024-10-11 03:07:55,339 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 6 states have (on average 2.1666666666666665) internal successors, (13), 6 states have internal predecessors, (13), 3 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-10-11 03:07:55,339 INFO L276 IsEmpty]: Start isEmpty. Operand 117 states and 140 transitions. [2024-10-11 03:07:55,340 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2024-10-11 03:07:55,340 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 03:07:55,341 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 03:07:55,359 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-10-11 03:07:55,541 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 03:07:55,541 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 03:07:55,542 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 03:07:55,542 INFO L85 PathProgramCache]: Analyzing trace with hash -1299588988, now seen corresponding path program 1 times [2024-10-11 03:07:55,542 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 03:07:55,543 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1838798656] [2024-10-11 03:07:55,543 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 03:07:55,543 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 03:07:55,577 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 03:07:56,532 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-11 03:07:56,534 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 03:07:56,537 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-10-11 03:07:56,539 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 03:07:56,542 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2024-10-11 03:07:56,543 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 03:07:56,546 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 22 [2024-10-11 03:07:56,547 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 03:07:56,550 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 28 [2024-10-11 03:07:56,551 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 03:07:56,554 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 10 proven. 3 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2024-10-11 03:07:56,554 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 03:07:56,554 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1838798656] [2024-10-11 03:07:56,555 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1838798656] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-11 03:07:56,555 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [684407714] [2024-10-11 03:07:56,555 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 03:07:56,555 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 03:07:56,555 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 03:07:56,557 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 03:07:56,560 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-10-11 03:07:56,683 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 03:07:56,690 INFO L255 TraceCheckSpWp]: Trace formula consists of 306 conjuncts, 66 conjuncts are in the unsatisfiable core [2024-10-11 03:07:56,695 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 03:07:56,712 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-10-11 03:07:56,735 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-10-11 03:07:58,238 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-10-11 03:07:58,255 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-10-11 03:07:58,459 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 0 proven. 25 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-10-11 03:07:58,459 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 03:08:03,419 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 11 proven. 14 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-10-11 03:08:03,419 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [684407714] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-11 03:08:03,419 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-11 03:08:03,419 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 13, 10] total 22 [2024-10-11 03:08:03,419 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1525218311] [2024-10-11 03:08:03,419 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-11 03:08:03,420 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2024-10-11 03:08:03,420 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 03:08:03,421 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-10-11 03:08:03,422 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=70, Invalid=391, Unknown=1, NotChecked=0, Total=462 [2024-10-11 03:08:03,422 INFO L87 Difference]: Start difference. First operand 117 states and 140 transitions. Second operand has 22 states, 17 states have (on average 2.3529411764705883) internal successors, (40), 17 states have internal predecessors, (40), 9 states have call successors, (22), 7 states have call predecessors, (22), 4 states have return successors, (15), 2 states have call predecessors, (15), 4 states have call successors, (15) [2024-10-11 03:08:09,382 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.02s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2024-10-11 03:08:13,505 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.03s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2024-10-11 03:08:15,266 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 03:08:15,266 INFO L93 Difference]: Finished difference Result 125 states and 146 transitions. [2024-10-11 03:08:15,267 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2024-10-11 03:08:15,267 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 17 states have (on average 2.3529411764705883) internal successors, (40), 17 states have internal predecessors, (40), 9 states have call successors, (22), 7 states have call predecessors, (22), 4 states have return successors, (15), 2 states have call predecessors, (15), 4 states have call successors, (15) Word has length 42 [2024-10-11 03:08:15,267 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 03:08:15,268 INFO L225 Difference]: With dead ends: 125 [2024-10-11 03:08:15,268 INFO L226 Difference]: Without dead ends: 123 [2024-10-11 03:08:15,269 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 114 GetRequests, 74 SyntacticMatches, 11 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 180 ImplicationChecksByTransitivity, 6.5s TimeCoverageRelationStatistics Valid=153, Invalid=776, Unknown=1, NotChecked=0, Total=930 [2024-10-11 03:08:15,270 INFO L432 NwaCegarLoop]: 25 mSDtfsCounter, 87 mSDsluCounter, 158 mSDsCounter, 0 mSdLazyCounter, 693 mSolverCounterSat, 39 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 10.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 92 SdHoareTripleChecker+Valid, 183 SdHoareTripleChecker+Invalid, 734 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 39 IncrementalHoareTripleChecker+Valid, 693 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 11.1s IncrementalHoareTripleChecker+Time [2024-10-11 03:08:15,270 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [92 Valid, 183 Invalid, 734 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [39 Valid, 693 Invalid, 2 Unknown, 0 Unchecked, 11.1s Time] [2024-10-11 03:08:15,271 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 123 states. [2024-10-11 03:08:15,303 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 123 to 121. [2024-10-11 03:08:15,304 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 121 states, 74 states have (on average 1.0675675675675675) internal successors, (79), 77 states have internal predecessors, (79), 30 states have call successors, (30), 13 states have call predecessors, (30), 16 states have return successors, (34), 30 states have call predecessors, (34), 28 states have call successors, (34) [2024-10-11 03:08:15,306 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 121 states to 121 states and 143 transitions. [2024-10-11 03:08:15,309 INFO L78 Accepts]: Start accepts. Automaton has 121 states and 143 transitions. Word has length 42 [2024-10-11 03:08:15,310 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 03:08:15,310 INFO L471 AbstractCegarLoop]: Abstraction has 121 states and 143 transitions. [2024-10-11 03:08:15,310 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 17 states have (on average 2.3529411764705883) internal successors, (40), 17 states have internal predecessors, (40), 9 states have call successors, (22), 7 states have call predecessors, (22), 4 states have return successors, (15), 2 states have call predecessors, (15), 4 states have call successors, (15) [2024-10-11 03:08:15,310 INFO L276 IsEmpty]: Start isEmpty. Operand 121 states and 143 transitions. [2024-10-11 03:08:15,311 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2024-10-11 03:08:15,311 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 03:08:15,311 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 03:08:15,330 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2024-10-11 03:08:15,512 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 03:08:15,512 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 03:08:15,513 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 03:08:15,513 INFO L85 PathProgramCache]: Analyzing trace with hash 277886434, now seen corresponding path program 1 times [2024-10-11 03:08:15,513 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 03:08:15,513 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1687328451] [2024-10-11 03:08:15,513 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 03:08:15,514 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 03:08:15,536 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 03:08:15,934 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-11 03:08:15,940 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 03:08:16,078 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-10-11 03:08:16,080 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 03:08:16,082 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-10-11 03:08:16,084 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 03:08:16,086 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-10-11 03:08:16,087 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 03:08:16,089 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 20 [2024-10-11 03:08:16,090 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 03:08:16,092 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 26 [2024-10-11 03:08:16,093 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 03:08:16,095 INFO L134 CoverageAnalysis]: Checked inductivity of 50 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2024-10-11 03:08:16,096 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 03:08:16,096 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1687328451] [2024-10-11 03:08:16,096 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1687328451] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-11 03:08:16,096 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-11 03:08:16,096 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2024-10-11 03:08:16,096 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1659504577] [2024-10-11 03:08:16,096 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-11 03:08:16,097 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-10-11 03:08:16,097 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 03:08:16,097 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-10-11 03:08:16,097 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2024-10-11 03:08:16,097 INFO L87 Difference]: Start difference. First operand 121 states and 143 transitions. Second operand has 8 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 6 states have internal predecessors, (17), 3 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2024-10-11 03:08:16,991 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 03:08:16,991 INFO L93 Difference]: Finished difference Result 127 states and 148 transitions. [2024-10-11 03:08:16,991 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-10-11 03:08:16,992 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 6 states have internal predecessors, (17), 3 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 42 [2024-10-11 03:08:16,992 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 03:08:16,993 INFO L225 Difference]: With dead ends: 127 [2024-10-11 03:08:16,993 INFO L226 Difference]: Without dead ends: 125 [2024-10-11 03:08:16,993 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 21 GetRequests, 13 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=26, Invalid=64, Unknown=0, NotChecked=0, Total=90 [2024-10-11 03:08:16,994 INFO L432 NwaCegarLoop]: 26 mSDtfsCounter, 17 mSDsluCounter, 66 mSDsCounter, 0 mSdLazyCounter, 185 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 23 SdHoareTripleChecker+Valid, 92 SdHoareTripleChecker+Invalid, 198 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 185 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2024-10-11 03:08:16,994 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [23 Valid, 92 Invalid, 198 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 185 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2024-10-11 03:08:16,994 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 125 states. [2024-10-11 03:08:17,023 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 125 to 125. [2024-10-11 03:08:17,024 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 125 states, 77 states have (on average 1.0649350649350648) internal successors, (82), 80 states have internal predecessors, (82), 30 states have call successors, (30), 14 states have call predecessors, (30), 17 states have return successors, (34), 30 states have call predecessors, (34), 28 states have call successors, (34) [2024-10-11 03:08:17,024 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 125 states to 125 states and 146 transitions. [2024-10-11 03:08:17,025 INFO L78 Accepts]: Start accepts. Automaton has 125 states and 146 transitions. Word has length 42 [2024-10-11 03:08:17,025 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 03:08:17,025 INFO L471 AbstractCegarLoop]: Abstraction has 125 states and 146 transitions. [2024-10-11 03:08:17,025 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 6 states have internal predecessors, (17), 3 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2024-10-11 03:08:17,025 INFO L276 IsEmpty]: Start isEmpty. Operand 125 states and 146 transitions. [2024-10-11 03:08:17,026 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 49 [2024-10-11 03:08:17,026 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 03:08:17,027 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 03:08:17,027 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6 [2024-10-11 03:08:17,027 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 03:08:17,027 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 03:08:17,028 INFO L85 PathProgramCache]: Analyzing trace with hash -560035385, now seen corresponding path program 2 times [2024-10-11 03:08:17,028 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 03:08:17,028 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [279159265] [2024-10-11 03:08:17,028 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 03:08:17,028 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 03:08:17,054 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-11 03:08:17,057 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [243866341] [2024-10-11 03:08:17,057 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-10-11 03:08:17,057 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 03:08:17,057 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 03:08:17,059 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 03:08:17,061 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-10-11 03:08:17,197 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-10-11 03:08:17,197 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-11 03:08:17,201 INFO L255 TraceCheckSpWp]: Trace formula consists of 323 conjuncts, 86 conjuncts are in the unsatisfiable core [2024-10-11 03:08:17,207 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 03:08:17,225 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-10-11 03:08:17,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 11 treesize of output 7 [2024-10-11 03:08:17,269 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-10-11 03:08:19,032 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-10-11 03:08:19,051 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-10-11 03:08:19,061 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-10-11 03:08:19,839 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 12 proven. 37 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-10-11 03:08:19,840 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 03:08:21,234 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 12 proven. 5 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2024-10-11 03:08:21,234 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 03:08:21,234 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [279159265] [2024-10-11 03:08:21,234 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-11 03:08:21,234 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [243866341] [2024-10-11 03:08:21,234 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [243866341] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-11 03:08:21,235 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-11 03:08:21,235 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 10] total 20 [2024-10-11 03:08:21,235 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1822648596] [2024-10-11 03:08:21,235 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-11 03:08:21,235 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2024-10-11 03:08:21,235 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 03:08:21,236 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2024-10-11 03:08:21,236 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=52, Invalid=328, Unknown=0, NotChecked=0, Total=380 [2024-10-11 03:08:21,236 INFO L87 Difference]: Start difference. First operand 125 states and 146 transitions. Second operand has 20 states, 16 states have (on average 2.4375) internal successors, (39), 15 states have internal predecessors, (39), 8 states have call successors, (18), 8 states have call predecessors, (18), 4 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2024-10-11 03:08:25,886 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 03:08:25,886 INFO L93 Difference]: Finished difference Result 163 states and 184 transitions. [2024-10-11 03:08:25,887 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2024-10-11 03:08:25,887 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 16 states have (on average 2.4375) internal successors, (39), 15 states have internal predecessors, (39), 8 states have call successors, (18), 8 states have call predecessors, (18), 4 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) Word has length 48 [2024-10-11 03:08:25,887 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 03:08:25,888 INFO L225 Difference]: With dead ends: 163 [2024-10-11 03:08:25,888 INFO L226 Difference]: Without dead ends: 161 [2024-10-11 03:08:25,889 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 109 GetRequests, 64 SyntacticMatches, 12 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 208 ImplicationChecksByTransitivity, 3.3s TimeCoverageRelationStatistics Valid=182, Invalid=1008, Unknown=0, NotChecked=0, Total=1190 [2024-10-11 03:08:25,890 INFO L432 NwaCegarLoop]: 45 mSDtfsCounter, 139 mSDsluCounter, 264 mSDsCounter, 0 mSdLazyCounter, 931 mSolverCounterSat, 68 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 144 SdHoareTripleChecker+Valid, 309 SdHoareTripleChecker+Invalid, 999 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 68 IncrementalHoareTripleChecker+Valid, 931 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.3s IncrementalHoareTripleChecker+Time [2024-10-11 03:08:25,890 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [144 Valid, 309 Invalid, 999 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [68 Valid, 931 Invalid, 0 Unknown, 0 Unchecked, 3.3s Time] [2024-10-11 03:08:25,891 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 161 states. [2024-10-11 03:08:25,919 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 161 to 157. [2024-10-11 03:08:25,920 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 157 states, 98 states have (on average 1.0612244897959184) internal successors, (104), 101 states have internal predecessors, (104), 36 states have call successors, (36), 19 states have call predecessors, (36), 22 states have return successors, (39), 36 states have call predecessors, (39), 33 states have call successors, (39) [2024-10-11 03:08:25,921 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 157 states to 157 states and 179 transitions. [2024-10-11 03:08:25,921 INFO L78 Accepts]: Start accepts. Automaton has 157 states and 179 transitions. Word has length 48 [2024-10-11 03:08:25,921 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 03:08:25,921 INFO L471 AbstractCegarLoop]: Abstraction has 157 states and 179 transitions. [2024-10-11 03:08:25,922 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 16 states have (on average 2.4375) internal successors, (39), 15 states have internal predecessors, (39), 8 states have call successors, (18), 8 states have call predecessors, (18), 4 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2024-10-11 03:08:25,922 INFO L276 IsEmpty]: Start isEmpty. Operand 157 states and 179 transitions. [2024-10-11 03:08:25,923 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 49 [2024-10-11 03:08:25,923 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 03:08:25,923 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 03:08:25,941 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-10-11 03:08:26,123 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable7 [2024-10-11 03:08:26,124 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 03:08:26,124 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 03:08:26,124 INFO L85 PathProgramCache]: Analyzing trace with hash 1232163489, now seen corresponding path program 1 times [2024-10-11 03:08:26,124 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 03:08:26,125 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [392474657] [2024-10-11 03:08:26,125 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 03:08:26,125 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 03:08:26,148 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-11 03:08:26,152 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1574636198] [2024-10-11 03:08:26,153 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 03:08:26,153 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 03:08:26,153 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 03:08:26,155 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 03:08:26,160 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-10-11 03:08:26,253 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 03:08:26,254 INFO L255 TraceCheckSpWp]: Trace formula consists of 263 conjuncts, 52 conjuncts are in the unsatisfiable core [2024-10-11 03:08:26,257 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 03:08:26,273 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-10-11 03:08:26,292 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-10-11 03:08:26,315 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 48 treesize of output 35 [2024-10-11 03:08:26,331 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 1 [2024-10-11 03:08:26,361 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 1 [2024-10-11 03:08:29,871 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 11 [2024-10-11 03:08:31,579 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-10-11 03:08:31,579 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 78 treesize of output 78 [2024-10-11 03:08:32,028 INFO L134 CoverageAnalysis]: Checked inductivity of 72 backedges. 5 proven. 43 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-10-11 03:08:32,029 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 03:08:32,722 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 03:08:32,722 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [392474657] [2024-10-11 03:08:32,722 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-11 03:08:32,722 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1574636198] [2024-10-11 03:08:32,722 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1574636198] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-11 03:08:32,722 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-10-11 03:08:32,722 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16] total 16 [2024-10-11 03:08:32,723 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1993789850] [2024-10-11 03:08:32,723 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-10-11 03:08:32,723 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-10-11 03:08:32,723 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 03:08:32,724 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-10-11 03:08:32,724 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=58, Invalid=284, Unknown=0, NotChecked=0, Total=342 [2024-10-11 03:08:32,725 INFO L87 Difference]: Start difference. First operand 157 states and 179 transitions. Second operand has 17 states, 14 states have (on average 1.7142857142857142) internal successors, (24), 13 states have internal predecessors, (24), 5 states have call successors, (8), 5 states have call predecessors, (8), 4 states have return successors, (7), 2 states have call predecessors, (7), 4 states have call successors, (7) [2024-10-11 03:08:39,037 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 03:08:39,037 INFO L93 Difference]: Finished difference Result 165 states and 185 transitions. [2024-10-11 03:08:39,038 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2024-10-11 03:08:39,038 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 14 states have (on average 1.7142857142857142) internal successors, (24), 13 states have internal predecessors, (24), 5 states have call successors, (8), 5 states have call predecessors, (8), 4 states have return successors, (7), 2 states have call predecessors, (7), 4 states have call successors, (7) Word has length 48 [2024-10-11 03:08:39,038 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 03:08:39,039 INFO L225 Difference]: With dead ends: 165 [2024-10-11 03:08:39,039 INFO L226 Difference]: Without dead ends: 163 [2024-10-11 03:08:39,040 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 73 GetRequests, 26 SyntacticMatches, 10 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 357 ImplicationChecksByTransitivity, 6.4s TimeCoverageRelationStatistics Valid=280, Invalid=1202, Unknown=0, NotChecked=0, Total=1482 [2024-10-11 03:08:39,041 INFO L432 NwaCegarLoop]: 15 mSDtfsCounter, 104 mSDsluCounter, 48 mSDsCounter, 0 mSdLazyCounter, 461 mSolverCounterSat, 104 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 109 SdHoareTripleChecker+Valid, 63 SdHoareTripleChecker+Invalid, 566 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 104 IncrementalHoareTripleChecker+Valid, 461 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.5s IncrementalHoareTripleChecker+Time [2024-10-11 03:08:39,041 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [109 Valid, 63 Invalid, 566 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [104 Valid, 461 Invalid, 1 Unknown, 0 Unchecked, 2.5s Time] [2024-10-11 03:08:39,043 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 163 states. [2024-10-11 03:08:39,093 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 163 to 161. [2024-10-11 03:08:39,094 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 161 states, 101 states have (on average 1.0594059405940595) internal successors, (107), 104 states have internal predecessors, (107), 36 states have call successors, (36), 20 states have call predecessors, (36), 23 states have return successors, (39), 36 states have call predecessors, (39), 33 states have call successors, (39) [2024-10-11 03:08:39,095 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 161 states to 161 states and 182 transitions. [2024-10-11 03:08:39,096 INFO L78 Accepts]: Start accepts. Automaton has 161 states and 182 transitions. Word has length 48 [2024-10-11 03:08:39,096 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 03:08:39,097 INFO L471 AbstractCegarLoop]: Abstraction has 161 states and 182 transitions. [2024-10-11 03:08:39,097 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 14 states have (on average 1.7142857142857142) internal successors, (24), 13 states have internal predecessors, (24), 5 states have call successors, (8), 5 states have call predecessors, (8), 4 states have return successors, (7), 2 states have call predecessors, (7), 4 states have call successors, (7) [2024-10-11 03:08:39,098 INFO L276 IsEmpty]: Start isEmpty. Operand 161 states and 182 transitions. [2024-10-11 03:08:39,098 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2024-10-11 03:08:39,100 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 03:08:39,101 INFO L215 NwaCegarLoop]: trace histogram [8, 7, 7, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 03:08:39,120 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2024-10-11 03:08:39,301 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 03:08:39,302 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 03:08:39,302 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 03:08:39,302 INFO L85 PathProgramCache]: Analyzing trace with hash -1233992248, now seen corresponding path program 3 times [2024-10-11 03:08:39,302 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 03:08:39,302 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1969977677] [2024-10-11 03:08:39,302 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 03:08:39,303 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 03:08:39,341 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-11 03:08:39,343 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1342249082] [2024-10-11 03:08:39,343 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-10-11 03:08:39,343 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 03:08:39,347 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 03:08:39,349 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 03:08:39,362 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-10-11 03:08:39,482 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2024-10-11 03:08:39,482 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-11 03:08:39,484 INFO L255 TraceCheckSpWp]: Trace formula consists of 253 conjuncts, 78 conjuncts are in the unsatisfiable core [2024-10-11 03:08:39,488 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 03:08:39,503 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-10-11 03:08:39,527 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-10-11 03:08:39,549 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-10-11 03:08:41,086 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-10-11 03:08:41,118 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-10-11 03:08:42,018 INFO L134 CoverageAnalysis]: Checked inductivity of 105 backedges. 0 proven. 61 refuted. 0 times theorem prover too weak. 44 trivial. 0 not checked. [2024-10-11 03:08:42,018 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 03:08:43,023 INFO L134 CoverageAnalysis]: Checked inductivity of 105 backedges. 14 proven. 7 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2024-10-11 03:08:43,023 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 03:08:43,023 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1969977677] [2024-10-11 03:08:43,023 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-11 03:08:43,024 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1342249082] [2024-10-11 03:08:43,032 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1342249082] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-11 03:08:43,032 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-11 03:08:43,032 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 10] total 20 [2024-10-11 03:08:43,032 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [107803689] [2024-10-11 03:08:43,032 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-11 03:08:43,033 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2024-10-11 03:08:43,033 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 03:08:43,033 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2024-10-11 03:08:43,034 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=52, Invalid=328, Unknown=0, NotChecked=0, Total=380 [2024-10-11 03:08:43,034 INFO L87 Difference]: Start difference. First operand 161 states and 182 transitions. Second operand has 20 states, 16 states have (on average 2.5) internal successors, (40), 14 states have internal predecessors, (40), 8 states have call successors, (20), 9 states have call predecessors, (20), 3 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2024-10-11 03:08:47,506 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 03:08:47,506 INFO L93 Difference]: Finished difference Result 171 states and 189 transitions. [2024-10-11 03:08:47,507 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2024-10-11 03:08:47,507 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 16 states have (on average 2.5) internal successors, (40), 14 states have internal predecessors, (40), 8 states have call successors, (20), 9 states have call predecessors, (20), 3 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) Word has length 54 [2024-10-11 03:08:47,507 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 03:08:47,508 INFO L225 Difference]: With dead ends: 171 [2024-10-11 03:08:47,509 INFO L226 Difference]: Without dead ends: 169 [2024-10-11 03:08:47,509 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 115 GetRequests, 77 SyntacticMatches, 12 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 92 ImplicationChecksByTransitivity, 2.5s TimeCoverageRelationStatistics Valid=115, Invalid=641, Unknown=0, NotChecked=0, Total=756 [2024-10-11 03:08:47,510 INFO L432 NwaCegarLoop]: 54 mSDtfsCounter, 95 mSDsluCounter, 377 mSDsCounter, 0 mSdLazyCounter, 870 mSolverCounterSat, 31 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 95 SdHoareTripleChecker+Valid, 431 SdHoareTripleChecker+Invalid, 901 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 31 IncrementalHoareTripleChecker+Valid, 870 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.6s IncrementalHoareTripleChecker+Time [2024-10-11 03:08:47,510 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [95 Valid, 431 Invalid, 901 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [31 Valid, 870 Invalid, 0 Unknown, 0 Unchecked, 3.6s Time] [2024-10-11 03:08:47,510 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 169 states. [2024-10-11 03:08:47,561 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 169 to 165. [2024-10-11 03:08:47,561 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 165 states, 104 states have (on average 1.0576923076923077) internal successors, (110), 107 states have internal predecessors, (110), 36 states have call successors, (36), 21 states have call predecessors, (36), 24 states have return successors, (39), 36 states have call predecessors, (39), 33 states have call successors, (39) [2024-10-11 03:08:47,562 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 165 states to 165 states and 185 transitions. [2024-10-11 03:08:47,562 INFO L78 Accepts]: Start accepts. Automaton has 165 states and 185 transitions. Word has length 54 [2024-10-11 03:08:47,563 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 03:08:47,563 INFO L471 AbstractCegarLoop]: Abstraction has 165 states and 185 transitions. [2024-10-11 03:08:47,563 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 16 states have (on average 2.5) internal successors, (40), 14 states have internal predecessors, (40), 8 states have call successors, (20), 9 states have call predecessors, (20), 3 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2024-10-11 03:08:47,563 INFO L276 IsEmpty]: Start isEmpty. Operand 165 states and 185 transitions. [2024-10-11 03:08:47,564 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2024-10-11 03:08:47,564 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 03:08:47,564 INFO L215 NwaCegarLoop]: trace histogram [8, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 03:08:47,579 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2024-10-11 03:08:47,764 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2024-10-11 03:08:47,765 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 03:08:47,765 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 03:08:47,765 INFO L85 PathProgramCache]: Analyzing trace with hash 1062890782, now seen corresponding path program 1 times [2024-10-11 03:08:47,765 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 03:08:47,765 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [650945566] [2024-10-11 03:08:47,765 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 03:08:47,766 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 03:08:47,784 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-11 03:08:47,787 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1948550987] [2024-10-11 03:08:47,787 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 03:08:47,787 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 03:08:47,787 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 03:08:47,789 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 03:08:47,791 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-10-11 03:08:47,904 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 03:08:47,907 INFO L255 TraceCheckSpWp]: Trace formula consists of 282 conjuncts, 49 conjuncts are in the unsatisfiable core [2024-10-11 03:08:47,910 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 03:08:47,926 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 48 treesize of output 35 [2024-10-11 03:08:47,964 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 1 [2024-10-11 03:08:47,991 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 1 [2024-10-11 03:08:48,016 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-10-11 03:08:48,041 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-10-11 03:08:51,056 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 23 treesize of output 15 [2024-10-11 03:09:01,434 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-10-11 03:09:01,434 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 68 treesize of output 72 [2024-10-11 03:09:01,924 INFO L134 CoverageAnalysis]: Checked inductivity of 98 backedges. 6 proven. 64 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-10-11 03:09:01,924 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 03:09:03,082 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 29 treesize of output 21 [2024-10-11 03:09:04,052 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 03:09:04,052 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [650945566] [2024-10-11 03:09:04,052 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-11 03:09:04,052 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1948550987] [2024-10-11 03:09:04,052 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1948550987] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-11 03:09:04,052 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-10-11 03:09:04,052 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17] total 17 [2024-10-11 03:09:04,052 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1732515398] [2024-10-11 03:09:04,052 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-10-11 03:09:04,053 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2024-10-11 03:09:04,053 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 03:09:04,053 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2024-10-11 03:09:04,053 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=78, Invalid=473, Unknown=1, NotChecked=0, Total=552 [2024-10-11 03:09:04,054 INFO L87 Difference]: Start difference. First operand 165 states and 185 transitions. Second operand has 18 states, 15 states have (on average 1.6666666666666667) internal successors, (25), 14 states have internal predecessors, (25), 5 states have call successors, (9), 5 states have call predecessors, (9), 4 states have return successors, (8), 2 states have call predecessors, (8), 4 states have call successors, (8)