./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/recursified_nla-digbench/recursified_sqrt1-ll.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 798a7b37 Calling Ultimate with: /root/.sdkman/candidates/java/21.0.5-tem/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/recursified_nla-digbench/recursified_sqrt1-ll.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash ac02a57e98f6481647f49b84c91fda6d0505e35fbffb37ed6b508f20e911a1af --- Real Ultimate output --- This is Ultimate 0.3.0-?-798a7b3-m [2025-03-03 14:41:45,973 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-03 14:41:46,026 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2025-03-03 14:41:46,029 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-03 14:41:46,029 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-03 14:41:46,049 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-03 14:41:46,050 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-03 14:41:46,050 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-03 14:41:46,050 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-03 14:41:46,051 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-03 14:41:46,051 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-03-03 14:41:46,051 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-03-03 14:41:46,052 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-03 14:41:46,052 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-03 14:41:46,052 INFO L153 SettingsManager]: * Use SBE=true [2025-03-03 14:41:46,052 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-03 14:41:46,052 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-03-03 14:41:46,053 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-03 14:41:46,053 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-03 14:41:46,053 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-03 14:41:46,053 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-03 14:41:46,053 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-03-03 14:41:46,053 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-03-03 14:41:46,053 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-03-03 14:41:46,053 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-03 14:41:46,053 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-03 14:41:46,053 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-03 14:41:46,053 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-03 14:41:46,053 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-03 14:41:46,054 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-03 14:41:46,054 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-03-03 14:41:46,054 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-03-03 14:41:46,054 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-03 14:41:46,054 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-03 14:41:46,054 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-03-03 14:41:46,054 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-03-03 14:41:46,054 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-03-03 14:41:46,054 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-03 14:41:46,055 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-03-03 14:41:46,055 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-03-03 14:41:46,055 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-03-03 14:41:46,055 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-03-03 14:41:46,055 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-03-03 14:41:46,055 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> ac02a57e98f6481647f49b84c91fda6d0505e35fbffb37ed6b508f20e911a1af [2025-03-03 14:41:46,266 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-03 14:41:46,275 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-03 14:41:46,277 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-03 14:41:46,278 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-03 14:41:46,278 INFO L274 PluginConnector]: CDTParser initialized [2025-03-03 14:41:46,280 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursified_nla-digbench/recursified_sqrt1-ll.c [2025-03-03 14:41:47,360 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/2791fcab4/b135f9c265dd4cf295c71bcf562aa083/FLAGc8d789811 [2025-03-03 14:41:47,539 INFO L384 CDTParser]: Found 1 translation units. [2025-03-03 14:41:47,540 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursified_nla-digbench/recursified_sqrt1-ll.c [2025-03-03 14:41:47,548 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/2791fcab4/b135f9c265dd4cf295c71bcf562aa083/FLAGc8d789811 [2025-03-03 14:41:47,920 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/2791fcab4/b135f9c265dd4cf295c71bcf562aa083 [2025-03-03 14:41:47,921 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-03 14:41:47,922 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-03 14:41:47,923 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-03 14:41:47,923 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-03 14:41:47,926 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-03 14:41:47,926 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 03.03 02:41:47" (1/1) ... [2025-03-03 14:41:47,927 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@24975776 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:41:47, skipping insertion in model container [2025-03-03 14:41:47,927 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 03.03 02:41:47" (1/1) ... [2025-03-03 14:41:47,935 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-03 14:41:48,025 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursified_nla-digbench/recursified_sqrt1-ll.c[1052,1065] [2025-03-03 14:41:48,041 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-03 14:41:48,048 INFO L200 MainTranslator]: Completed pre-run [2025-03-03 14:41:48,056 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursified_nla-digbench/recursified_sqrt1-ll.c[1052,1065] [2025-03-03 14:41:48,065 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-03 14:41:48,077 INFO L204 MainTranslator]: Completed translation [2025-03-03 14:41:48,077 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:41:48 WrapperNode [2025-03-03 14:41:48,078 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-03 14:41:48,078 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-03 14:41:48,078 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-03 14:41:48,078 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-03 14:41:48,082 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:41:48" (1/1) ... [2025-03-03 14:41:48,087 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:41:48" (1/1) ... [2025-03-03 14:41:48,101 INFO L138 Inliner]: procedures = 16, calls = 58, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 60 [2025-03-03 14:41:48,102 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-03 14:41:48,102 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-03 14:41:48,103 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-03 14:41:48,103 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-03 14:41:48,107 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:41:48" (1/1) ... [2025-03-03 14:41:48,108 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:41:48" (1/1) ... [2025-03-03 14:41:48,109 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:41:48" (1/1) ... [2025-03-03 14:41:48,118 INFO L175 MemorySlicer]: Split 33 memory accesses to 5 slices as follows [2, 9, 2, 12, 8]. 36 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2, 0, 0, 0, 0]. The 7 writes are split as follows [0, 2, 1, 2, 2]. [2025-03-03 14:41:48,118 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:41:48" (1/1) ... [2025-03-03 14:41:48,118 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:41:48" (1/1) ... [2025-03-03 14:41:48,124 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:41:48" (1/1) ... [2025-03-03 14:41:48,124 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:41:48" (1/1) ... [2025-03-03 14:41:48,125 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:41:48" (1/1) ... [2025-03-03 14:41:48,126 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:41:48" (1/1) ... [2025-03-03 14:41:48,131 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-03 14:41:48,131 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-03 14:41:48,131 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-03 14:41:48,132 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-03 14:41:48,132 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:41:48" (1/1) ... [2025-03-03 14:41:48,136 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-03 14:41:48,146 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:41:48,157 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2025-03-03 14:41:48,162 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2025-03-03 14:41:48,176 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-03 14:41:48,176 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-03-03 14:41:48,176 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2025-03-03 14:41:48,176 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2025-03-03 14:41:48,176 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#3 [2025-03-03 14:41:48,176 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#4 [2025-03-03 14:41:48,176 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2025-03-03 14:41:48,176 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2025-03-03 14:41:48,177 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2025-03-03 14:41:48,177 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#2 [2025-03-03 14:41:48,177 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#3 [2025-03-03 14:41:48,177 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#4 [2025-03-03 14:41:48,178 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_29_to_40_0 [2025-03-03 14:41:48,178 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_29_to_40_0 [2025-03-03 14:41:48,178 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-03 14:41:48,178 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-03 14:41:48,178 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2025-03-03 14:41:48,178 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2025-03-03 14:41:48,178 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#2 [2025-03-03 14:41:48,178 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#3 [2025-03-03 14:41:48,178 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#4 [2025-03-03 14:41:48,178 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2025-03-03 14:41:48,178 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2025-03-03 14:41:48,178 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2025-03-03 14:41:48,245 INFO L256 CfgBuilder]: Building ICFG [2025-03-03 14:41:48,246 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-03 14:41:48,326 INFO L1325 $ProcedureCfgBuilder]: dead code at ProgramPoint L76: call ULTIMATE.dealloc(main_~#n~0#1.base, main_~#n~0#1.offset);havoc main_~#n~0#1.base, main_~#n~0#1.offset;call ULTIMATE.dealloc(main_~#a~0#1.base, main_~#a~0#1.offset);havoc main_~#a~0#1.base, main_~#a~0#1.offset;call ULTIMATE.dealloc(main_~#s~0#1.base, main_~#s~0#1.offset);havoc main_~#s~0#1.base, main_~#s~0#1.offset;call ULTIMATE.dealloc(main_~#t~0#1.base, main_~#t~0#1.offset);havoc main_~#t~0#1.base, main_~#t~0#1.offset; [2025-03-03 14:41:48,342 INFO L? ?]: Removed 7 outVars from TransFormulas that were not future-live. [2025-03-03 14:41:48,342 INFO L307 CfgBuilder]: Performing block encoding [2025-03-03 14:41:48,349 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-03 14:41:48,349 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-03 14:41:48,350 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 03.03 02:41:48 BoogieIcfgContainer [2025-03-03 14:41:48,350 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-03 14:41:48,351 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-03-03 14:41:48,352 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-03-03 14:41:48,354 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-03-03 14:41:48,354 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 03.03 02:41:47" (1/3) ... [2025-03-03 14:41:48,355 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@37fc999b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 03.03 02:41:48, skipping insertion in model container [2025-03-03 14:41:48,355 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:41:48" (2/3) ... [2025-03-03 14:41:48,355 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@37fc999b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 03.03 02:41:48, skipping insertion in model container [2025-03-03 14:41:48,355 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 03.03 02:41:48" (3/3) ... [2025-03-03 14:41:48,356 INFO L128 eAbstractionObserver]: Analyzing ICFG recursified_sqrt1-ll.c [2025-03-03 14:41:48,365 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-03-03 14:41:48,366 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG recursified_sqrt1-ll.c that has 3 procedures, 31 locations, 1 initial locations, 0 loop locations, and 1 error locations. [2025-03-03 14:41:48,398 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-03-03 14:41:48,407 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;@5508fb1f, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-03-03 14:41:48,407 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-03-03 14:41:48,410 INFO L276 IsEmpty]: Start isEmpty. Operand has 31 states, 19 states have (on average 1.2105263157894737) internal successors, (23), 21 states have internal predecessors, (23), 8 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2025-03-03 14:41:48,413 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2025-03-03 14:41:48,413 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:41:48,413 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:41:48,414 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:41:48,418 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:41:48,418 INFO L85 PathProgramCache]: Analyzing trace with hash 1531851238, now seen corresponding path program 1 times [2025-03-03 14:41:48,422 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:41:48,424 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1433236971] [2025-03-03 14:41:48,424 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:41:48,425 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:41:48,480 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 9 statements into 1 equivalence classes. [2025-03-03 14:41:48,510 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 9 of 9 statements. [2025-03-03 14:41:48,511 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:41:48,511 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:41:48,941 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-03 14:41:48,942 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:41:48,942 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1433236971] [2025-03-03 14:41:48,942 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1433236971] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 14:41:48,942 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 14:41:48,943 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2025-03-03 14:41:48,943 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [852896517] [2025-03-03 14:41:48,944 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 14:41:48,946 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2025-03-03 14:41:48,946 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:41:48,956 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-03-03 14:41:48,957 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2025-03-03 14:41:48,959 INFO L87 Difference]: Start difference. First operand has 31 states, 19 states have (on average 1.2105263157894737) internal successors, (23), 21 states have internal predecessors, (23), 8 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) Second operand has 8 states, 6 states have (on average 1.1666666666666667) internal successors, (7), 6 states have internal predecessors, (7), 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) [2025-03-03 14:41:49,129 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:41:49,130 INFO L93 Difference]: Finished difference Result 77 states and 110 transitions. [2025-03-03 14:41:49,131 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2025-03-03 14:41:49,131 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 6 states have (on average 1.1666666666666667) internal successors, (7), 6 states have internal predecessors, (7), 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 9 [2025-03-03 14:41:49,132 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:41:49,135 INFO L225 Difference]: With dead ends: 77 [2025-03-03 14:41:49,135 INFO L226 Difference]: Without dead ends: 45 [2025-03-03 14:41:49,137 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2025-03-03 14:41:49,139 INFO L435 NwaCegarLoop]: 26 mSDtfsCounter, 17 mSDsluCounter, 125 mSDsCounter, 0 mSdLazyCounter, 106 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 151 SdHoareTripleChecker+Invalid, 114 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 106 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-03 14:41:49,139 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 151 Invalid, 114 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 106 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-03 14:41:49,147 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2025-03-03 14:41:49,158 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 42. [2025-03-03 14:41:49,159 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 42 states, 26 states have (on average 1.1153846153846154) internal successors, (29), 28 states have internal predecessors, (29), 11 states have call successors, (11), 4 states have call predecessors, (11), 4 states have return successors, (11), 10 states have call predecessors, (11), 10 states have call successors, (11) [2025-03-03 14:41:49,161 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 42 states to 42 states and 51 transitions. [2025-03-03 14:41:49,162 INFO L78 Accepts]: Start accepts. Automaton has 42 states and 51 transitions. Word has length 9 [2025-03-03 14:41:49,162 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:41:49,162 INFO L471 AbstractCegarLoop]: Abstraction has 42 states and 51 transitions. [2025-03-03 14:41:49,163 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 6 states have (on average 1.1666666666666667) internal successors, (7), 6 states have internal predecessors, (7), 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) [2025-03-03 14:41:49,163 INFO L276 IsEmpty]: Start isEmpty. Operand 42 states and 51 transitions. [2025-03-03 14:41:49,163 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2025-03-03 14:41:49,163 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:41:49,163 INFO L218 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:41:49,163 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2025-03-03 14:41:49,164 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:41:49,164 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:41:49,164 INFO L85 PathProgramCache]: Analyzing trace with hash 1152737057, now seen corresponding path program 1 times [2025-03-03 14:41:49,164 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:41:49,164 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1564457120] [2025-03-03 14:41:49,164 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:41:49,164 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:41:49,177 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 15 statements into 1 equivalence classes. [2025-03-03 14:41:49,190 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 15 of 15 statements. [2025-03-03 14:41:49,191 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:41:49,191 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 14:41:49,192 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1212821669] [2025-03-03 14:41:49,193 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:41:49,193 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:41:49,193 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:41:49,195 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:41:49,196 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2025-03-03 14:41:49,242 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 15 statements into 1 equivalence classes. [2025-03-03 14:41:49,263 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 15 of 15 statements. [2025-03-03 14:41:49,263 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:41:49,263 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:41:49,265 INFO L256 TraceCheckSpWp]: Trace formula consists of 147 conjuncts, 37 conjuncts are in the unsatisfiable core [2025-03-03 14:41:49,269 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:41:49,295 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 [2025-03-03 14:41:49,300 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 [2025-03-03 14:41:49,477 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-03 14:41:49,477 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:41:49,603 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-03 14:41:49,603 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:41:49,603 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1564457120] [2025-03-03 14:41:49,606 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 14:41:49,606 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1212821669] [2025-03-03 14:41:49,606 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1212821669] provided 1 perfect and 1 imperfect interpolant sequences [2025-03-03 14:41:49,606 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-03 14:41:49,607 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [9] total 13 [2025-03-03 14:41:49,607 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [557677016] [2025-03-03 14:41:49,607 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 14:41:49,607 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2025-03-03 14:41:49,607 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:41:49,608 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-03-03 14:41:49,608 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=126, Unknown=0, NotChecked=0, Total=156 [2025-03-03 14:41:49,608 INFO L87 Difference]: Start difference. First operand 42 states and 51 transitions. Second operand has 8 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 6 states have internal predecessors, (11), 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) [2025-03-03 14:41:49,769 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:41:49,769 INFO L93 Difference]: Finished difference Result 51 states and 60 transitions. [2025-03-03 14:41:49,770 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2025-03-03 14:41:49,770 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 6 states have internal predecessors, (11), 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 15 [2025-03-03 14:41:49,770 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:41:49,771 INFO L225 Difference]: With dead ends: 51 [2025-03-03 14:41:49,771 INFO L226 Difference]: Without dead ends: 49 [2025-03-03 14:41:49,772 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 31 GetRequests, 14 SyntacticMatches, 3 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 19 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=44, Invalid=196, Unknown=0, NotChecked=0, Total=240 [2025-03-03 14:41:49,772 INFO L435 NwaCegarLoop]: 24 mSDtfsCounter, 16 mSDsluCounter, 110 mSDsCounter, 0 mSdLazyCounter, 112 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 134 SdHoareTripleChecker+Invalid, 119 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 112 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-03 14:41:49,773 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 134 Invalid, 119 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 112 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-03 14:41:49,773 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2025-03-03 14:41:49,781 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 46. [2025-03-03 14:41:49,782 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 46 states, 29 states have (on average 1.103448275862069) internal successors, (32), 31 states have internal predecessors, (32), 11 states have call successors, (11), 5 states have call predecessors, (11), 5 states have return successors, (11), 10 states have call predecessors, (11), 10 states have call successors, (11) [2025-03-03 14:41:49,782 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 54 transitions. [2025-03-03 14:41:49,782 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 54 transitions. Word has length 15 [2025-03-03 14:41:49,782 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:41:49,784 INFO L471 AbstractCegarLoop]: Abstraction has 46 states and 54 transitions. [2025-03-03 14:41:49,784 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 6 states have internal predecessors, (11), 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) [2025-03-03 14:41:49,785 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 54 transitions. [2025-03-03 14:41:49,785 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2025-03-03 14:41:49,785 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:41:49,785 INFO L218 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:41:49,792 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2025-03-03 14:41:49,990 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:41:49,990 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:41:49,990 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:41:49,990 INFO L85 PathProgramCache]: Analyzing trace with hash -355488994, now seen corresponding path program 1 times [2025-03-03 14:41:49,990 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:41:49,991 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1655269167] [2025-03-03 14:41:49,991 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:41:49,991 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:41:50,001 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 21 statements into 1 equivalence classes. [2025-03-03 14:41:50,014 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 21 of 21 statements. [2025-03-03 14:41:50,018 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:41:50,018 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 14:41:50,019 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2910624] [2025-03-03 14:41:50,019 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:41:50,019 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:41:50,019 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:41:50,021 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:41:50,024 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2025-03-03 14:41:50,063 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 21 statements into 1 equivalence classes. [2025-03-03 14:41:50,082 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 21 of 21 statements. [2025-03-03 14:41:50,082 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:41:50,082 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:41:50,084 INFO L256 TraceCheckSpWp]: Trace formula consists of 164 conjuncts, 46 conjuncts are in the unsatisfiable core [2025-03-03 14:41:50,085 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:41:50,093 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 [2025-03-03 14:41:50,097 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 [2025-03-03 14:41:50,367 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 1 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-03 14:41:50,368 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:41:50,640 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 45 treesize of output 29 [2025-03-03 14:41:50,705 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 3 proven. 4 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2025-03-03 14:41:50,706 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:41:50,706 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1655269167] [2025-03-03 14:41:50,706 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 14:41:50,707 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2910624] [2025-03-03 14:41:50,707 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2910624] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 14:41:50,707 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-03 14:41:50,707 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 12] total 22 [2025-03-03 14:41:50,707 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1303172141] [2025-03-03 14:41:50,707 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-03 14:41:50,708 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2025-03-03 14:41:50,708 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:41:50,708 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2025-03-03 14:41:50,709 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=64, Invalid=398, Unknown=0, NotChecked=0, Total=462 [2025-03-03 14:41:50,709 INFO L87 Difference]: Start difference. First operand 46 states and 54 transitions. Second operand has 22 states, 16 states have (on average 1.625) internal successors, (26), 18 states have internal predecessors, (26), 8 states have call successors, (8), 6 states have call predecessors, (8), 4 states have return successors, (4), 2 states have call predecessors, (4), 4 states have call successors, (4) [2025-03-03 14:41:55,775 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] [2025-03-03 14:41:55,792 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:41:55,792 INFO L93 Difference]: Finished difference Result 83 states and 97 transitions. [2025-03-03 14:41:55,792 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2025-03-03 14:41:55,793 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 16 states have (on average 1.625) internal successors, (26), 18 states have internal predecessors, (26), 8 states have call successors, (8), 6 states have call predecessors, (8), 4 states have return successors, (4), 2 states have call predecessors, (4), 4 states have call successors, (4) Word has length 21 [2025-03-03 14:41:55,793 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:41:55,795 INFO L225 Difference]: With dead ends: 83 [2025-03-03 14:41:55,795 INFO L226 Difference]: Without dead ends: 81 [2025-03-03 14:41:55,797 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 58 GetRequests, 18 SyntacticMatches, 3 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 253 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=235, Invalid=1247, Unknown=0, NotChecked=0, Total=1482 [2025-03-03 14:41:55,797 INFO L435 NwaCegarLoop]: 16 mSDtfsCounter, 71 mSDsluCounter, 99 mSDsCounter, 0 mSdLazyCounter, 341 mSolverCounterSat, 47 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 72 SdHoareTripleChecker+Valid, 115 SdHoareTripleChecker+Invalid, 389 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 47 IncrementalHoareTripleChecker+Valid, 341 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.5s IncrementalHoareTripleChecker+Time [2025-03-03 14:41:55,797 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [72 Valid, 115 Invalid, 389 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [47 Valid, 341 Invalid, 1 Unknown, 0 Unchecked, 4.5s Time] [2025-03-03 14:41:55,798 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 81 states. [2025-03-03 14:41:55,808 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 81 to 78. [2025-03-03 14:41:55,808 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 78 states, 49 states have (on average 1.1020408163265305) internal successors, (54), 52 states have internal predecessors, (54), 18 states have call successors, (18), 9 states have call predecessors, (18), 10 states have return successors, (19), 17 states have call predecessors, (19), 16 states have call successors, (19) [2025-03-03 14:41:55,809 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 78 states to 78 states and 91 transitions. [2025-03-03 14:41:55,809 INFO L78 Accepts]: Start accepts. Automaton has 78 states and 91 transitions. Word has length 21 [2025-03-03 14:41:55,809 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:41:55,810 INFO L471 AbstractCegarLoop]: Abstraction has 78 states and 91 transitions. [2025-03-03 14:41:55,810 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 16 states have (on average 1.625) internal successors, (26), 18 states have internal predecessors, (26), 8 states have call successors, (8), 6 states have call predecessors, (8), 4 states have return successors, (4), 2 states have call predecessors, (4), 4 states have call successors, (4) [2025-03-03 14:41:55,811 INFO L276 IsEmpty]: Start isEmpty. Operand 78 states and 91 transitions. [2025-03-03 14:41:55,811 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2025-03-03 14:41:55,811 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:41:55,811 INFO L218 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:41:55,817 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2025-03-03 14:41:56,011 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2025-03-03 14:41:56,011 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:41:56,012 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:41:56,012 INFO L85 PathProgramCache]: Analyzing trace with hash -1616890220, now seen corresponding path program 1 times [2025-03-03 14:41:56,012 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:41:56,012 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [395274518] [2025-03-03 14:41:56,012 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:41:56,012 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:41:56,019 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-03-03 14:41:56,029 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-03-03 14:41:56,029 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:41:56,029 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:41:56,548 INFO L134 CoverageAnalysis]: Checked inductivity of 21 backedges. 6 proven. 3 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2025-03-03 14:41:56,548 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:41:56,548 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [395274518] [2025-03-03 14:41:56,548 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [395274518] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:41:56,548 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1996352238] [2025-03-03 14:41:56,548 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:41:56,548 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:41:56,548 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:41:56,551 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:41:56,552 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2025-03-03 14:41:56,588 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-03-03 14:41:56,610 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-03-03 14:41:56,610 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:41:56,610 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:41:56,611 INFO L256 TraceCheckSpWp]: Trace formula consists of 232 conjuncts, 40 conjuncts are in the unsatisfiable core [2025-03-03 14:41:56,613 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:41:56,770 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 33 treesize of output 21 [2025-03-03 14:41:56,772 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 33 treesize of output 21 [2025-03-03 14:41:56,795 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 [2025-03-03 14:41:56,797 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2025-03-03 14:41:56,834 INFO L134 CoverageAnalysis]: Checked inductivity of 21 backedges. 5 proven. 12 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-03 14:41:56,834 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:42:01,208 INFO L134 CoverageAnalysis]: Checked inductivity of 21 backedges. 7 proven. 8 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2025-03-03 14:42:01,208 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1996352238] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 14:42:01,208 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-03 14:42:01,208 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 11, 10] total 21 [2025-03-03 14:42:01,208 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [324590323] [2025-03-03 14:42:01,208 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-03 14:42:01,209 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2025-03-03 14:42:01,209 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:42:01,209 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2025-03-03 14:42:01,209 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=63, Invalid=356, Unknown=1, NotChecked=0, Total=420 [2025-03-03 14:42:01,209 INFO L87 Difference]: Start difference. First operand 78 states and 91 transitions. Second operand has 21 states, 16 states have (on average 2.3125) internal successors, (37), 17 states have internal predecessors, (37), 9 states have call successors, (15), 7 states have call predecessors, (15), 4 states have return successors, (9), 2 states have call predecessors, (9), 4 states have call successors, (9) [2025-03-03 14:42:02,969 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:42:02,970 INFO L93 Difference]: Finished difference Result 88 states and 101 transitions. [2025-03-03 14:42:02,970 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2025-03-03 14:42:02,971 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 16 states have (on average 2.3125) internal successors, (37), 17 states have internal predecessors, (37), 9 states have call successors, (15), 7 states have call predecessors, (15), 4 states have return successors, (9), 2 states have call predecessors, (9), 4 states have call successors, (9) Word has length 31 [2025-03-03 14:42:02,971 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:42:02,971 INFO L225 Difference]: With dead ends: 88 [2025-03-03 14:42:02,972 INFO L226 Difference]: Without dead ends: 86 [2025-03-03 14:42:02,972 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 84 GetRequests, 50 SyntacticMatches, 5 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 116 ImplicationChecksByTransitivity, 5.0s TimeCoverageRelationStatistics Valid=155, Invalid=774, Unknown=1, NotChecked=0, Total=930 [2025-03-03 14:42:02,972 INFO L435 NwaCegarLoop]: 22 mSDtfsCounter, 70 mSDsluCounter, 132 mSDsCounter, 0 mSdLazyCounter, 436 mSolverCounterSat, 36 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 73 SdHoareTripleChecker+Valid, 154 SdHoareTripleChecker+Invalid, 472 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 36 IncrementalHoareTripleChecker+Valid, 436 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.2s IncrementalHoareTripleChecker+Time [2025-03-03 14:42:02,973 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [73 Valid, 154 Invalid, 472 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [36 Valid, 436 Invalid, 0 Unknown, 0 Unchecked, 1.2s Time] [2025-03-03 14:42:02,973 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 86 states. [2025-03-03 14:42:02,987 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 86 to 86. [2025-03-03 14:42:02,987 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 86 states, 54 states have (on average 1.0925925925925926) internal successors, (59), 57 states have internal predecessors, (59), 18 states have call successors, (18), 10 states have call predecessors, (18), 13 states have return successors, (22), 18 states have call predecessors, (22), 16 states have call successors, (22) [2025-03-03 14:42:02,988 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 86 states to 86 states and 99 transitions. [2025-03-03 14:42:02,990 INFO L78 Accepts]: Start accepts. Automaton has 86 states and 99 transitions. Word has length 31 [2025-03-03 14:42:02,990 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:42:02,990 INFO L471 AbstractCegarLoop]: Abstraction has 86 states and 99 transitions. [2025-03-03 14:42:02,990 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 16 states have (on average 2.3125) internal successors, (37), 17 states have internal predecessors, (37), 9 states have call successors, (15), 7 states have call predecessors, (15), 4 states have return successors, (9), 2 states have call predecessors, (9), 4 states have call successors, (9) [2025-03-03 14:42:02,990 INFO L276 IsEmpty]: Start isEmpty. Operand 86 states and 99 transitions. [2025-03-03 14:42:02,991 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2025-03-03 14:42:02,991 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:42:02,991 INFO L218 NwaCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:42:02,997 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2025-03-03 14:42:03,191 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:42:03,191 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:42:03,192 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:42:03,192 INFO L85 PathProgramCache]: Analyzing trace with hash -1193788605, now seen corresponding path program 1 times [2025-03-03 14:42:03,192 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:42:03,192 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1615370073] [2025-03-03 14:42:03,192 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:42:03,192 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:42:03,199 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-03-03 14:42:03,210 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-03-03 14:42:03,214 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:42:03,215 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:42:03,531 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2025-03-03 14:42:03,531 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:42:03,531 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1615370073] [2025-03-03 14:42:03,531 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1615370073] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 14:42:03,531 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 14:42:03,531 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2025-03-03 14:42:03,531 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [298313762] [2025-03-03 14:42:03,532 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 14:42:03,532 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2025-03-03 14:42:03,532 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:42:03,532 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2025-03-03 14:42:03,532 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2025-03-03 14:42:03,533 INFO L87 Difference]: Start difference. First operand 86 states and 99 transitions. Second operand has 7 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 6 states have internal predecessors, (16), 3 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2025-03-03 14:42:03,961 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:42:03,961 INFO L93 Difference]: Finished difference Result 92 states and 104 transitions. [2025-03-03 14:42:03,962 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2025-03-03 14:42:03,962 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 6 states have internal predecessors, (16), 3 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 31 [2025-03-03 14:42:03,962 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:42:03,963 INFO L225 Difference]: With dead ends: 92 [2025-03-03 14:42:03,963 INFO L226 Difference]: Without dead ends: 90 [2025-03-03 14:42:03,963 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 4 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=25, Invalid=65, Unknown=0, NotChecked=0, Total=90 [2025-03-03 14:42:03,964 INFO L435 NwaCegarLoop]: 17 mSDtfsCounter, 9 mSDsluCounter, 51 mSDsCounter, 0 mSdLazyCounter, 118 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 68 SdHoareTripleChecker+Invalid, 128 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 118 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-03-03 14:42:03,964 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 68 Invalid, 128 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 118 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-03-03 14:42:03,964 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 90 states. [2025-03-03 14:42:03,977 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 90 to 90. [2025-03-03 14:42:03,978 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 90 states, 57 states have (on average 1.087719298245614) internal successors, (62), 60 states have internal predecessors, (62), 18 states have call successors, (18), 11 states have call predecessors, (18), 14 states have return successors, (22), 18 states have call predecessors, (22), 16 states have call successors, (22) [2025-03-03 14:42:03,978 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 90 states to 90 states and 102 transitions. [2025-03-03 14:42:03,979 INFO L78 Accepts]: Start accepts. Automaton has 90 states and 102 transitions. Word has length 31 [2025-03-03 14:42:03,979 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:42:03,979 INFO L471 AbstractCegarLoop]: Abstraction has 90 states and 102 transitions. [2025-03-03 14:42:03,979 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 6 states have internal predecessors, (16), 3 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2025-03-03 14:42:03,979 INFO L276 IsEmpty]: Start isEmpty. Operand 90 states and 102 transitions. [2025-03-03 14:42:03,980 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2025-03-03 14:42:03,980 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:42:03,980 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 4, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:42:03,980 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4 [2025-03-03 14:42:03,980 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:42:03,980 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:42:03,981 INFO L85 PathProgramCache]: Analyzing trace with hash 284207439, now seen corresponding path program 2 times [2025-03-03 14:42:03,981 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:42:03,981 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [647522757] [2025-03-03 14:42:03,981 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-03 14:42:03,981 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:42:03,988 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 37 statements into 2 equivalence classes. [2025-03-03 14:42:04,001 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 37 of 37 statements. [2025-03-03 14:42:04,004 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-03 14:42:04,004 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 14:42:04,005 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [294378568] [2025-03-03 14:42:04,005 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-03 14:42:04,005 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:42:04,006 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:42:04,007 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:42:04,009 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2025-03-03 14:42:04,056 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 37 statements into 2 equivalence classes. [2025-03-03 14:42:04,083 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 37 of 37 statements. [2025-03-03 14:42:04,084 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-03 14:42:04,084 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:42:04,086 INFO L256 TraceCheckSpWp]: Trace formula consists of 247 conjuncts, 74 conjuncts are in the unsatisfiable core [2025-03-03 14:42:04,089 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:42:04,101 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 [2025-03-03 14:42:04,116 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 [2025-03-03 14:42:05,255 INFO L349 Elim1Store]: treesize reduction 29, result has 34.1 percent of original size [2025-03-03 14:42:05,255 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 26 treesize of output 29 [2025-03-03 14:42:05,321 INFO L349 Elim1Store]: treesize reduction 29, result has 34.1 percent of original size [2025-03-03 14:42:05,321 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 26 treesize of output 29 [2025-03-03 14:42:05,835 INFO L134 CoverageAnalysis]: Checked inductivity of 37 backedges. 2 proven. 31 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-03 14:42:05,835 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:42:06,676 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 49 treesize of output 41 [2025-03-03 14:42:06,773 INFO L134 CoverageAnalysis]: Checked inductivity of 37 backedges. 7 proven. 13 refuted. 0 times theorem prover too weak. 17 trivial. 0 not checked. [2025-03-03 14:42:06,773 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:42:06,773 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [647522757] [2025-03-03 14:42:06,773 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 14:42:06,773 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [294378568] [2025-03-03 14:42:06,773 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [294378568] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 14:42:06,773 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-03 14:42:06,773 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 12] total 25 [2025-03-03 14:42:06,773 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [721877439] [2025-03-03 14:42:06,773 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-03 14:42:06,774 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2025-03-03 14:42:06,774 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:42:06,774 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2025-03-03 14:42:06,774 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=78, Invalid=522, Unknown=0, NotChecked=0, Total=600 [2025-03-03 14:42:06,774 INFO L87 Difference]: Start difference. First operand 90 states and 102 transitions. Second operand has 25 states, 19 states have (on average 2.0) internal successors, (38), 20 states have internal predecessors, (38), 10 states have call successors, (14), 8 states have call predecessors, (14), 5 states have return successors, (8), 4 states have call predecessors, (8), 6 states have call successors, (8) [2025-03-03 14:42:11,345 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:42:11,346 INFO L93 Difference]: Finished difference Result 118 states and 128 transitions. [2025-03-03 14:42:11,346 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 37 states. [2025-03-03 14:42:11,346 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 19 states have (on average 2.0) internal successors, (38), 20 states have internal predecessors, (38), 10 states have call successors, (14), 8 states have call predecessors, (14), 5 states have return successors, (8), 4 states have call predecessors, (8), 6 states have call successors, (8) Word has length 37 [2025-03-03 14:42:11,346 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:42:11,347 INFO L225 Difference]: With dead ends: 118 [2025-03-03 14:42:11,347 INFO L226 Difference]: Without dead ends: 116 [2025-03-03 14:42:11,348 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 98 GetRequests, 43 SyntacticMatches, 6 SemanticMatches, 49 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 570 ImplicationChecksByTransitivity, 3.5s TimeCoverageRelationStatistics Valid=341, Invalid=2209, Unknown=0, NotChecked=0, Total=2550 [2025-03-03 14:42:11,348 INFO L435 NwaCegarLoop]: 29 mSDtfsCounter, 78 mSDsluCounter, 240 mSDsCounter, 0 mSdLazyCounter, 788 mSolverCounterSat, 39 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 81 SdHoareTripleChecker+Valid, 269 SdHoareTripleChecker+Invalid, 827 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 39 IncrementalHoareTripleChecker+Valid, 788 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.5s IncrementalHoareTripleChecker+Time [2025-03-03 14:42:11,348 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [81 Valid, 269 Invalid, 827 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [39 Valid, 788 Invalid, 0 Unknown, 0 Unchecked, 2.5s Time] [2025-03-03 14:42:11,348 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 116 states. [2025-03-03 14:42:11,363 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 116 to 112. [2025-03-03 14:42:11,363 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 112 states, 72 states have (on average 1.0833333333333333) internal successors, (78), 75 states have internal predecessors, (78), 21 states have call successors, (21), 15 states have call predecessors, (21), 18 states have return successors, (24), 21 states have call predecessors, (24), 18 states have call successors, (24) [2025-03-03 14:42:11,364 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 112 states to 112 states and 123 transitions. [2025-03-03 14:42:11,365 INFO L78 Accepts]: Start accepts. Automaton has 112 states and 123 transitions. Word has length 37 [2025-03-03 14:42:11,365 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:42:11,365 INFO L471 AbstractCegarLoop]: Abstraction has 112 states and 123 transitions. [2025-03-03 14:42:11,365 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 25 states, 19 states have (on average 2.0) internal successors, (38), 20 states have internal predecessors, (38), 10 states have call successors, (14), 8 states have call predecessors, (14), 5 states have return successors, (8), 4 states have call predecessors, (8), 6 states have call successors, (8) [2025-03-03 14:42:11,365 INFO L276 IsEmpty]: Start isEmpty. Operand 112 states and 123 transitions. [2025-03-03 14:42:11,365 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2025-03-03 14:42:11,365 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:42:11,365 INFO L218 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, 1, 1, 1, 1, 1] [2025-03-03 14:42:11,371 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2025-03-03 14:42:11,566 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:42:11,566 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:42:11,566 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:42:11,566 INFO L85 PathProgramCache]: Analyzing trace with hash 762261055, now seen corresponding path program 1 times [2025-03-03 14:42:11,566 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:42:11,566 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1897157616] [2025-03-03 14:42:11,566 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:42:11,566 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:42:11,574 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 37 statements into 1 equivalence classes. [2025-03-03 14:42:11,583 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 37 of 37 statements. [2025-03-03 14:42:11,583 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:42:11,584 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 14:42:11,584 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [786923970] [2025-03-03 14:42:11,584 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:42:11,584 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:42:11,585 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:42:11,586 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:42:11,588 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2025-03-03 14:42:11,626 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 37 statements into 1 equivalence classes. [2025-03-03 14:42:11,645 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 37 of 37 statements. [2025-03-03 14:42:11,645 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:42:11,645 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:42:11,646 INFO L256 TraceCheckSpWp]: Trace formula consists of 199 conjuncts, 19 conjuncts are in the unsatisfiable core [2025-03-03 14:42:11,647 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:42:11,655 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 [2025-03-03 14:42:11,669 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 [2025-03-03 14:42:12,011 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 18 proven. 2 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2025-03-03 14:42:12,011 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:42:12,364 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:42:12,364 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1897157616] [2025-03-03 14:42:12,364 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 14:42:12,364 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [786923970] [2025-03-03 14:42:12,364 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [786923970] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:42:12,364 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-03 14:42:12,364 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8] total 8 [2025-03-03 14:42:12,364 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1451516079] [2025-03-03 14:42:12,364 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-03 14:42:12,364 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2025-03-03 14:42:12,364 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:42:12,365 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-03-03 14:42:12,365 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=87, Unknown=0, NotChecked=0, Total=110 [2025-03-03 14:42:12,365 INFO L87 Difference]: Start difference. First operand 112 states and 123 transitions. Second operand has 8 states, 7 states have (on average 2.857142857142857) internal successors, (20), 7 states have internal predecessors, (20), 3 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2025-03-03 14:42:12,958 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:42:12,958 INFO L93 Difference]: Finished difference Result 120 states and 129 transitions. [2025-03-03 14:42:12,958 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-03-03 14:42:12,958 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 2.857142857142857) internal successors, (20), 7 states have internal predecessors, (20), 3 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 37 [2025-03-03 14:42:12,959 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:42:12,959 INFO L225 Difference]: With dead ends: 120 [2025-03-03 14:42:12,959 INFO L226 Difference]: Without dead ends: 116 [2025-03-03 14:42:12,960 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 59 GetRequests, 43 SyntacticMatches, 3 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=49, Invalid=161, Unknown=0, NotChecked=0, Total=210 [2025-03-03 14:42:12,960 INFO L435 NwaCegarLoop]: 14 mSDtfsCounter, 25 mSDsluCounter, 49 mSDsCounter, 0 mSdLazyCounter, 147 mSolverCounterSat, 23 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 63 SdHoareTripleChecker+Invalid, 170 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 23 IncrementalHoareTripleChecker+Valid, 147 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2025-03-03 14:42:12,960 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [25 Valid, 63 Invalid, 170 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [23 Valid, 147 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2025-03-03 14:42:12,961 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 116 states. [2025-03-03 14:42:12,982 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 116 to 114. [2025-03-03 14:42:12,982 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 114 states, 74 states have (on average 1.0675675675675675) internal successors, (79), 76 states have internal predecessors, (79), 21 states have call successors, (21), 16 states have call predecessors, (21), 18 states have return successors, (24), 21 states have call predecessors, (24), 18 states have call successors, (24) [2025-03-03 14:42:12,983 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 114 states to 114 states and 124 transitions. [2025-03-03 14:42:12,983 INFO L78 Accepts]: Start accepts. Automaton has 114 states and 124 transitions. Word has length 37 [2025-03-03 14:42:12,983 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:42:12,983 INFO L471 AbstractCegarLoop]: Abstraction has 114 states and 124 transitions. [2025-03-03 14:42:12,983 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 2.857142857142857) internal successors, (20), 7 states have internal predecessors, (20), 3 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2025-03-03 14:42:12,984 INFO L276 IsEmpty]: Start isEmpty. Operand 114 states and 124 transitions. [2025-03-03 14:42:12,985 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2025-03-03 14:42:12,986 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:42:12,986 INFO L218 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, 1] [2025-03-03 14:42:12,992 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2025-03-03 14:42:13,186 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:42:13,187 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:42:13,187 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:42:13,187 INFO L85 PathProgramCache]: Analyzing trace with hash 212085565, now seen corresponding path program 1 times [2025-03-03 14:42:13,187 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:42:13,187 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [861507714] [2025-03-03 14:42:13,187 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:42:13,187 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:42:13,192 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 43 statements into 1 equivalence classes. [2025-03-03 14:42:13,199 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 43 of 43 statements. [2025-03-03 14:42:13,199 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:42:13,199 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 14:42:13,200 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [690906522] [2025-03-03 14:42:13,200 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:42:13,200 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:42:13,200 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:42:13,201 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:42:13,203 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2025-03-03 14:42:13,243 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 43 statements into 1 equivalence classes. [2025-03-03 14:42:13,263 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 43 of 43 statements. [2025-03-03 14:42:13,263 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:42:13,263 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:42:13,264 INFO L256 TraceCheckSpWp]: Trace formula consists of 216 conjuncts, 21 conjuncts are in the unsatisfiable core [2025-03-03 14:42:13,266 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:42:13,274 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 [2025-03-03 14:42:13,291 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 [2025-03-03 14:42:13,773 INFO L134 CoverageAnalysis]: Checked inductivity of 50 backedges. 30 proven. 4 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2025-03-03 14:42:13,774 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:42:14,309 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:42:14,311 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [861507714] [2025-03-03 14:42:14,311 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 14:42:14,311 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [690906522] [2025-03-03 14:42:14,311 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [690906522] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:42:14,311 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-03 14:42:14,311 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8] total 8 [2025-03-03 14:42:14,311 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1512761578] [2025-03-03 14:42:14,311 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-03 14:42:14,311 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2025-03-03 14:42:14,311 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:42:14,311 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-03-03 14:42:14,311 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=87, Unknown=0, NotChecked=0, Total=110 [2025-03-03 14:42:14,312 INFO L87 Difference]: Start difference. First operand 114 states and 124 transitions. Second operand has 8 states, 7 states have (on average 3.0) internal successors, (21), 7 states have internal predecessors, (21), 3 states have call successors, (7), 4 states have call predecessors, (7), 3 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2025-03-03 14:42:14,932 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:42:14,932 INFO L93 Difference]: Finished difference Result 116 states and 125 transitions. [2025-03-03 14:42:14,933 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2025-03-03 14:42:14,933 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 3.0) internal successors, (21), 7 states have internal predecessors, (21), 3 states have call successors, (7), 4 states have call predecessors, (7), 3 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 43 [2025-03-03 14:42:14,933 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:42:14,934 INFO L225 Difference]: With dead ends: 116 [2025-03-03 14:42:14,934 INFO L226 Difference]: Without dead ends: 96 [2025-03-03 14:42:14,935 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 70 GetRequests, 52 SyntacticMatches, 5 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=49, Invalid=161, Unknown=0, NotChecked=0, Total=210 [2025-03-03 14:42:14,936 INFO L435 NwaCegarLoop]: 14 mSDtfsCounter, 17 mSDsluCounter, 51 mSDsCounter, 0 mSdLazyCounter, 141 mSolverCounterSat, 21 mSolverCounterUnsat, 3 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 65 SdHoareTripleChecker+Invalid, 165 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 21 IncrementalHoareTripleChecker+Valid, 141 IncrementalHoareTripleChecker+Invalid, 3 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2025-03-03 14:42:14,936 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 65 Invalid, 165 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [21 Valid, 141 Invalid, 3 Unknown, 0 Unchecked, 0.4s Time] [2025-03-03 14:42:14,936 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 96 states. [2025-03-03 14:42:14,946 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 96 to 96. [2025-03-03 14:42:14,946 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 96 states, 62 states have (on average 1.064516129032258) internal successors, (66), 64 states have internal predecessors, (66), 18 states have call successors, (18), 13 states have call predecessors, (18), 15 states have return successors, (21), 18 states have call predecessors, (21), 16 states have call successors, (21) [2025-03-03 14:42:14,947 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 105 transitions. [2025-03-03 14:42:14,947 INFO L78 Accepts]: Start accepts. Automaton has 96 states and 105 transitions. Word has length 43 [2025-03-03 14:42:14,947 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:42:14,947 INFO L471 AbstractCegarLoop]: Abstraction has 96 states and 105 transitions. [2025-03-03 14:42:14,948 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 3.0) internal successors, (21), 7 states have internal predecessors, (21), 3 states have call successors, (7), 4 states have call predecessors, (7), 3 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2025-03-03 14:42:14,948 INFO L276 IsEmpty]: Start isEmpty. Operand 96 states and 105 transitions. [2025-03-03 14:42:14,948 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2025-03-03 14:42:14,950 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:42:14,950 INFO L218 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:42:14,956 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2025-03-03 14:42:15,155 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:42:15,155 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:42:15,155 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:42:15,155 INFO L85 PathProgramCache]: Analyzing trace with hash -1318512677, now seen corresponding path program 1 times [2025-03-03 14:42:15,155 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:42:15,155 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [749141077] [2025-03-03 14:42:15,155 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:42:15,155 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:42:15,162 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 55 statements into 1 equivalence classes. [2025-03-03 14:42:15,172 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 55 of 55 statements. [2025-03-03 14:42:15,173 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:42:15,173 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:42:16,099 INFO L134 CoverageAnalysis]: Checked inductivity of 83 backedges. 12 proven. 10 refuted. 0 times theorem prover too weak. 61 trivial. 0 not checked. [2025-03-03 14:42:16,099 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:42:16,099 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [749141077] [2025-03-03 14:42:16,099 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [749141077] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:42:16,099 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [423962486] [2025-03-03 14:42:16,099 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:42:16,099 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:42:16,100 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:42:16,101 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:42:16,103 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2025-03-03 14:42:16,147 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 55 statements into 1 equivalence classes. [2025-03-03 14:42:16,169 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 55 of 55 statements. [2025-03-03 14:42:16,169 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:42:16,169 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:42:16,171 INFO L256 TraceCheckSpWp]: Trace formula consists of 286 conjuncts, 55 conjuncts are in the unsatisfiable core [2025-03-03 14:42:16,179 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:42:16,187 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 [2025-03-03 14:42:16,198 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 [2025-03-03 14:42:16,756 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 [2025-03-03 14:42:16,767 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 [2025-03-03 14:42:16,884 INFO L134 CoverageAnalysis]: Checked inductivity of 83 backedges. 12 proven. 10 refuted. 0 times theorem prover too weak. 61 trivial. 0 not checked. [2025-03-03 14:42:16,884 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:42:17,685 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 16 treesize of output 12 [2025-03-03 14:42:17,694 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 12 treesize of output 8 [2025-03-03 14:42:17,832 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [423962486] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:42:17,832 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-03 14:42:17,832 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 16 [2025-03-03 14:42:17,832 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [63677865] [2025-03-03 14:42:17,832 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-03 14:42:17,833 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2025-03-03 14:42:17,833 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:42:17,833 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2025-03-03 14:42:17,833 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=55, Invalid=325, Unknown=0, NotChecked=0, Total=380 [2025-03-03 14:42:17,833 INFO L87 Difference]: Start difference. First operand 96 states and 105 transitions. Second operand has 16 states, 12 states have (on average 2.6666666666666665) internal successors, (32), 13 states have internal predecessors, (32), 7 states have call successors, (14), 4 states have call predecessors, (14), 4 states have return successors, (13), 6 states have call predecessors, (13), 6 states have call successors, (13) [2025-03-03 14:42:18,607 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:42:18,607 INFO L93 Difference]: Finished difference Result 102 states and 110 transitions. [2025-03-03 14:42:18,608 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-03-03 14:42:18,608 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 12 states have (on average 2.6666666666666665) internal successors, (32), 13 states have internal predecessors, (32), 7 states have call successors, (14), 4 states have call predecessors, (14), 4 states have return successors, (13), 6 states have call predecessors, (13), 6 states have call successors, (13) Word has length 55 [2025-03-03 14:42:18,608 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:42:18,609 INFO L225 Difference]: With dead ends: 102 [2025-03-03 14:42:18,609 INFO L226 Difference]: Without dead ends: 100 [2025-03-03 14:42:18,609 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 85 GetRequests, 61 SyntacticMatches, 2 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 88 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=85, Invalid=467, Unknown=0, NotChecked=0, Total=552 [2025-03-03 14:42:18,609 INFO L435 NwaCegarLoop]: 17 mSDtfsCounter, 16 mSDsluCounter, 77 mSDsCounter, 0 mSdLazyCounter, 257 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 94 SdHoareTripleChecker+Invalid, 268 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 257 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2025-03-03 14:42:18,609 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 94 Invalid, 268 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 257 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2025-03-03 14:42:18,610 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 100 states. [2025-03-03 14:42:18,620 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 100 to 100. [2025-03-03 14:42:18,620 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 100 states, 65 states have (on average 1.0615384615384615) internal successors, (69), 67 states have internal predecessors, (69), 18 states have call successors, (18), 14 states have call predecessors, (18), 16 states have return successors, (21), 18 states have call predecessors, (21), 16 states have call successors, (21) [2025-03-03 14:42:18,620 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 100 states to 100 states and 108 transitions. [2025-03-03 14:42:18,621 INFO L78 Accepts]: Start accepts. Automaton has 100 states and 108 transitions. Word has length 55 [2025-03-03 14:42:18,621 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:42:18,621 INFO L471 AbstractCegarLoop]: Abstraction has 100 states and 108 transitions. [2025-03-03 14:42:18,621 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 12 states have (on average 2.6666666666666665) internal successors, (32), 13 states have internal predecessors, (32), 7 states have call successors, (14), 4 states have call predecessors, (14), 4 states have return successors, (13), 6 states have call predecessors, (13), 6 states have call successors, (13) [2025-03-03 14:42:18,621 INFO L276 IsEmpty]: Start isEmpty. Operand 100 states and 108 transitions. [2025-03-03 14:42:18,621 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 62 [2025-03-03 14:42:18,621 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:42:18,621 INFO L218 NwaCegarLoop]: trace histogram [8, 7, 7, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:42:18,627 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2025-03-03 14:42:18,822 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:42:18,822 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:42:18,822 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:42:18,822 INFO L85 PathProgramCache]: Analyzing trace with hash -1113704233, now seen corresponding path program 1 times [2025-03-03 14:42:18,822 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:42:18,822 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [841518184] [2025-03-03 14:42:18,822 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:42:18,822 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:42:18,829 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 61 statements into 1 equivalence classes. [2025-03-03 14:42:18,843 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 61 of 61 statements. [2025-03-03 14:42:18,845 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:42:18,846 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 14:42:18,847 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [443715907] [2025-03-03 14:42:18,848 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:42:18,848 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:42:18,848 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:42:18,850 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:42:18,851 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2025-03-03 14:42:18,899 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 61 statements into 1 equivalence classes. [2025-03-03 14:42:18,929 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 61 of 61 statements. [2025-03-03 14:42:18,930 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:42:18,930 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:42:18,931 INFO L256 TraceCheckSpWp]: Trace formula consists of 301 conjuncts, 58 conjuncts are in the unsatisfiable core [2025-03-03 14:42:18,934 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:42:19,186 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2025-03-03 14:42:19,193 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2025-03-03 14:42:20,001 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 34 treesize of output 26 [2025-03-03 14:42:20,009 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 37 treesize of output 17 [2025-03-03 14:42:20,142 INFO L134 CoverageAnalysis]: Checked inductivity of 109 backedges. 59 proven. 18 refuted. 0 times theorem prover too weak. 32 trivial. 0 not checked. [2025-03-03 14:42:20,143 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:42:21,613 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:42:21,613 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [841518184] [2025-03-03 14:42:21,613 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 14:42:21,613 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [443715907] [2025-03-03 14:42:21,613 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [443715907] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:42:21,613 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-03 14:42:21,613 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2025-03-03 14:42:21,614 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1678054917] [2025-03-03 14:42:21,614 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-03 14:42:21,614 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2025-03-03 14:42:21,614 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:42:21,614 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2025-03-03 14:42:21,614 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=51, Invalid=255, Unknown=0, NotChecked=0, Total=306 [2025-03-03 14:42:21,614 INFO L87 Difference]: Start difference. First operand 100 states and 108 transitions. Second operand has 15 states, 13 states have (on average 2.3076923076923075) internal successors, (30), 13 states have internal predecessors, (30), 7 states have call successors, (10), 4 states have call predecessors, (10), 5 states have return successors, (9), 5 states have call predecessors, (9), 6 states have call successors, (9) [2025-03-03 14:42:23,006 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:42:23,006 INFO L93 Difference]: Finished difference Result 110 states and 117 transitions. [2025-03-03 14:42:23,006 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2025-03-03 14:42:23,007 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 13 states have (on average 2.3076923076923075) internal successors, (30), 13 states have internal predecessors, (30), 7 states have call successors, (10), 4 states have call predecessors, (10), 5 states have return successors, (9), 5 states have call predecessors, (9), 6 states have call successors, (9) Word has length 61 [2025-03-03 14:42:23,007 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:42:23,007 INFO L225 Difference]: With dead ends: 110 [2025-03-03 14:42:23,007 INFO L226 Difference]: Without dead ends: 106 [2025-03-03 14:42:23,008 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 94 GetRequests, 61 SyntacticMatches, 5 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 186 ImplicationChecksByTransitivity, 1.7s TimeCoverageRelationStatistics Valid=146, Invalid=724, Unknown=0, NotChecked=0, Total=870 [2025-03-03 14:42:23,008 INFO L435 NwaCegarLoop]: 12 mSDtfsCounter, 29 mSDsluCounter, 54 mSDsCounter, 0 mSdLazyCounter, 281 mSolverCounterSat, 26 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 31 SdHoareTripleChecker+Valid, 66 SdHoareTripleChecker+Invalid, 308 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 26 IncrementalHoareTripleChecker+Valid, 281 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2025-03-03 14:42:23,008 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [31 Valid, 66 Invalid, 308 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [26 Valid, 281 Invalid, 1 Unknown, 0 Unchecked, 0.7s Time] [2025-03-03 14:42:23,008 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 106 states. [2025-03-03 14:42:23,021 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 106 to 106. [2025-03-03 14:42:23,021 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 106 states, 70 states have (on average 1.042857142857143) internal successors, (73), 71 states have internal predecessors, (73), 18 states have call successors, (18), 16 states have call predecessors, (18), 17 states have return successors, (21), 18 states have call predecessors, (21), 16 states have call successors, (21) [2025-03-03 14:42:23,021 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 112 transitions. [2025-03-03 14:42:23,022 INFO L78 Accepts]: Start accepts. Automaton has 106 states and 112 transitions. Word has length 61 [2025-03-03 14:42:23,022 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:42:23,022 INFO L471 AbstractCegarLoop]: Abstraction has 106 states and 112 transitions. [2025-03-03 14:42:23,022 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 13 states have (on average 2.3076923076923075) internal successors, (30), 13 states have internal predecessors, (30), 7 states have call successors, (10), 4 states have call predecessors, (10), 5 states have return successors, (9), 5 states have call predecessors, (9), 6 states have call successors, (9) [2025-03-03 14:42:23,022 INFO L276 IsEmpty]: Start isEmpty. Operand 106 states and 112 transitions. [2025-03-03 14:42:23,022 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 66 [2025-03-03 14:42:23,022 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:42:23,022 INFO L218 NwaCegarLoop]: trace histogram [9, 8, 8, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1] [2025-03-03 14:42:23,028 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2025-03-03 14:42:23,223 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2025-03-03 14:42:23,223 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:42:23,223 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:42:23,223 INFO L85 PathProgramCache]: Analyzing trace with hash 1735226362, now seen corresponding path program 3 times [2025-03-03 14:42:23,223 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:42:23,223 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [724905332] [2025-03-03 14:42:23,223 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-03 14:42:23,223 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:42:23,231 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 65 statements into 5 equivalence classes. [2025-03-03 14:42:23,252 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) and asserted 65 of 65 statements. [2025-03-03 14:42:23,252 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2025-03-03 14:42:23,252 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 14:42:23,253 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1520963975] [2025-03-03 14:42:23,253 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-03 14:42:23,253 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:42:23,253 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:42:23,255 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:42:23,257 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2025-03-03 14:42:23,309 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 65 statements into 5 equivalence classes. [2025-03-03 14:42:23,371 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) and asserted 47 of 65 statements. [2025-03-03 14:42:23,371 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2025-03-03 14:42:23,371 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:42:23,373 INFO L256 TraceCheckSpWp]: Trace formula consists of 317 conjuncts, 98 conjuncts are in the unsatisfiable core [2025-03-03 14:42:23,376 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:42:23,384 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 [2025-03-03 14:42:23,398 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 [2025-03-03 14:42:24,009 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 25 treesize of output 17 [2025-03-03 14:42:24,028 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 [2025-03-03 14:42:24,608 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 25 treesize of output 17 [2025-03-03 14:42:24,629 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 [2025-03-03 14:42:25,332 INFO L134 CoverageAnalysis]: Checked inductivity of 152 backedges. 0 proven. 124 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2025-03-03 14:42:25,332 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:42:26,119 INFO L134 CoverageAnalysis]: Checked inductivity of 152 backedges. 16 proven. 2 refuted. 0 times theorem prover too weak. 134 trivial. 0 not checked. [2025-03-03 14:42:26,119 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:42:26,119 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [724905332] [2025-03-03 14:42:26,119 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 14:42:26,119 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1520963975] [2025-03-03 14:42:26,120 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1520963975] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 14:42:26,120 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-03 14:42:26,120 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 8] total 21 [2025-03-03 14:42:26,120 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [740299947] [2025-03-03 14:42:26,120 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-03 14:42:26,121 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2025-03-03 14:42:26,121 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:42:26,121 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2025-03-03 14:42:26,121 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=56, Invalid=364, Unknown=0, NotChecked=0, Total=420 [2025-03-03 14:42:26,121 INFO L87 Difference]: Start difference. First operand 106 states and 112 transitions. Second operand has 21 states, 17 states have (on average 2.5294117647058822) internal successors, (43), 15 states have internal predecessors, (43), 8 states have call successors, (18), 10 states have call predecessors, (18), 4 states have return successors, (11), 4 states have call predecessors, (11), 4 states have call successors, (11) [2025-03-03 14:42:29,522 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:42:29,522 INFO L93 Difference]: Finished difference Result 158 states and 165 transitions. [2025-03-03 14:42:29,522 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 29 states. [2025-03-03 14:42:29,522 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 17 states have (on average 2.5294117647058822) internal successors, (43), 15 states have internal predecessors, (43), 8 states have call successors, (18), 10 states have call predecessors, (18), 4 states have return successors, (11), 4 states have call predecessors, (11), 4 states have call successors, (11) Word has length 65 [2025-03-03 14:42:29,523 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:42:29,523 INFO L225 Difference]: With dead ends: 158 [2025-03-03 14:42:29,523 INFO L226 Difference]: Without dead ends: 156 [2025-03-03 14:42:29,524 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 143 GetRequests, 96 SyntacticMatches, 13 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 174 ImplicationChecksByTransitivity, 2.7s TimeCoverageRelationStatistics Valid=172, Invalid=1088, Unknown=0, NotChecked=0, Total=1260 [2025-03-03 14:42:29,524 INFO L435 NwaCegarLoop]: 47 mSDtfsCounter, 76 mSDsluCounter, 386 mSDsCounter, 0 mSdLazyCounter, 749 mSolverCounterSat, 28 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 76 SdHoareTripleChecker+Valid, 433 SdHoareTripleChecker+Invalid, 777 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 28 IncrementalHoareTripleChecker+Valid, 749 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.0s IncrementalHoareTripleChecker+Time [2025-03-03 14:42:29,524 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [76 Valid, 433 Invalid, 777 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [28 Valid, 749 Invalid, 0 Unknown, 0 Unchecked, 2.0s Time] [2025-03-03 14:42:29,525 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 156 states. [2025-03-03 14:42:29,549 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 156 to 138. [2025-03-03 14:42:29,549 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 138 states, 91 states have (on average 1.043956043956044) internal successors, (95), 93 states have internal predecessors, (95), 22 states have call successors, (22), 21 states have call predecessors, (22), 24 states have return successors, (28), 23 states have call predecessors, (28), 20 states have call successors, (28) [2025-03-03 14:42:29,550 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 138 states to 138 states and 145 transitions. [2025-03-03 14:42:29,550 INFO L78 Accepts]: Start accepts. Automaton has 138 states and 145 transitions. Word has length 65 [2025-03-03 14:42:29,550 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:42:29,550 INFO L471 AbstractCegarLoop]: Abstraction has 138 states and 145 transitions. [2025-03-03 14:42:29,550 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 17 states have (on average 2.5294117647058822) internal successors, (43), 15 states have internal predecessors, (43), 8 states have call successors, (18), 10 states have call predecessors, (18), 4 states have return successors, (11), 4 states have call predecessors, (11), 4 states have call successors, (11) [2025-03-03 14:42:29,550 INFO L276 IsEmpty]: Start isEmpty. Operand 138 states and 145 transitions. [2025-03-03 14:42:29,551 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 68 [2025-03-03 14:42:29,551 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:42:29,551 INFO L218 NwaCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:42:29,556 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2025-03-03 14:42:29,751 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:42:29,751 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:42:29,751 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:42:29,752 INFO L85 PathProgramCache]: Analyzing trace with hash -459873323, now seen corresponding path program 1 times [2025-03-03 14:42:29,752 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:42:29,752 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1855020361] [2025-03-03 14:42:29,752 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:42:29,752 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:42:29,757 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 67 statements into 1 equivalence classes. [2025-03-03 14:42:29,766 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 67 of 67 statements. [2025-03-03 14:42:29,766 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:42:29,766 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 14:42:29,767 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1865229835] [2025-03-03 14:42:29,767 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:42:29,767 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:42:29,767 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:42:29,769 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:42:29,771 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2025-03-03 14:42:29,830 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 67 statements into 1 equivalence classes. [2025-03-03 14:42:29,861 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 67 of 67 statements. [2025-03-03 14:42:29,861 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:42:29,861 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:42:29,864 INFO L256 TraceCheckSpWp]: Trace formula consists of 318 conjuncts, 105 conjuncts are in the unsatisfiable core [2025-03-03 14:42:29,867 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:42:29,876 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 [2025-03-03 14:42:29,886 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 [2025-03-03 14:42:29,896 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 [2025-03-03 14:42:44,300 INFO L349 Elim1Store]: treesize reduction 14, result has 58.8 percent of original size [2025-03-03 14:42:44,301 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 25 treesize of output 32 [2025-03-03 14:42:44,335 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 [2025-03-03 14:42:44,362 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 3 [2025-03-03 14:42:44,593 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-03 14:42:44,594 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 45 treesize of output 61 [2025-03-03 14:42:45,997 INFO L134 CoverageAnalysis]: Checked inductivity of 139 backedges. 77 proven. 44 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2025-03-03 14:42:45,997 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:43:01,692 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:43:01,693 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1855020361] [2025-03-03 14:43:01,693 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 14:43:01,693 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1865229835] [2025-03-03 14:43:01,693 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1865229835] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:43:01,693 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-03 14:43:01,693 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [26] total 26 [2025-03-03 14:43:01,693 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1017724635] [2025-03-03 14:43:01,693 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-03 14:43:01,693 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2025-03-03 14:43:01,693 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:43:01,693 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2025-03-03 14:43:01,694 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=124, Invalid=929, Unknown=3, NotChecked=0, Total=1056 [2025-03-03 14:43:01,694 INFO L87 Difference]: Start difference. First operand 138 states and 145 transitions. Second operand has 26 states, 20 states have (on average 2.0) internal successors, (40), 23 states have internal predecessors, (40), 9 states have call successors, (11), 5 states have call predecessors, (11), 8 states have return successors, (10), 6 states have call predecessors, (10), 8 states have call successors, (10) [2025-03-03 14:43:20,181 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 [0] [2025-03-03 14:43:28,336 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 [0]