./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/recursified_nla-digbench/recursified_egcd-ll.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version e2fb8bed 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_egcd-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 494d69f416dd1b0b56dc0371ee72744b83dbc298da37778d271d6f779b4cdcdc --- Real Ultimate output --- This is Ultimate 0.3.0-?-e2fb8be-m [2025-03-08 05:48:52,138 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-08 05:48:52,195 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2025-03-08 05:48:52,200 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-08 05:48:52,200 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-08 05:48:52,220 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-08 05:48:52,221 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-08 05:48:52,221 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-08 05:48:52,222 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-08 05:48:52,222 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-08 05:48:52,222 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-03-08 05:48:52,222 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-03-08 05:48:52,223 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-08 05:48:52,223 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-08 05:48:52,223 INFO L153 SettingsManager]: * Use SBE=true [2025-03-08 05:48:52,223 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-08 05:48:52,223 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-03-08 05:48:52,224 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-08 05:48:52,224 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-08 05:48:52,224 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-08 05:48:52,224 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-08 05:48:52,224 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-03-08 05:48:52,224 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-03-08 05:48:52,224 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-03-08 05:48:52,224 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-08 05:48:52,224 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-08 05:48:52,224 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-08 05:48:52,224 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-08 05:48:52,224 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-08 05:48:52,224 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-08 05:48:52,224 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-03-08 05:48:52,225 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-03-08 05:48:52,225 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-08 05:48:52,225 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-08 05:48:52,225 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-03-08 05:48:52,225 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-03-08 05:48:52,225 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-03-08 05:48:52,225 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-08 05:48:52,225 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-03-08 05:48:52,225 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-03-08 05:48:52,225 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-03-08 05:48:52,225 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-03-08 05:48:52,225 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-03-08 05:48:52,225 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 -> 494d69f416dd1b0b56dc0371ee72744b83dbc298da37778d271d6f779b4cdcdc [2025-03-08 05:48:52,454 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-08 05:48:52,460 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-08 05:48:52,462 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-08 05:48:52,463 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-08 05:48:52,463 INFO L274 PluginConnector]: CDTParser initialized [2025-03-08 05:48:52,464 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursified_nla-digbench/recursified_egcd-ll.c [2025-03-08 05:48:53,562 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/5543e6951/9849032cf6334ef8afdb7844bbbc188f/FLAG08bb7e24e [2025-03-08 05:48:53,796 INFO L384 CDTParser]: Found 1 translation units. [2025-03-08 05:48:53,797 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursified_nla-digbench/recursified_egcd-ll.c [2025-03-08 05:48:53,802 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/5543e6951/9849032cf6334ef8afdb7844bbbc188f/FLAG08bb7e24e [2025-03-08 05:48:54,136 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/5543e6951/9849032cf6334ef8afdb7844bbbc188f [2025-03-08 05:48:54,138 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-08 05:48:54,138 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-08 05:48:54,139 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-08 05:48:54,139 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-08 05:48:54,142 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-08 05:48:54,143 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.03 05:48:54" (1/1) ... [2025-03-08 05:48:54,143 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@deefa6d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:48:54, skipping insertion in model container [2025-03-08 05:48:54,143 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.03 05:48:54" (1/1) ... [2025-03-08 05:48:54,152 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-08 05:48:54,244 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_egcd-ll.c[1019,1032] [2025-03-08 05:48:54,261 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-08 05:48:54,268 INFO L200 MainTranslator]: Completed pre-run [2025-03-08 05:48:54,275 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_egcd-ll.c[1019,1032] [2025-03-08 05:48:54,284 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-08 05:48:54,293 INFO L204 MainTranslator]: Completed translation [2025-03-08 05:48:54,293 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:48:54 WrapperNode [2025-03-08 05:48:54,293 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-08 05:48:54,294 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-08 05:48:54,294 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-08 05:48:54,294 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-08 05:48:54,298 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:48:54" (1/1) ... [2025-03-08 05:48:54,302 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:48:54" (1/1) ... [2025-03-08 05:48:54,313 INFO L138 Inliner]: procedures = 16, calls = 106, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 112 [2025-03-08 05:48:54,314 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-08 05:48:54,314 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-08 05:48:54,314 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-08 05:48:54,314 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-08 05:48:54,319 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:48:54" (1/1) ... [2025-03-08 05:48:54,319 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:48:54" (1/1) ... [2025-03-08 05:48:54,321 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:48:54" (1/1) ... [2025-03-08 05:48:54,331 INFO L175 MemorySlicer]: Split 66 memory accesses to 9 slices as follows [8, 2, 8, 8, 8, 8, 10, 7, 7]. 15 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [0, 2, 0, 0, 0, 0, 0, 0, 0]. The 14 writes are split as follows [2, 0, 2, 2, 2, 2, 2, 1, 1]. [2025-03-08 05:48:54,331 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:48:54" (1/1) ... [2025-03-08 05:48:54,332 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:48:54" (1/1) ... [2025-03-08 05:48:54,340 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:48:54" (1/1) ... [2025-03-08 05:48:54,341 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:48:54" (1/1) ... [2025-03-08 05:48:54,342 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:48:54" (1/1) ... [2025-03-08 05:48:54,342 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:48:54" (1/1) ... [2025-03-08 05:48:54,344 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-08 05:48:54,345 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-08 05:48:54,345 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-08 05:48:54,345 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-08 05:48:54,345 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:48:54" (1/1) ... [2025-03-08 05:48:54,350 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-08 05:48:54,358 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:48:54,367 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-08 05:48:54,369 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-08 05:48:54,384 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-08 05:48:54,384 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_33_to_48_0 [2025-03-08 05:48:54,385 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_33_to_48_0 [2025-03-08 05:48:54,385 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2025-03-08 05:48:54,385 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2025-03-08 05:48:54,385 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-03-08 05:48:54,385 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2025-03-08 05:48:54,385 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2025-03-08 05:48:54,385 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#3 [2025-03-08 05:48:54,385 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#4 [2025-03-08 05:48:54,385 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#5 [2025-03-08 05:48:54,385 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#6 [2025-03-08 05:48:54,385 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#7 [2025-03-08 05:48:54,385 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#8 [2025-03-08 05:48:54,386 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2025-03-08 05:48:54,386 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2025-03-08 05:48:54,386 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2025-03-08 05:48:54,386 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#2 [2025-03-08 05:48:54,386 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#3 [2025-03-08 05:48:54,386 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#4 [2025-03-08 05:48:54,386 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#5 [2025-03-08 05:48:54,386 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#6 [2025-03-08 05:48:54,386 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#7 [2025-03-08 05:48:54,386 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#8 [2025-03-08 05:48:54,386 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-08 05:48:54,386 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-08 05:48:54,386 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2025-03-08 05:48:54,386 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2025-03-08 05:48:54,387 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#2 [2025-03-08 05:48:54,387 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#3 [2025-03-08 05:48:54,387 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#4 [2025-03-08 05:48:54,387 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#5 [2025-03-08 05:48:54,387 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#6 [2025-03-08 05:48:54,387 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#7 [2025-03-08 05:48:54,387 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#8 [2025-03-08 05:48:54,387 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2025-03-08 05:48:54,387 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2025-03-08 05:48:54,387 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2025-03-08 05:48:54,463 INFO L256 CfgBuilder]: Building ICFG [2025-03-08 05:48:54,465 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-08 05:48:54,645 INFO L1307 $ProcedureCfgBuilder]: dead code at ProgramPoint L84: 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_~#b~0#1.base, main_~#b~0#1.offset);havoc main_~#b~0#1.base, main_~#b~0#1.offset;call ULTIMATE.dealloc(main_~#p~0#1.base, main_~#p~0#1.offset);havoc main_~#p~0#1.base, main_~#p~0#1.offset;call ULTIMATE.dealloc(main_~#q~0#1.base, main_~#q~0#1.offset);havoc main_~#q~0#1.base, main_~#q~0#1.offset;call ULTIMATE.dealloc(main_~#r~0#1.base, main_~#r~0#1.offset);havoc main_~#r~0#1.base, main_~#r~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_~#x~0#1.base, main_~#x~0#1.offset);havoc main_~#x~0#1.base, main_~#x~0#1.offset;call ULTIMATE.dealloc(main_~#y~0#1.base, main_~#y~0#1.offset);havoc main_~#y~0#1.base, main_~#y~0#1.offset; [2025-03-08 05:48:54,671 INFO L? ?]: Removed 13 outVars from TransFormulas that were not future-live. [2025-03-08 05:48:54,671 INFO L307 CfgBuilder]: Performing block encoding [2025-03-08 05:48:54,677 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-08 05:48:54,678 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-08 05:48:54,678 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 08.03 05:48:54 BoogieIcfgContainer [2025-03-08 05:48:54,678 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-08 05:48:54,680 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-03-08 05:48:54,680 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-03-08 05:48:54,683 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-03-08 05:48:54,683 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 08.03 05:48:54" (1/3) ... [2025-03-08 05:48:54,683 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3f5ccfc2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.03 05:48:54, skipping insertion in model container [2025-03-08 05:48:54,684 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:48:54" (2/3) ... [2025-03-08 05:48:54,684 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3f5ccfc2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.03 05:48:54, skipping insertion in model container [2025-03-08 05:48:54,684 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 08.03 05:48:54" (3/3) ... [2025-03-08 05:48:54,684 INFO L128 eAbstractionObserver]: Analyzing ICFG recursified_egcd-ll.c [2025-03-08 05:48:54,695 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-03-08 05:48:54,697 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG recursified_egcd-ll.c that has 4 procedures, 42 locations, 1 initial locations, 0 loop locations, and 1 error locations. [2025-03-08 05:48:54,728 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-03-08 05:48:54,736 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;@3600460d, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-03-08 05:48:54,737 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-03-08 05:48:54,739 INFO L276 IsEmpty]: Start isEmpty. Operand has 42 states, 26 states have (on average 1.2307692307692308) internal successors, (32), 28 states have internal predecessors, (32), 11 states have call successors, (11), 3 states have call predecessors, (11), 3 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2025-03-08 05:48:54,743 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2025-03-08 05:48:54,743 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:48:54,743 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:48:54,744 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:48:54,747 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:48:54,748 INFO L85 PathProgramCache]: Analyzing trace with hash 426273804, now seen corresponding path program 1 times [2025-03-08 05:48:54,752 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:48:54,755 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1582787855] [2025-03-08 05:48:54,755 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:48:54,755 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:48:54,822 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 21 statements into 1 equivalence classes. [2025-03-08 05:48:54,849 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 21 of 21 statements. [2025-03-08 05:48:54,851 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:48:54,851 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:48:54,918 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2025-03-08 05:48:54,918 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:48:54,918 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1582787855] [2025-03-08 05:48:54,918 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1582787855] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:48:54,919 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [42282275] [2025-03-08 05:48:54,919 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:48:54,919 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:48:54,919 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:48:54,921 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-08 05:48:54,923 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-08 05:48:54,996 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 21 statements into 1 equivalence classes. [2025-03-08 05:48:55,034 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 21 of 21 statements. [2025-03-08 05:48:55,035 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:48:55,035 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:48:55,036 INFO L256 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 1 conjuncts are in the unsatisfiable core [2025-03-08 05:48:55,039 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:48:55,049 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2025-03-08 05:48:55,050 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-08 05:48:55,050 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [42282275] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:48:55,050 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-08 05:48:55,050 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [2] total 2 [2025-03-08 05:48:55,051 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2080456047] [2025-03-08 05:48:55,052 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:48:55,055 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2025-03-08 05:48:55,055 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:48:55,068 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2025-03-08 05:48:55,068 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-03-08 05:48:55,070 INFO L87 Difference]: Start difference. First operand has 42 states, 26 states have (on average 1.2307692307692308) internal successors, (32), 28 states have internal predecessors, (32), 11 states have call successors, (11), 3 states have call predecessors, (11), 3 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) Second operand has 2 states, 2 states have (on average 7.0) internal successors, (14), 2 states have internal predecessors, (14), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-08 05:48:55,086 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:48:55,087 INFO L93 Difference]: Finished difference Result 81 states and 115 transitions. [2025-03-08 05:48:55,087 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2025-03-08 05:48:55,089 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 7.0) internal successors, (14), 2 states have internal predecessors, (14), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Word has length 21 [2025-03-08 05:48:55,089 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:48:55,093 INFO L225 Difference]: With dead ends: 81 [2025-03-08 05:48:55,094 INFO L226 Difference]: Without dead ends: 38 [2025-03-08 05:48:55,096 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 22 GetRequests, 22 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-03-08 05:48:55,100 INFO L435 NwaCegarLoop]: 51 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 51 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-08 05:48:55,100 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 51 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-08 05:48:55,110 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 38 states. [2025-03-08 05:48:55,131 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 38 to 38. [2025-03-08 05:48:55,131 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 38 states, 23 states have (on average 1.1304347826086956) internal successors, (26), 25 states have internal predecessors, (26), 11 states have call successors, (11), 3 states have call predecessors, (11), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2025-03-08 05:48:55,135 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 38 states to 38 states and 47 transitions. [2025-03-08 05:48:55,136 INFO L78 Accepts]: Start accepts. Automaton has 38 states and 47 transitions. Word has length 21 [2025-03-08 05:48:55,137 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:48:55,137 INFO L471 AbstractCegarLoop]: Abstraction has 38 states and 47 transitions. [2025-03-08 05:48:55,137 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 7.0) internal successors, (14), 2 states have internal predecessors, (14), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-08 05:48:55,137 INFO L276 IsEmpty]: Start isEmpty. Operand 38 states and 47 transitions. [2025-03-08 05:48:55,138 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2025-03-08 05:48:55,139 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:48:55,139 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:48:55,146 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-08 05:48:55,339 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable0 [2025-03-08 05:48:55,340 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:48:55,341 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:48:55,341 INFO L85 PathProgramCache]: Analyzing trace with hash -17367858, now seen corresponding path program 1 times [2025-03-08 05:48:55,341 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:48:55,341 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [101904738] [2025-03-08 05:48:55,341 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:48:55,341 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:48:55,355 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 21 statements into 1 equivalence classes. [2025-03-08 05:48:55,401 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 21 of 21 statements. [2025-03-08 05:48:55,402 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:48:55,402 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:48:55,406 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1766362241] [2025-03-08 05:48:55,408 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:48:55,408 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:48:55,408 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:48:55,410 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-08 05:48:55,411 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-08 05:48:55,478 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 21 statements into 1 equivalence classes. [2025-03-08 05:48:55,531 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 21 of 21 statements. [2025-03-08 05:48:55,532 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:48:55,532 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:48:55,534 INFO L256 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 60 conjuncts are in the unsatisfiable core [2025-03-08 05:48:55,541 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:48:55,578 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-08 05:48:55,590 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-08 05:48:55,598 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-08 05:48:55,607 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-08 05:48:55,774 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-08 05:48:55,774 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-08 05:48:55,774 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:48:55,774 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [101904738] [2025-03-08 05:48:55,774 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:48:55,774 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1766362241] [2025-03-08 05:48:55,774 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1766362241] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:48:55,775 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-08 05:48:55,775 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2025-03-08 05:48:55,775 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [179052157] [2025-03-08 05:48:55,775 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:48:55,775 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2025-03-08 05:48:55,775 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:48:55,776 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-03-08 05:48:55,776 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2025-03-08 05:48:55,776 INFO L87 Difference]: Start difference. First operand 38 states and 47 transitions. Second operand has 8 states, 6 states have (on average 2.0) internal successors, (12), 6 states have internal predecessors, (12), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2025-03-08 05:48:55,969 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:48:55,970 INFO L93 Difference]: Finished difference Result 61 states and 76 transitions. [2025-03-08 05:48:55,970 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2025-03-08 05:48:55,970 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 6 states have (on average 2.0) internal successors, (12), 6 states have internal predecessors, (12), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 21 [2025-03-08 05:48:55,970 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:48:55,971 INFO L225 Difference]: With dead ends: 61 [2025-03-08 05:48:55,971 INFO L226 Difference]: Without dead ends: 59 [2025-03-08 05:48:55,971 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 23 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2025-03-08 05:48:55,972 INFO L435 NwaCegarLoop]: 35 mSDtfsCounter, 20 mSDsluCounter, 174 mSDsCounter, 0 mSdLazyCounter, 118 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 209 SdHoareTripleChecker+Invalid, 126 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 118 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 05:48:55,972 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 209 Invalid, 126 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 118 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 05:48:55,973 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 59 states. [2025-03-08 05:48:55,996 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 59 to 53. [2025-03-08 05:48:55,997 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 53 states, 33 states have (on average 1.121212121212121) internal successors, (37), 35 states have internal predecessors, (37), 14 states have call successors, (14), 5 states have call predecessors, (14), 5 states have return successors, (14), 13 states have call predecessors, (14), 13 states have call successors, (14) [2025-03-08 05:48:55,999 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 65 transitions. [2025-03-08 05:48:55,999 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 65 transitions. Word has length 21 [2025-03-08 05:48:56,000 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:48:56,001 INFO L471 AbstractCegarLoop]: Abstraction has 53 states and 65 transitions. [2025-03-08 05:48:56,001 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 6 states have (on average 2.0) internal successors, (12), 6 states have internal predecessors, (12), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2025-03-08 05:48:56,001 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 65 transitions. [2025-03-08 05:48:56,001 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2025-03-08 05:48:56,002 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:48:56,002 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:48:56,009 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2025-03-08 05:48:56,202 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,SelfDestructingSolverStorable1 [2025-03-08 05:48:56,202 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:48:56,203 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:48:56,203 INFO L85 PathProgramCache]: Analyzing trace with hash 979391871, now seen corresponding path program 1 times [2025-03-08 05:48:56,203 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:48:56,203 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [406024440] [2025-03-08 05:48:56,203 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:48:56,203 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:48:56,215 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 27 statements into 1 equivalence classes. [2025-03-08 05:48:56,234 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 27 of 27 statements. [2025-03-08 05:48:56,236 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:48:56,236 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:48:56,238 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [915102552] [2025-03-08 05:48:56,238 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:48:56,238 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:48:56,238 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:48:56,240 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-08 05:48:56,243 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-08 05:48:56,310 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 27 statements into 1 equivalence classes. [2025-03-08 05:48:56,354 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 27 of 27 statements. [2025-03-08 05:48:56,355 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:48:56,355 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:48:56,357 INFO L256 TraceCheckSpWp]: Trace formula consists of 273 conjuncts, 73 conjuncts are in the unsatisfiable core [2025-03-08 05:48:56,360 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:48:56,365 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-03-08 05:48:56,367 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-03-08 05:48:56,375 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-03-08 05:48:56,380 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-08 05:48:56,385 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-08 05:48:56,572 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-08 05:48:56,576 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2025-03-08 05:48:56,581 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2025-03-08 05:48:56,625 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-08 05:48:56,626 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:48:56,771 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-08 05:48:56,772 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:48:56,772 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [406024440] [2025-03-08 05:48:56,772 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:48:56,772 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [915102552] [2025-03-08 05:48:56,772 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [915102552] provided 1 perfect and 1 imperfect interpolant sequences [2025-03-08 05:48:56,772 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-08 05:48:56,772 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [9] total 13 [2025-03-08 05:48:56,772 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1952115714] [2025-03-08 05:48:56,773 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:48:56,773 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2025-03-08 05:48:56,773 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:48:56,774 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-03-08 05:48:56,774 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=126, Unknown=0, NotChecked=0, Total=156 [2025-03-08 05:48:56,775 INFO L87 Difference]: Start difference. First operand 53 states and 65 transitions. Second operand has 8 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 6 states have internal predecessors, (16), 4 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-08 05:48:57,046 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:48:57,046 INFO L93 Difference]: Finished difference Result 75 states and 93 transitions. [2025-03-08 05:48:57,047 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-03-08 05:48:57,047 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 6 states have internal predecessors, (16), 4 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 27 [2025-03-08 05:48:57,047 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:48:57,049 INFO L225 Difference]: With dead ends: 75 [2025-03-08 05:48:57,049 INFO L226 Difference]: Without dead ends: 73 [2025-03-08 05:48:57,049 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 55 GetRequests, 38 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-08 05:48:57,049 INFO L435 NwaCegarLoop]: 37 mSDtfsCounter, 20 mSDsluCounter, 176 mSDsCounter, 0 mSdLazyCounter, 140 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 20 SdHoareTripleChecker+Valid, 213 SdHoareTripleChecker+Invalid, 149 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 140 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-08 05:48:57,049 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [20 Valid, 213 Invalid, 149 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 140 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-08 05:48:57,050 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 73 states. [2025-03-08 05:48:57,061 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 73 to 72. [2025-03-08 05:48:57,062 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 72 states, 45 states have (on average 1.1333333333333333) internal successors, (51), 48 states have internal predecessors, (51), 18 states have call successors, (18), 7 states have call predecessors, (18), 8 states have return successors, (21), 17 states have call predecessors, (21), 17 states have call successors, (21) [2025-03-08 05:48:57,064 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 72 states to 72 states and 90 transitions. [2025-03-08 05:48:57,065 INFO L78 Accepts]: Start accepts. Automaton has 72 states and 90 transitions. Word has length 27 [2025-03-08 05:48:57,065 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:48:57,065 INFO L471 AbstractCegarLoop]: Abstraction has 72 states and 90 transitions. [2025-03-08 05:48:57,065 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 6 states have internal predecessors, (16), 4 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-08 05:48:57,066 INFO L276 IsEmpty]: Start isEmpty. Operand 72 states and 90 transitions. [2025-03-08 05:48:57,066 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2025-03-08 05:48:57,066 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:48:57,066 INFO L218 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:48:57,072 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2025-03-08 05:48:57,268 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:48:57,268 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:48:57,268 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:48:57,268 INFO L85 PathProgramCache]: Analyzing trace with hash 923786354, now seen corresponding path program 1 times [2025-03-08 05:48:57,269 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:48:57,269 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [77659670] [2025-03-08 05:48:57,269 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:48:57,269 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:48:57,279 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 33 statements into 1 equivalence classes. [2025-03-08 05:48:57,311 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 33 of 33 statements. [2025-03-08 05:48:57,311 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:48:57,311 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:48:57,312 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1479736277] [2025-03-08 05:48:57,315 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:48:57,315 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:48:57,315 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:48:57,317 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-08 05:48:57,318 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-08 05:48:57,388 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 33 statements into 1 equivalence classes. [2025-03-08 05:48:57,424 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 33 of 33 statements. [2025-03-08 05:48:57,425 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:48:57,425 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:48:57,427 INFO L256 TraceCheckSpWp]: Trace formula consists of 292 conjuncts, 79 conjuncts are in the unsatisfiable core [2025-03-08 05:48:57,429 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:48:57,436 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-03-08 05:48:57,438 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-03-08 05:48:57,467 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-03-08 05:48:57,470 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-08 05:48:57,476 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-08 05:48:57,770 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-08 05:48:57,774 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 10 [2025-03-08 05:48:57,780 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2025-03-08 05:48:57,821 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 3 proven. 4 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2025-03-08 05:48:57,821 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:48:57,975 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2025-03-08 05:48:57,975 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:48:57,975 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [77659670] [2025-03-08 05:48:57,975 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:48:57,975 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1479736277] [2025-03-08 05:48:57,975 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1479736277] provided 1 perfect and 1 imperfect interpolant sequences [2025-03-08 05:48:57,976 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-08 05:48:57,976 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [13] total 17 [2025-03-08 05:48:57,976 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [192798340] [2025-03-08 05:48:57,976 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:48:57,976 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2025-03-08 05:48:57,976 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:48:57,976 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-03-08 05:48:57,977 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=39, Invalid=233, Unknown=0, NotChecked=0, Total=272 [2025-03-08 05:48:57,977 INFO L87 Difference]: Start difference. First operand 72 states and 90 transitions. Second operand has 8 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 6 states have internal predecessors, (17), 4 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2025-03-08 05:48:58,290 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:48:58,290 INFO L93 Difference]: Finished difference Result 101 states and 129 transitions. [2025-03-08 05:48:58,290 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-03-08 05:48:58,291 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 6 states have internal predecessors, (17), 4 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 33 [2025-03-08 05:48:58,291 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:48:58,291 INFO L225 Difference]: With dead ends: 101 [2025-03-08 05:48:58,292 INFO L226 Difference]: Without dead ends: 99 [2025-03-08 05:48:58,292 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 67 GetRequests, 44 SyntacticMatches, 5 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 39 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=53, Invalid=327, Unknown=0, NotChecked=0, Total=380 [2025-03-08 05:48:58,292 INFO L435 NwaCegarLoop]: 33 mSDtfsCounter, 22 mSDsluCounter, 145 mSDsCounter, 0 mSdLazyCounter, 166 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 178 SdHoareTripleChecker+Invalid, 174 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 166 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-08 05:48:58,292 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [25 Valid, 178 Invalid, 174 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 166 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-08 05:48:58,293 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 99 states. [2025-03-08 05:48:58,310 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 99 to 92. [2025-03-08 05:48:58,311 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 92 states, 58 states have (on average 1.1551724137931034) internal successors, (67), 62 states have internal predecessors, (67), 22 states have call successors, (22), 9 states have call predecessors, (22), 11 states have return successors, (28), 21 states have call predecessors, (28), 21 states have call successors, (28) [2025-03-08 05:48:58,311 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 92 states to 92 states and 117 transitions. [2025-03-08 05:48:58,312 INFO L78 Accepts]: Start accepts. Automaton has 92 states and 117 transitions. Word has length 33 [2025-03-08 05:48:58,312 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:48:58,312 INFO L471 AbstractCegarLoop]: Abstraction has 92 states and 117 transitions. [2025-03-08 05:48:58,312 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 6 states have internal predecessors, (17), 4 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2025-03-08 05:48:58,312 INFO L276 IsEmpty]: Start isEmpty. Operand 92 states and 117 transitions. [2025-03-08 05:48:58,313 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2025-03-08 05:48:58,314 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:48:58,314 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:48:58,321 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2025-03-08 05:48:58,514 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:48:58,515 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:48:58,515 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:48:58,515 INFO L85 PathProgramCache]: Analyzing trace with hash 1144909765, now seen corresponding path program 1 times [2025-03-08 05:48:58,515 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:48:58,515 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [931764095] [2025-03-08 05:48:58,515 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:48:58,515 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:48:58,527 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 43 statements into 1 equivalence classes. [2025-03-08 05:48:58,543 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 43 of 43 statements. [2025-03-08 05:48:58,545 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:48:58,545 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:48:58,869 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2025-03-08 05:48:58,869 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:48:58,869 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [931764095] [2025-03-08 05:48:58,869 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [931764095] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:48:58,869 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-08 05:48:58,869 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2025-03-08 05:48:58,869 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1719449092] [2025-03-08 05:48:58,869 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:48:58,870 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2025-03-08 05:48:58,870 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:48:58,870 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2025-03-08 05:48:58,870 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=57, Unknown=0, NotChecked=0, Total=72 [2025-03-08 05:48:58,870 INFO L87 Difference]: Start difference. First operand 92 states and 117 transitions. Second operand has 9 states, 8 states have (on average 2.625) internal successors, (21), 7 states have internal predecessors, (21), 3 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 3 states have call predecessors, (6), 2 states have call successors, (6) [2025-03-08 05:48:59,001 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:48:59,002 INFO L93 Difference]: Finished difference Result 98 states and 122 transitions. [2025-03-08 05:48:59,002 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-03-08 05:48:59,002 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 2.625) internal successors, (21), 7 states have internal predecessors, (21), 3 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 3 states have call predecessors, (6), 2 states have call successors, (6) Word has length 43 [2025-03-08 05:48:59,002 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:48:59,003 INFO L225 Difference]: With dead ends: 98 [2025-03-08 05:48:59,003 INFO L226 Difference]: Without dead ends: 96 [2025-03-08 05:48:59,003 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=27, Invalid=105, Unknown=0, NotChecked=0, Total=132 [2025-03-08 05:48:59,004 INFO L435 NwaCegarLoop]: 37 mSDtfsCounter, 9 mSDsluCounter, 210 mSDsCounter, 0 mSdLazyCounter, 127 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 247 SdHoareTripleChecker+Invalid, 128 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 127 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 05:48:59,004 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 247 Invalid, 128 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 127 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 05:48:59,004 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 96 states. [2025-03-08 05:48:59,021 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 96 to 96. [2025-03-08 05:48:59,021 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 96 states, 61 states have (on average 1.1475409836065573) internal successors, (70), 65 states have internal predecessors, (70), 22 states have call successors, (22), 10 states have call predecessors, (22), 12 states have return successors, (28), 21 states have call predecessors, (28), 21 states have call successors, (28) [2025-03-08 05:48:59,022 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 120 transitions. [2025-03-08 05:48:59,022 INFO L78 Accepts]: Start accepts. Automaton has 96 states and 120 transitions. Word has length 43 [2025-03-08 05:48:59,022 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:48:59,023 INFO L471 AbstractCegarLoop]: Abstraction has 96 states and 120 transitions. [2025-03-08 05:48:59,023 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 2.625) internal successors, (21), 7 states have internal predecessors, (21), 3 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 3 states have call predecessors, (6), 2 states have call successors, (6) [2025-03-08 05:48:59,023 INFO L276 IsEmpty]: Start isEmpty. Operand 96 states and 120 transitions. [2025-03-08 05:48:59,023 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2025-03-08 05:48:59,023 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:48:59,023 INFO L218 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:48:59,024 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4 [2025-03-08 05:48:59,024 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:48:59,024 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:48:59,024 INFO L85 PathProgramCache]: Analyzing trace with hash -1293273473, now seen corresponding path program 1 times [2025-03-08 05:48:59,024 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:48:59,024 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1284278731] [2025-03-08 05:48:59,024 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:48:59,024 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:48:59,034 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 44 statements into 1 equivalence classes. [2025-03-08 05:48:59,060 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 44 of 44 statements. [2025-03-08 05:48:59,060 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:48:59,060 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:48:59,062 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2042586438] [2025-03-08 05:48:59,063 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:48:59,063 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:48:59,064 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:48:59,065 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-08 05:48:59,067 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-08 05:48:59,129 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 44 statements into 1 equivalence classes. [2025-03-08 05:48:59,187 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 44 of 44 statements. [2025-03-08 05:48:59,187 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:48:59,188 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:48:59,191 INFO L256 TraceCheckSpWp]: Trace formula consists of 407 conjuncts, 106 conjuncts are in the unsatisfiable core [2025-03-08 05:48:59,197 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:48:59,205 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-08 05:48:59,210 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-08 05:48:59,214 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-08 05:48:59,219 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-08 05:48:59,530 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-08 05:48:59,538 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 13 [2025-03-08 05:48:59,637 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2025-03-08 05:48:59,637 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:49:42,994 WARN L851 $PredicateComparison]: unable to prove that (forall ((|v_func_to_recursive_line_33_to_48_0_#t~mem6_9| Int)) (let ((.cse0 (select (select |c_#memory_int#4| c_func_to_recursive_line_33_to_48_0_~s.base) c_func_to_recursive_line_33_to_48_0_~s.offset))) (or (< (select (select |c_#memory_int#5| c_func_to_recursive_line_33_to_48_0_~r.base) c_func_to_recursive_line_33_to_48_0_~r.offset) (+ |v_func_to_recursive_line_33_to_48_0_#t~mem6_9| .cse0)) (= (let ((.cse1 (select (select |c_#memory_int#2| c_func_to_recursive_line_33_to_48_0_~q.base) c_func_to_recursive_line_33_to_48_0_~q.offset))) (+ (* |v_func_to_recursive_line_33_to_48_0_#t~mem6_9| .cse1) (* .cse1 .cse0) 1)) (* (select (select |c_#memory_int#3| c_func_to_recursive_line_33_to_48_0_~p.base) c_func_to_recursive_line_33_to_48_0_~p.offset) .cse0))))) is different from false [2025-03-08 05:49:43,038 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:49:43,038 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1284278731] [2025-03-08 05:49:43,038 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:49:43,038 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2042586438] [2025-03-08 05:49:43,038 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2042586438] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:49:43,038 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-08 05:49:43,038 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2025-03-08 05:49:43,038 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1574490518] [2025-03-08 05:49:43,038 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-08 05:49:43,039 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2025-03-08 05:49:43,039 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:49:43,039 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2025-03-08 05:49:43,039 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=140, Unknown=11, NotChecked=24, Total=210 [2025-03-08 05:49:43,039 INFO L87 Difference]: Start difference. First operand 96 states and 120 transitions. Second operand has 11 states, 9 states have (on average 2.4444444444444446) internal successors, (22), 8 states have internal predecessors, (22), 5 states have call successors, (8), 5 states have call predecessors, (8), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2025-03-08 05:49:43,453 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:49:43,454 INFO L93 Difference]: Finished difference Result 143 states and 171 transitions. [2025-03-08 05:49:43,456 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2025-03-08 05:49:43,456 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 9 states have (on average 2.4444444444444446) internal successors, (22), 8 states have internal predecessors, (22), 5 states have call successors, (8), 5 states have call predecessors, (8), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 44 [2025-03-08 05:49:43,456 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:49:43,457 INFO L225 Difference]: With dead ends: 143 [2025-03-08 05:49:43,457 INFO L226 Difference]: Without dead ends: 141 [2025-03-08 05:49:43,458 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 58 GetRequests, 34 SyntacticMatches, 7 SemanticMatches, 17 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 24 ImplicationChecksByTransitivity, 43.5s TimeCoverageRelationStatistics Valid=61, Invalid=238, Unknown=11, NotChecked=32, Total=342 [2025-03-08 05:49:43,458 INFO L435 NwaCegarLoop]: 45 mSDtfsCounter, 42 mSDsluCounter, 247 mSDsCounter, 0 mSdLazyCounter, 271 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 44 SdHoareTripleChecker+Valid, 292 SdHoareTripleChecker+Invalid, 286 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 271 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-03-08 05:49:43,458 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [44 Valid, 292 Invalid, 286 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 271 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-03-08 05:49:43,459 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 141 states. [2025-03-08 05:49:43,485 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 141 to 138. [2025-03-08 05:49:43,487 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 138 states, 88 states have (on average 1.125) internal successors, (99), 93 states have internal predecessors, (99), 30 states have call successors, (30), 16 states have call predecessors, (30), 19 states have return successors, (37), 29 states have call predecessors, (37), 28 states have call successors, (37) [2025-03-08 05:49:43,488 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 138 states to 138 states and 166 transitions. [2025-03-08 05:49:43,489 INFO L78 Accepts]: Start accepts. Automaton has 138 states and 166 transitions. Word has length 44 [2025-03-08 05:49:43,489 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:49:43,489 INFO L471 AbstractCegarLoop]: Abstraction has 138 states and 166 transitions. [2025-03-08 05:49:43,489 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 9 states have (on average 2.4444444444444446) internal successors, (22), 8 states have internal predecessors, (22), 5 states have call successors, (8), 5 states have call predecessors, (8), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2025-03-08 05:49:43,489 INFO L276 IsEmpty]: Start isEmpty. Operand 138 states and 166 transitions. [2025-03-08 05:49:43,490 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2025-03-08 05:49:43,491 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:49:43,491 INFO L218 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:49:43,497 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-08 05:49:43,691 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:49:43,692 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:49:43,692 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:49:43,692 INFO L85 PathProgramCache]: Analyzing trace with hash 449536862, now seen corresponding path program 1 times [2025-03-08 05:49:43,692 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:49:43,692 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [992832928] [2025-03-08 05:49:43,692 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:49:43,692 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:49:43,724 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 44 statements into 1 equivalence classes. [2025-03-08 05:49:43,743 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 44 of 44 statements. [2025-03-08 05:49:43,743 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:49:43,743 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:49:43,744 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1859119858] [2025-03-08 05:49:43,744 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:49:43,744 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:49:43,745 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:49:43,746 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-08 05:49:43,748 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-08 05:49:43,815 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 44 statements into 1 equivalence classes. [2025-03-08 05:49:43,865 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 44 of 44 statements. [2025-03-08 05:49:43,865 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:49:43,865 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:49:43,868 INFO L256 TraceCheckSpWp]: Trace formula consists of 407 conjuncts, 107 conjuncts are in the unsatisfiable core [2025-03-08 05:49:43,871 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:49:43,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-08 05:49:43,880 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-08 05:49:43,885 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-08 05:49:43,890 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-08 05:49:44,145 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-08 05:49:44,150 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 13 [2025-03-08 05:49:44,234 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2025-03-08 05:49:44,234 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:49:44,436 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 6 proven. 1 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2025-03-08 05:49:44,436 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:49:44,436 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [992832928] [2025-03-08 05:49:44,436 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:49:44,436 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1859119858] [2025-03-08 05:49:44,436 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1859119858] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 05:49:44,436 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-08 05:49:44,436 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 8] total 15 [2025-03-08 05:49:44,436 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [255987260] [2025-03-08 05:49:44,436 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-08 05:49:44,437 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2025-03-08 05:49:44,437 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:49:44,437 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2025-03-08 05:49:44,437 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=36, Invalid=174, Unknown=0, NotChecked=0, Total=210 [2025-03-08 05:49:44,437 INFO L87 Difference]: Start difference. First operand 138 states and 166 transitions. Second operand has 15 states, 11 states have (on average 3.090909090909091) internal successors, (34), 11 states have internal predecessors, (34), 8 states have call successors, (14), 6 states have call predecessors, (14), 2 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2025-03-08 05:49:46,014 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:49:46,015 INFO L93 Difference]: Finished difference Result 166 states and 206 transitions. [2025-03-08 05:49:46,015 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2025-03-08 05:49:46,015 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 11 states have (on average 3.090909090909091) internal successors, (34), 11 states have internal predecessors, (34), 8 states have call successors, (14), 6 states have call predecessors, (14), 2 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) Word has length 44 [2025-03-08 05:49:46,015 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:49:46,016 INFO L225 Difference]: With dead ends: 166 [2025-03-08 05:49:46,016 INFO L226 Difference]: Without dead ends: 164 [2025-03-08 05:49:46,017 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 96 GetRequests, 66 SyntacticMatches, 7 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 59 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=106, Invalid=494, Unknown=0, NotChecked=0, Total=600 [2025-03-08 05:49:46,017 INFO L435 NwaCegarLoop]: 40 mSDtfsCounter, 62 mSDsluCounter, 301 mSDsCounter, 0 mSdLazyCounter, 423 mSolverCounterSat, 29 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 64 SdHoareTripleChecker+Valid, 341 SdHoareTripleChecker+Invalid, 452 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 29 IncrementalHoareTripleChecker+Valid, 423 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.1s IncrementalHoareTripleChecker+Time [2025-03-08 05:49:46,017 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [64 Valid, 341 Invalid, 452 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [29 Valid, 423 Invalid, 0 Unknown, 0 Unchecked, 1.1s Time] [2025-03-08 05:49:46,018 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 164 states. [2025-03-08 05:49:46,035 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 164 to 158. [2025-03-08 05:49:46,036 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 158 states, 100 states have (on average 1.12) internal successors, (112), 106 states have internal predecessors, (112), 34 states have call successors, (34), 18 states have call predecessors, (34), 23 states have return successors, (48), 33 states have call predecessors, (48), 32 states have call successors, (48) [2025-03-08 05:49:46,037 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 158 states to 158 states and 194 transitions. [2025-03-08 05:49:46,037 INFO L78 Accepts]: Start accepts. Automaton has 158 states and 194 transitions. Word has length 44 [2025-03-08 05:49:46,037 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:49:46,037 INFO L471 AbstractCegarLoop]: Abstraction has 158 states and 194 transitions. [2025-03-08 05:49:46,037 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 11 states have (on average 3.090909090909091) internal successors, (34), 11 states have internal predecessors, (34), 8 states have call successors, (14), 6 states have call predecessors, (14), 2 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2025-03-08 05:49:46,037 INFO L276 IsEmpty]: Start isEmpty. Operand 158 states and 194 transitions. [2025-03-08 05:49:46,038 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2025-03-08 05:49:46,038 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:49:46,038 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:49:46,045 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-08 05:49:46,240 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:49:46,240 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:49:46,241 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:49:46,241 INFO L85 PathProgramCache]: Analyzing trace with hash -1341974087, now seen corresponding path program 1 times [2025-03-08 05:49:46,241 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:49:46,241 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1134905867] [2025-03-08 05:49:46,241 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:49:46,241 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:49:46,249 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 49 statements into 1 equivalence classes. [2025-03-08 05:49:46,261 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 49 of 49 statements. [2025-03-08 05:49:46,261 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:49:46,261 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:49:46,264 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2010350128] [2025-03-08 05:49:46,264 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:49:46,264 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:49:46,264 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:49:46,266 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-08 05:49:46,267 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-08 05:49:46,328 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 49 statements into 1 equivalence classes. [2025-03-08 05:49:46,365 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 49 of 49 statements. [2025-03-08 05:49:46,365 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:49:46,365 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:49:46,367 INFO L256 TraceCheckSpWp]: Trace formula consists of 332 conjuncts, 48 conjuncts are in the unsatisfiable core [2025-03-08 05:49:46,369 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:49:46,372 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-03-08 05:49:46,395 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-08 05:49:46,403 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-03-08 05:49:46,407 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-03-08 05:49:46,411 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-08 05:49:46,432 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-08 05:49:46,439 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-08 05:49:46,596 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-08 05:49:46,797 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 05:49:46,797 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 44 treesize of output 36 [2025-03-08 05:49:46,804 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 05:49:46,804 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 60 treesize of output 44 [2025-03-08 05:49:46,810 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2025-03-08 05:49:46,848 INFO L134 CoverageAnalysis]: Checked inductivity of 36 backedges. 15 proven. 8 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2025-03-08 05:49:46,849 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:50:13,356 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:50:13,356 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1134905867] [2025-03-08 05:50:13,356 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:50:13,356 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2010350128] [2025-03-08 05:50:13,356 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2010350128] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:50:13,356 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-08 05:50:13,356 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17] total 17 [2025-03-08 05:50:13,356 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [47107497] [2025-03-08 05:50:13,356 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-08 05:50:13,356 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2025-03-08 05:50:13,356 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:50:13,357 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2025-03-08 05:50:13,357 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=76, Invalid=471, Unknown=5, NotChecked=0, Total=552 [2025-03-08 05:50:13,357 INFO L87 Difference]: Start difference. First operand 158 states and 194 transitions. Second operand has 17 states, 14 states have (on average 2.0) internal successors, (28), 13 states have internal predecessors, (28), 6 states have call successors, (8), 5 states have call predecessors, (8), 5 states have return successors, (7), 5 states have call predecessors, (7), 5 states have call successors, (7) [2025-03-08 05:50:17,409 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-03-08 05:50:27,404 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:50:27,404 INFO L93 Difference]: Finished difference Result 166 states and 200 transitions. [2025-03-08 05:50:27,404 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2025-03-08 05:50:27,404 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 14 states have (on average 2.0) internal successors, (28), 13 states have internal predecessors, (28), 6 states have call successors, (8), 5 states have call predecessors, (8), 5 states have return successors, (7), 5 states have call predecessors, (7), 5 states have call successors, (7) Word has length 49 [2025-03-08 05:50:27,405 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:50:27,406 INFO L225 Difference]: With dead ends: 166 [2025-03-08 05:50:27,406 INFO L226 Difference]: Without dead ends: 164 [2025-03-08 05:50:27,406 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 74 GetRequests, 40 SyntacticMatches, 3 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 185 ImplicationChecksByTransitivity, 29.6s TimeCoverageRelationStatistics Valid=165, Invalid=886, Unknown=5, NotChecked=0, Total=1056 [2025-03-08 05:50:27,407 INFO L435 NwaCegarLoop]: 20 mSDtfsCounter, 54 mSDsluCounter, 124 mSDsCounter, 0 mSdLazyCounter, 467 mSolverCounterSat, 41 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 10.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 60 SdHoareTripleChecker+Valid, 144 SdHoareTripleChecker+Invalid, 510 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 41 IncrementalHoareTripleChecker+Valid, 467 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 10.3s IncrementalHoareTripleChecker+Time [2025-03-08 05:50:27,407 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [60 Valid, 144 Invalid, 510 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [41 Valid, 467 Invalid, 2 Unknown, 0 Unchecked, 10.3s Time] [2025-03-08 05:50:27,407 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 164 states. [2025-03-08 05:50:27,428 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 164 to 162. [2025-03-08 05:50:27,428 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 162 states, 103 states have (on average 1.116504854368932) internal successors, (115), 109 states have internal predecessors, (115), 34 states have call successors, (34), 19 states have call predecessors, (34), 24 states have return successors, (48), 33 states have call predecessors, (48), 32 states have call successors, (48) [2025-03-08 05:50:27,430 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 162 states to 162 states and 197 transitions. [2025-03-08 05:50:27,430 INFO L78 Accepts]: Start accepts. Automaton has 162 states and 197 transitions. Word has length 49 [2025-03-08 05:50:27,430 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:50:27,430 INFO L471 AbstractCegarLoop]: Abstraction has 162 states and 197 transitions. [2025-03-08 05:50:27,430 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 14 states have (on average 2.0) internal successors, (28), 13 states have internal predecessors, (28), 6 states have call successors, (8), 5 states have call predecessors, (8), 5 states have return successors, (7), 5 states have call predecessors, (7), 5 states have call successors, (7) [2025-03-08 05:50:27,431 INFO L276 IsEmpty]: Start isEmpty. Operand 162 states and 197 transitions. [2025-03-08 05:50:27,433 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2025-03-08 05:50:27,433 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:50:27,433 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:50:27,441 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-08 05:50:27,634 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:50:27,634 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:50:27,635 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:50:27,635 INFO L85 PathProgramCache]: Analyzing trace with hash -1032599952, now seen corresponding path program 2 times [2025-03-08 05:50:27,635 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:50:27,635 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1661090511] [2025-03-08 05:50:27,635 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-08 05:50:27,635 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:50:27,643 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 50 statements into 2 equivalence classes. [2025-03-08 05:50:27,667 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 50 of 50 statements. [2025-03-08 05:50:27,668 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-08 05:50:27,668 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:50:27,670 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [778501049] [2025-03-08 05:50:27,670 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-08 05:50:27,670 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:50:27,670 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:50:27,672 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-08 05:50:27,673 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-08 05:50:27,738 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 50 statements into 2 equivalence classes. [2025-03-08 05:50:27,787 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 50 of 50 statements. [2025-03-08 05:50:27,787 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-08 05:50:27,787 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:50:27,791 INFO L256 TraceCheckSpWp]: Trace formula consists of 426 conjuncts, 167 conjuncts are in the unsatisfiable core [2025-03-08 05:50:27,794 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:50:27,820 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-03-08 05:50:27,844 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-03-08 05:50:27,872 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-08 05:50:27,922 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-03-08 05:50:27,973 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-08 05:50:28,025 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-08 05:50:28,079 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2025-03-08 05:50:28,134 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-08 05:50:33,033 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 35 treesize of output 21 [2025-03-08 05:50:33,056 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 21 [2025-03-08 05:50:33,103 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 13 [2025-03-08 05:50:33,162 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-08 05:50:34,683 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 25 treesize of output 17 [2025-03-08 05:50:34,707 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 21 treesize of output 13 [2025-03-08 05:50:34,730 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 9 [2025-03-08 05:50:35,491 INFO L134 CoverageAnalysis]: Checked inductivity of 41 backedges. 0 proven. 25 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2025-03-08 05:50:35,491 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:50:38,596 INFO L134 CoverageAnalysis]: Checked inductivity of 41 backedges. 8 proven. 5 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2025-03-08 05:50:38,596 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:50:38,596 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1661090511] [2025-03-08 05:50:38,596 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:50:38,596 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [778501049] [2025-03-08 05:50:38,596 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [778501049] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 05:50:38,596 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-08 05:50:38,596 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 10] total 18 [2025-03-08 05:50:38,596 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [950951808] [2025-03-08 05:50:38,596 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-08 05:50:38,597 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2025-03-08 05:50:38,597 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:50:38,597 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2025-03-08 05:50:38,597 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=46, Invalid=260, Unknown=0, NotChecked=0, Total=306 [2025-03-08 05:50:38,597 INFO L87 Difference]: Start difference. First operand 162 states and 197 transitions. Second operand has 18 states, 14 states have (on average 2.857142857142857) internal successors, (40), 13 states have internal predecessors, (40), 9 states have call successors, (16), 8 states have call predecessors, (16), 3 states have return successors, (10), 5 states have call predecessors, (10), 5 states have call successors, (10)