./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/array-cav19/array_min_and_copy_shift_sum_add.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 8fc3dc66 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/array-cav19/array_min_and_copy_shift_sum_add.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 8262fd4bdb4bed8fef0fbefd142e15775d81a64587fab0af0aa2004f91ae895c --- Real Ultimate output --- This is Ultimate 0.3.0-?-8fc3dc6-m [2025-03-16 13:51:31,877 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-16 13:51:31,935 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2025-03-16 13:51:31,941 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-16 13:51:31,941 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-16 13:51:31,964 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-16 13:51:31,965 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-16 13:51:31,965 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-16 13:51:31,965 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-16 13:51:31,965 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-16 13:51:31,966 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-03-16 13:51:31,966 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-03-16 13:51:31,966 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-16 13:51:31,966 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-16 13:51:31,967 INFO L153 SettingsManager]: * Use SBE=true [2025-03-16 13:51:31,967 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-16 13:51:31,967 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-03-16 13:51:31,967 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-16 13:51:31,967 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-16 13:51:31,967 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-16 13:51:31,967 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-16 13:51:31,967 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-03-16 13:51:31,967 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-03-16 13:51:31,967 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-03-16 13:51:31,967 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-16 13:51:31,967 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-16 13:51:31,967 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-16 13:51:31,967 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-16 13:51:31,967 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-16 13:51:31,968 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-16 13:51:31,968 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-03-16 13:51:31,968 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-03-16 13:51:31,968 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-16 13:51:31,968 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-16 13:51:31,968 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-03-16 13:51:31,968 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-03-16 13:51:31,968 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-03-16 13:51:31,968 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-16 13:51:31,968 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-03-16 13:51:31,968 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-03-16 13:51:31,968 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-03-16 13:51:31,968 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-03-16 13:51:31,968 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-03-16 13:51:31,968 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 -> 8262fd4bdb4bed8fef0fbefd142e15775d81a64587fab0af0aa2004f91ae895c [2025-03-16 13:51:32,187 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-16 13:51:32,193 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-16 13:51:32,196 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-16 13:51:32,197 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-16 13:51:32,197 INFO L274 PluginConnector]: CDTParser initialized [2025-03-16 13:51:32,198 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/array-cav19/array_min_and_copy_shift_sum_add.c [2025-03-16 13:51:33,293 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/3665501ce/9fa4c6d053d9416dabd22caf7475bcc4/FLAG28b042805 [2025-03-16 13:51:33,563 INFO L384 CDTParser]: Found 1 translation units. [2025-03-16 13:51:33,564 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/array-cav19/array_min_and_copy_shift_sum_add.c [2025-03-16 13:51:33,569 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/3665501ce/9fa4c6d053d9416dabd22caf7475bcc4/FLAG28b042805 [2025-03-16 13:51:33,582 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/3665501ce/9fa4c6d053d9416dabd22caf7475bcc4 [2025-03-16 13:51:33,585 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-16 13:51:33,586 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-16 13:51:33,589 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-16 13:51:33,589 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-16 13:51:33,593 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-16 13:51:33,594 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.03 01:51:33" (1/1) ... [2025-03-16 13:51:33,594 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@75c0eff9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:51:33, skipping insertion in model container [2025-03-16 13:51:33,595 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.03 01:51:33" (1/1) ... [2025-03-16 13:51:33,605 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-16 13:51:33,702 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/array-cav19/array_min_and_copy_shift_sum_add.c[423,436] [2025-03-16 13:51:33,714 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-16 13:51:33,719 INFO L200 MainTranslator]: Completed pre-run [2025-03-16 13:51:33,725 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/array-cav19/array_min_and_copy_shift_sum_add.c[423,436] [2025-03-16 13:51:33,730 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-16 13:51:33,738 INFO L204 MainTranslator]: Completed translation [2025-03-16 13:51:33,739 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:51:33 WrapperNode [2025-03-16 13:51:33,739 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-16 13:51:33,740 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-16 13:51:33,740 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-16 13:51:33,740 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-16 13:51:33,744 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:51:33" (1/1) ... [2025-03-16 13:51:33,748 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:51:33" (1/1) ... [2025-03-16 13:51:33,761 INFO L138 Inliner]: procedures = 15, calls = 24, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 75 [2025-03-16 13:51:33,761 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-16 13:51:33,762 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-16 13:51:33,762 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-16 13:51:33,762 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-16 13:51:33,767 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:51:33" (1/1) ... [2025-03-16 13:51:33,767 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:51:33" (1/1) ... [2025-03-16 13:51:33,768 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:51:33" (1/1) ... [2025-03-16 13:51:33,775 INFO L175 MemorySlicer]: Split 9 memory accesses to 3 slices as follows [2, 2, 5]. 56 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2, 0, 0]. The 1 writes are split as follows [0, 1, 0]. [2025-03-16 13:51:33,775 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:51:33" (1/1) ... [2025-03-16 13:51:33,775 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:51:33" (1/1) ... [2025-03-16 13:51:33,778 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:51:33" (1/1) ... [2025-03-16 13:51:33,779 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:51:33" (1/1) ... [2025-03-16 13:51:33,779 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:51:33" (1/1) ... [2025-03-16 13:51:33,780 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:51:33" (1/1) ... [2025-03-16 13:51:33,781 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-16 13:51:33,782 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-16 13:51:33,782 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-16 13:51:33,782 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-16 13:51:33,782 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:51:33" (1/1) ... [2025-03-16 13:51:33,786 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-16 13:51:33,797 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:51:33,808 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-16 13:51:33,812 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-16 13:51:33,829 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-16 13:51:33,829 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2025-03-16 13:51:33,829 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2025-03-16 13:51:33,830 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-03-16 13:51:33,830 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2025-03-16 13:51:33,830 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2025-03-16 13:51:33,830 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2025-03-16 13:51:33,830 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2025-03-16 13:51:33,830 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2025-03-16 13:51:33,830 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#2 [2025-03-16 13:51:33,830 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-16 13:51:33,830 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-16 13:51:33,830 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2025-03-16 13:51:33,831 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2025-03-16 13:51:33,831 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#2 [2025-03-16 13:51:33,831 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2025-03-16 13:51:33,890 INFO L256 CfgBuilder]: Building ICFG [2025-03-16 13:51:33,891 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-16 13:51:34,030 INFO L1322 $ProcedureCfgBuilder]: dead code at ProgramPoint L18: 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; [2025-03-16 13:51:34,040 INFO L? ?]: Removed 12 outVars from TransFormulas that were not future-live. [2025-03-16 13:51:34,040 INFO L307 CfgBuilder]: Performing block encoding [2025-03-16 13:51:34,045 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-16 13:51:34,046 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-16 13:51:34,046 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 16.03 01:51:34 BoogieIcfgContainer [2025-03-16 13:51:34,046 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-16 13:51:34,048 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-03-16 13:51:34,048 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-03-16 13:51:34,051 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-03-16 13:51:34,051 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 16.03 01:51:33" (1/3) ... [2025-03-16 13:51:34,052 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5d52bcf6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.03 01:51:34, skipping insertion in model container [2025-03-16 13:51:34,052 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:51:33" (2/3) ... [2025-03-16 13:51:34,052 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5d52bcf6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.03 01:51:34, skipping insertion in model container [2025-03-16 13:51:34,052 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 16.03 01:51:34" (3/3) ... [2025-03-16 13:51:34,053 INFO L128 eAbstractionObserver]: Analyzing ICFG array_min_and_copy_shift_sum_add.c [2025-03-16 13:51:34,063 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-03-16 13:51:34,064 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG array_min_and_copy_shift_sum_add.c that has 2 procedures, 24 locations, 1 initial locations, 3 loop locations, and 1 error locations. [2025-03-16 13:51:34,102 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-03-16 13:51:34,111 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;@185fefba, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-03-16 13:51:34,113 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-03-16 13:51:34,116 INFO L276 IsEmpty]: Start isEmpty. Operand has 24 states, 18 states have (on average 1.4444444444444444) internal successors, (26), 19 states have internal predecessors, (26), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2025-03-16 13:51:34,120 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2025-03-16 13:51:34,121 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:51:34,121 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:51:34,121 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:51:34,125 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:51:34,125 INFO L85 PathProgramCache]: Analyzing trace with hash 1613187741, now seen corresponding path program 1 times [2025-03-16 13:51:34,130 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:51:34,130 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2049231593] [2025-03-16 13:51:34,131 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 13:51:34,131 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:51:34,187 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 18 statements into 1 equivalence classes. [2025-03-16 13:51:34,199 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 18 of 18 statements. [2025-03-16 13:51:34,200 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 13:51:34,200 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:51:34,243 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-16 13:51:34,244 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:51:34,244 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2049231593] [2025-03-16 13:51:34,244 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2049231593] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:51:34,244 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1229058828] [2025-03-16 13:51:34,244 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 13:51:34,245 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:51:34,245 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:51:34,246 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-16 13:51:34,248 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-16 13:51:34,289 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 18 statements into 1 equivalence classes. [2025-03-16 13:51:34,310 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 18 of 18 statements. [2025-03-16 13:51:34,310 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 13:51:34,310 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:51:34,311 INFO L256 TraceCheckSpWp]: Trace formula consists of 83 conjuncts, 1 conjuncts are in the unsatisfiable core [2025-03-16 13:51:34,313 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:51:34,320 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-16 13:51:34,320 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-16 13:51:34,321 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1229058828] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 13:51:34,321 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-16 13:51:34,322 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [2] total 2 [2025-03-16 13:51:34,323 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1310765610] [2025-03-16 13:51:34,324 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 13:51:34,326 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2025-03-16 13:51:34,326 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:51:34,339 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2025-03-16 13:51:34,339 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-03-16 13:51:34,341 INFO L87 Difference]: Start difference. First operand has 24 states, 18 states have (on average 1.4444444444444444) internal successors, (26), 19 states have internal predecessors, (26), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Second operand has 2 states, 2 states have (on average 6.5) internal successors, (13), 2 states have internal predecessors, (13), 2 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-16 13:51:34,355 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:51:34,355 INFO L93 Difference]: Finished difference Result 46 states and 64 transitions. [2025-03-16 13:51:34,356 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2025-03-16 13:51:34,357 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 6.5) internal successors, (13), 2 states have internal predecessors, (13), 2 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Word has length 18 [2025-03-16 13:51:34,357 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:51:34,360 INFO L225 Difference]: With dead ends: 46 [2025-03-16 13:51:34,360 INFO L226 Difference]: Without dead ends: 20 [2025-03-16 13:51:34,362 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 19 GetRequests, 19 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-16 13:51:34,363 INFO L435 NwaCegarLoop]: 30 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, 30 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-16 13:51:34,364 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 30 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 13:51:34,372 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 20 states. [2025-03-16 13:51:34,380 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 20 to 20. [2025-03-16 13:51:34,381 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 20 states, 15 states have (on average 1.3333333333333333) internal successors, (20), 15 states have internal predecessors, (20), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2025-03-16 13:51:34,383 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 26 transitions. [2025-03-16 13:51:34,384 INFO L78 Accepts]: Start accepts. Automaton has 20 states and 26 transitions. Word has length 18 [2025-03-16 13:51:34,384 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:51:34,385 INFO L471 AbstractCegarLoop]: Abstraction has 20 states and 26 transitions. [2025-03-16 13:51:34,385 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 6.5) internal successors, (13), 2 states have internal predecessors, (13), 2 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-16 13:51:34,385 INFO L276 IsEmpty]: Start isEmpty. Operand 20 states and 26 transitions. [2025-03-16 13:51:34,386 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2025-03-16 13:51:34,386 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:51:34,386 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:51:34,392 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2025-03-16 13:51:34,590 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-16 13:51:34,590 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:51:34,592 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:51:34,592 INFO L85 PathProgramCache]: Analyzing trace with hash 1313285087, now seen corresponding path program 1 times [2025-03-16 13:51:34,592 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:51:34,592 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1972756329] [2025-03-16 13:51:34,592 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 13:51:34,592 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:51:34,603 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 18 statements into 1 equivalence classes. [2025-03-16 13:51:34,617 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 18 of 18 statements. [2025-03-16 13:51:34,617 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 13:51:34,618 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:51:34,763 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-16 13:51:34,763 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:51:34,763 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1972756329] [2025-03-16 13:51:34,763 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1972756329] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 13:51:34,763 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 13:51:34,763 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2025-03-16 13:51:34,763 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [401700472] [2025-03-16 13:51:34,763 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 13:51:34,765 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2025-03-16 13:51:34,765 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:51:34,766 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2025-03-16 13:51:34,766 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2025-03-16 13:51:34,766 INFO L87 Difference]: Start difference. First operand 20 states and 26 transitions. Second operand has 4 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-16 13:51:34,782 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:51:34,782 INFO L93 Difference]: Finished difference Result 24 states and 30 transitions. [2025-03-16 13:51:34,783 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2025-03-16 13:51:34,783 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 18 [2025-03-16 13:51:34,783 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:51:34,784 INFO L225 Difference]: With dead ends: 24 [2025-03-16 13:51:34,784 INFO L226 Difference]: Without dead ends: 21 [2025-03-16 13:51:34,784 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2025-03-16 13:51:34,785 INFO L435 NwaCegarLoop]: 24 mSDtfsCounter, 8 mSDsluCounter, 32 mSDsCounter, 0 mSdLazyCounter, 8 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 56 SdHoareTripleChecker+Invalid, 8 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 8 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-16 13:51:34,785 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 56 Invalid, 8 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 8 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 13:51:34,786 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 21 states. [2025-03-16 13:51:34,790 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 21 to 21. [2025-03-16 13:51:34,790 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 21 states, 16 states have (on average 1.3125) internal successors, (21), 16 states have internal predecessors, (21), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2025-03-16 13:51:34,791 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 27 transitions. [2025-03-16 13:51:34,791 INFO L78 Accepts]: Start accepts. Automaton has 21 states and 27 transitions. Word has length 18 [2025-03-16 13:51:34,791 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:51:34,791 INFO L471 AbstractCegarLoop]: Abstraction has 21 states and 27 transitions. [2025-03-16 13:51:34,791 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-16 13:51:34,791 INFO L276 IsEmpty]: Start isEmpty. Operand 21 states and 27 transitions. [2025-03-16 13:51:34,792 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2025-03-16 13:51:34,792 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:51:34,792 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:51:34,792 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2025-03-16 13:51:34,792 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:51:34,792 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:51:34,795 INFO L85 PathProgramCache]: Analyzing trace with hash 2057163786, now seen corresponding path program 1 times [2025-03-16 13:51:34,795 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:51:34,795 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1886701734] [2025-03-16 13:51:34,795 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 13:51:34,795 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:51:34,805 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 19 statements into 1 equivalence classes. [2025-03-16 13:51:34,817 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 19 of 19 statements. [2025-03-16 13:51:34,819 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 13:51:34,819 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:51:34,904 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-16 13:51:34,904 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:51:34,904 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1886701734] [2025-03-16 13:51:34,904 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1886701734] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 13:51:34,904 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 13:51:34,904 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-16 13:51:34,905 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1526913094] [2025-03-16 13:51:34,905 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 13:51:34,905 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-16 13:51:34,905 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:51:34,905 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-16 13:51:34,905 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2025-03-16 13:51:34,905 INFO L87 Difference]: Start difference. First operand 21 states and 27 transitions. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 5 states have internal predecessors, (12), 1 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2025-03-16 13:51:34,946 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:51:34,947 INFO L93 Difference]: Finished difference Result 36 states and 49 transitions. [2025-03-16 13:51:34,947 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2025-03-16 13:51:34,947 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 5 states have internal predecessors, (12), 1 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 19 [2025-03-16 13:51:34,947 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:51:34,948 INFO L225 Difference]: With dead ends: 36 [2025-03-16 13:51:34,948 INFO L226 Difference]: Without dead ends: 28 [2025-03-16 13:51:34,948 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2025-03-16 13:51:34,948 INFO L435 NwaCegarLoop]: 17 mSDtfsCounter, 6 mSDsluCounter, 27 mSDsCounter, 0 mSdLazyCounter, 31 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 44 SdHoareTripleChecker+Invalid, 39 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 31 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-16 13:51:34,948 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 44 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 31 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 13:51:34,949 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 28 states. [2025-03-16 13:51:34,952 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 28 to 23. [2025-03-16 13:51:34,952 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 23 states, 18 states have (on average 1.2777777777777777) internal successors, (23), 18 states have internal predecessors, (23), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2025-03-16 13:51:34,952 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 29 transitions. [2025-03-16 13:51:34,952 INFO L78 Accepts]: Start accepts. Automaton has 23 states and 29 transitions. Word has length 19 [2025-03-16 13:51:34,953 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:51:34,953 INFO L471 AbstractCegarLoop]: Abstraction has 23 states and 29 transitions. [2025-03-16 13:51:34,953 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 5 states have internal predecessors, (12), 1 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2025-03-16 13:51:34,953 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 29 transitions. [2025-03-16 13:51:34,953 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2025-03-16 13:51:34,953 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:51:34,953 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:51:34,954 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2025-03-16 13:51:34,954 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:51:34,954 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:51:34,954 INFO L85 PathProgramCache]: Analyzing trace with hash 148978505, now seen corresponding path program 1 times [2025-03-16 13:51:34,954 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:51:34,954 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1782216601] [2025-03-16 13:51:34,954 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 13:51:34,954 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:51:34,961 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 30 statements into 1 equivalence classes. [2025-03-16 13:51:34,987 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 30 of 30 statements. [2025-03-16 13:51:34,987 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 13:51:34,987 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:51:35,492 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2025-03-16 13:51:35,492 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:51:35,492 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1782216601] [2025-03-16 13:51:35,492 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1782216601] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:51:35,492 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2080902765] [2025-03-16 13:51:35,492 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 13:51:35,492 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:51:35,492 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:51:35,495 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-16 13:51:35,497 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-16 13:51:35,530 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 30 statements into 1 equivalence classes. [2025-03-16 13:51:35,551 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 30 of 30 statements. [2025-03-16 13:51:35,551 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 13:51:35,551 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:51:35,555 INFO L256 TraceCheckSpWp]: Trace formula consists of 121 conjuncts, 19 conjuncts are in the unsatisfiable core [2025-03-16 13:51:35,558 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:51:35,739 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-16 13:51:35,776 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-16 13:51:35,788 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2025-03-16 13:51:35,788 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:51:35,839 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 27 [2025-03-16 13:51:35,843 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 32 treesize of output 30 [2025-03-16 13:51:35,887 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:51:35,887 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 18 treesize of output 15 [2025-03-16 13:51:35,949 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2025-03-16 13:51:35,950 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2080902765] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 13:51:35,950 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 13:51:35,953 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 9, 9] total 21 [2025-03-16 13:51:35,954 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1442089007] [2025-03-16 13:51:35,954 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 13:51:35,954 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2025-03-16 13:51:35,954 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:51:35,954 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2025-03-16 13:51:35,955 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=90, Invalid=330, Unknown=0, NotChecked=0, Total=420 [2025-03-16 13:51:35,955 INFO L87 Difference]: Start difference. First operand 23 states and 29 transitions. Second operand has 21 states, 21 states have (on average 1.9523809523809523) internal successors, (41), 21 states have internal predecessors, (41), 6 states have call successors, (6), 1 states have call predecessors, (6), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2025-03-16 13:51:36,141 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:51:36,141 INFO L93 Difference]: Finished difference Result 42 states and 56 transitions. [2025-03-16 13:51:36,142 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2025-03-16 13:51:36,142 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 21 states have (on average 1.9523809523809523) internal successors, (41), 21 states have internal predecessors, (41), 6 states have call successors, (6), 1 states have call predecessors, (6), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Word has length 30 [2025-03-16 13:51:36,142 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:51:36,142 INFO L225 Difference]: With dead ends: 42 [2025-03-16 13:51:36,143 INFO L226 Difference]: Without dead ends: 39 [2025-03-16 13:51:36,144 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 74 GetRequests, 48 SyntacticMatches, 3 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 241 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=138, Invalid=462, Unknown=0, NotChecked=0, Total=600 [2025-03-16 13:51:36,145 INFO L435 NwaCegarLoop]: 21 mSDtfsCounter, 56 mSDsluCounter, 98 mSDsCounter, 0 mSdLazyCounter, 187 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 58 SdHoareTripleChecker+Valid, 119 SdHoareTripleChecker+Invalid, 195 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 187 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 13:51:36,145 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [58 Valid, 119 Invalid, 195 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 187 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 13:51:36,146 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2025-03-16 13:51:36,152 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 36. [2025-03-16 13:51:36,152 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 36 states, 29 states have (on average 1.3793103448275863) internal successors, (40), 29 states have internal predecessors, (40), 5 states have call successors, (5), 1 states have call predecessors, (5), 1 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2025-03-16 13:51:36,153 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 50 transitions. [2025-03-16 13:51:36,153 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 50 transitions. Word has length 30 [2025-03-16 13:51:36,153 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:51:36,153 INFO L471 AbstractCegarLoop]: Abstraction has 36 states and 50 transitions. [2025-03-16 13:51:36,153 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 21 states have (on average 1.9523809523809523) internal successors, (41), 21 states have internal predecessors, (41), 6 states have call successors, (6), 1 states have call predecessors, (6), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2025-03-16 13:51:36,153 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 50 transitions. [2025-03-16 13:51:36,154 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2025-03-16 13:51:36,154 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:51:36,154 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:51:36,160 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2025-03-16 13:51:36,354 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,SelfDestructingSolverStorable3 [2025-03-16 13:51:36,355 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:51:36,355 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:51:36,355 INFO L85 PathProgramCache]: Analyzing trace with hash -1658475958, now seen corresponding path program 1 times [2025-03-16 13:51:36,355 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:51:36,356 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2095647942] [2025-03-16 13:51:36,356 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 13:51:36,356 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:51:36,363 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 30 statements into 1 equivalence classes. [2025-03-16 13:51:36,376 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 30 of 30 statements. [2025-03-16 13:51:36,376 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 13:51:36,376 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:51:36,727 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2025-03-16 13:51:36,728 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:51:36,728 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2095647942] [2025-03-16 13:51:36,728 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2095647942] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:51:36,730 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [364934473] [2025-03-16 13:51:36,730 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 13:51:36,730 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:51:36,730 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:51:36,735 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-16 13:51:36,736 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-16 13:51:36,768 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 30 statements into 1 equivalence classes. [2025-03-16 13:51:36,782 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 30 of 30 statements. [2025-03-16 13:51:36,782 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 13:51:36,782 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:51:36,782 INFO L256 TraceCheckSpWp]: Trace formula consists of 117 conjuncts, 19 conjuncts are in the unsatisfiable core [2025-03-16 13:51:36,784 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:51:36,911 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-16 13:51:36,941 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-16 13:51:36,958 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2025-03-16 13:51:36,958 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:51:36,993 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 27 [2025-03-16 13:51:36,996 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 32 treesize of output 30 [2025-03-16 13:51:37,049 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:51:37,049 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 18 treesize of output 15 [2025-03-16 13:51:37,104 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2025-03-16 13:51:37,104 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [364934473] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 13:51:37,104 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 13:51:37,105 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 10, 10] total 24 [2025-03-16 13:51:37,105 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1783795561] [2025-03-16 13:51:37,105 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 13:51:37,105 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2025-03-16 13:51:37,105 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:51:37,106 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2025-03-16 13:51:37,106 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=105, Invalid=447, Unknown=0, NotChecked=0, Total=552 [2025-03-16 13:51:37,106 INFO L87 Difference]: Start difference. First operand 36 states and 50 transitions. Second operand has 24 states, 24 states have (on average 1.7083333333333333) internal successors, (41), 24 states have internal predecessors, (41), 6 states have call successors, (6), 1 states have call predecessors, (6), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2025-03-16 13:51:37,308 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:51:37,309 INFO L93 Difference]: Finished difference Result 52 states and 71 transitions. [2025-03-16 13:51:37,309 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2025-03-16 13:51:37,309 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 24 states have (on average 1.7083333333333333) internal successors, (41), 24 states have internal predecessors, (41), 6 states have call successors, (6), 1 states have call predecessors, (6), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Word has length 30 [2025-03-16 13:51:37,309 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:51:37,311 INFO L225 Difference]: With dead ends: 52 [2025-03-16 13:51:37,311 INFO L226 Difference]: Without dead ends: 49 [2025-03-16 13:51:37,312 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 75 GetRequests, 46 SyntacticMatches, 3 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 323 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=154, Invalid=602, Unknown=0, NotChecked=0, Total=756 [2025-03-16 13:51:37,312 INFO L435 NwaCegarLoop]: 20 mSDtfsCounter, 35 mSDsluCounter, 153 mSDsCounter, 0 mSdLazyCounter, 250 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 37 SdHoareTripleChecker+Valid, 173 SdHoareTripleChecker+Invalid, 264 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 250 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 13:51:37,312 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [37 Valid, 173 Invalid, 264 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 250 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 13:51:37,313 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2025-03-16 13:51:37,319 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 36. [2025-03-16 13:51:37,320 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 36 states, 29 states have (on average 1.3793103448275863) internal successors, (40), 29 states have internal predecessors, (40), 5 states have call successors, (5), 1 states have call predecessors, (5), 1 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2025-03-16 13:51:37,320 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 50 transitions. [2025-03-16 13:51:37,321 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 50 transitions. Word has length 30 [2025-03-16 13:51:37,321 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:51:37,321 INFO L471 AbstractCegarLoop]: Abstraction has 36 states and 50 transitions. [2025-03-16 13:51:37,322 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 24 states have (on average 1.7083333333333333) internal successors, (41), 24 states have internal predecessors, (41), 6 states have call successors, (6), 1 states have call predecessors, (6), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2025-03-16 13:51:37,322 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 50 transitions. [2025-03-16 13:51:37,322 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2025-03-16 13:51:37,322 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:51:37,322 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:51:37,328 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2025-03-16 13:51:37,523 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:51:37,523 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:51:37,523 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:51:37,524 INFO L85 PathProgramCache]: Analyzing trace with hash 323398112, now seen corresponding path program 2 times [2025-03-16 13:51:37,524 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:51:37,524 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1351865688] [2025-03-16 13:51:37,524 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 13:51:37,524 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:51:37,537 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 31 statements into 2 equivalence classes. [2025-03-16 13:51:37,542 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 31 of 31 statements. [2025-03-16 13:51:37,542 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 13:51:37,543 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:51:37,587 INFO L134 CoverageAnalysis]: Checked inductivity of 17 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2025-03-16 13:51:37,587 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:51:37,587 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1351865688] [2025-03-16 13:51:37,587 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1351865688] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:51:37,587 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1910477476] [2025-03-16 13:51:37,588 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 13:51:37,588 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:51:37,588 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:51:37,590 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-16 13:51:37,592 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-16 13:51:37,622 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 31 statements into 2 equivalence classes. [2025-03-16 13:51:37,636 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 31 of 31 statements. [2025-03-16 13:51:37,636 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 13:51:37,636 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:51:37,637 INFO L256 TraceCheckSpWp]: Trace formula consists of 126 conjuncts, 6 conjuncts are in the unsatisfiable core [2025-03-16 13:51:37,638 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:51:37,685 INFO L134 CoverageAnalysis]: Checked inductivity of 17 backedges. 3 proven. 1 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2025-03-16 13:51:37,686 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:51:37,726 INFO L134 CoverageAnalysis]: Checked inductivity of 17 backedges. 3 proven. 1 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2025-03-16 13:51:37,726 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1910477476] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 13:51:37,726 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 13:51:37,726 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 10 [2025-03-16 13:51:37,726 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [304482738] [2025-03-16 13:51:37,726 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 13:51:37,726 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2025-03-16 13:51:37,726 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:51:37,727 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2025-03-16 13:51:37,727 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=60, Unknown=0, NotChecked=0, Total=90 [2025-03-16 13:51:37,727 INFO L87 Difference]: Start difference. First operand 36 states and 50 transitions. Second operand has 10 states, 10 states have (on average 2.4) internal successors, (24), 10 states have internal predecessors, (24), 2 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-16 13:51:37,791 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:51:37,792 INFO L93 Difference]: Finished difference Result 61 states and 85 transitions. [2025-03-16 13:51:37,792 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-16 13:51:37,792 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.4) internal successors, (24), 10 states have internal predecessors, (24), 2 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 31 [2025-03-16 13:51:37,792 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:51:37,793 INFO L225 Difference]: With dead ends: 61 [2025-03-16 13:51:37,793 INFO L226 Difference]: Without dead ends: 50 [2025-03-16 13:51:37,793 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 68 GetRequests, 56 SyntacticMatches, 3 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 25 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=38, Invalid=72, Unknown=0, NotChecked=0, Total=110 [2025-03-16 13:51:37,793 INFO L435 NwaCegarLoop]: 16 mSDtfsCounter, 10 mSDsluCounter, 65 mSDsCounter, 0 mSdLazyCounter, 84 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 81 SdHoareTripleChecker+Invalid, 100 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 84 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 13:51:37,794 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 81 Invalid, 100 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 84 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 13:51:37,795 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2025-03-16 13:51:37,800 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 42. [2025-03-16 13:51:37,801 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 42 states, 35 states have (on average 1.3428571428571427) internal successors, (47), 35 states have internal predecessors, (47), 5 states have call successors, (5), 1 states have call predecessors, (5), 1 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2025-03-16 13:51:37,802 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 42 states to 42 states and 57 transitions. [2025-03-16 13:51:37,802 INFO L78 Accepts]: Start accepts. Automaton has 42 states and 57 transitions. Word has length 31 [2025-03-16 13:51:37,803 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:51:37,803 INFO L471 AbstractCegarLoop]: Abstraction has 42 states and 57 transitions. [2025-03-16 13:51:37,803 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.4) internal successors, (24), 10 states have internal predecessors, (24), 2 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-16 13:51:37,803 INFO L276 IsEmpty]: Start isEmpty. Operand 42 states and 57 transitions. [2025-03-16 13:51:37,804 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2025-03-16 13:51:37,804 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:51:37,804 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:51:37,811 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-16 13:51:38,005 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:51:38,005 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:51:38,005 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:51:38,005 INFO L85 PathProgramCache]: Analyzing trace with hash -38240077, now seen corresponding path program 3 times [2025-03-16 13:51:38,005 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:51:38,006 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [553544895] [2025-03-16 13:51:38,006 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 13:51:38,006 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:51:38,013 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 40 statements into 4 equivalence classes. [2025-03-16 13:51:38,031 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) and asserted 34 of 40 statements. [2025-03-16 13:51:38,031 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2025-03-16 13:51:38,031 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:51:38,079 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 1 proven. 8 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2025-03-16 13:51:38,079 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:51:38,079 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [553544895] [2025-03-16 13:51:38,079 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [553544895] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:51:38,079 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1577406060] [2025-03-16 13:51:38,080 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 13:51:38,080 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:51:38,080 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:51:38,081 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-16 13:51:38,083 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-16 13:51:38,116 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 40 statements into 4 equivalence classes. [2025-03-16 13:51:38,131 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) and asserted 34 of 40 statements. [2025-03-16 13:51:38,131 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2025-03-16 13:51:38,131 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:51:38,132 INFO L256 TraceCheckSpWp]: Trace formula consists of 134 conjuncts, 6 conjuncts are in the unsatisfiable core [2025-03-16 13:51:38,133 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:51:38,174 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 1 proven. 8 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2025-03-16 13:51:38,174 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:51:38,220 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 1 proven. 8 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2025-03-16 13:51:38,220 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1577406060] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 13:51:38,221 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 13:51:38,221 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 10 [2025-03-16 13:51:38,221 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [580881794] [2025-03-16 13:51:38,221 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 13:51:38,222 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2025-03-16 13:51:38,222 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:51:38,222 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2025-03-16 13:51:38,222 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=31, Invalid=59, Unknown=0, NotChecked=0, Total=90 [2025-03-16 13:51:38,223 INFO L87 Difference]: Start difference. First operand 42 states and 57 transitions. Second operand has 10 states, 10 states have (on average 2.8) internal successors, (28), 10 states have internal predecessors, (28), 3 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2025-03-16 13:51:38,314 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:51:38,314 INFO L93 Difference]: Finished difference Result 47 states and 62 transitions. [2025-03-16 13:51:38,315 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-03-16 13:51:38,315 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.8) internal successors, (28), 10 states have internal predecessors, (28), 3 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) Word has length 40 [2025-03-16 13:51:38,315 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:51:38,315 INFO L225 Difference]: With dead ends: 47 [2025-03-16 13:51:38,316 INFO L226 Difference]: Without dead ends: 42 [2025-03-16 13:51:38,316 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 89 GetRequests, 73 SyntacticMatches, 4 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 33 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=59, Invalid=123, Unknown=0, NotChecked=0, Total=182 [2025-03-16 13:51:38,317 INFO L435 NwaCegarLoop]: 20 mSDtfsCounter, 19 mSDsluCounter, 95 mSDsCounter, 0 mSdLazyCounter, 109 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 115 SdHoareTripleChecker+Invalid, 121 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 109 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 13:51:38,317 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 115 Invalid, 121 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 109 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 13:51:38,317 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states. [2025-03-16 13:51:38,322 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 31. [2025-03-16 13:51:38,323 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 31 states, 25 states have (on average 1.28) internal successors, (32), 25 states have internal predecessors, (32), 4 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2025-03-16 13:51:38,323 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 40 transitions. [2025-03-16 13:51:38,324 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 40 transitions. Word has length 40 [2025-03-16 13:51:38,325 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:51:38,325 INFO L471 AbstractCegarLoop]: Abstraction has 31 states and 40 transitions. [2025-03-16 13:51:38,325 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.8) internal successors, (28), 10 states have internal predecessors, (28), 3 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2025-03-16 13:51:38,325 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 40 transitions. [2025-03-16 13:51:38,325 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2025-03-16 13:51:38,325 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:51:38,325 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:51:38,332 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-16 13:51:38,526 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:51:38,526 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:51:38,526 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:51:38,527 INFO L85 PathProgramCache]: Analyzing trace with hash -1471826701, now seen corresponding path program 4 times [2025-03-16 13:51:38,527 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:51:38,527 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [210727722] [2025-03-16 13:51:38,527 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-16 13:51:38,527 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:51:38,535 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 42 statements into 2 equivalence classes. [2025-03-16 13:51:38,563 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 42 of 42 statements. [2025-03-16 13:51:38,564 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-03-16 13:51:38,564 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:51:39,148 INFO L134 CoverageAnalysis]: Checked inductivity of 38 backedges. 0 proven. 14 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-03-16 13:51:39,148 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:51:39,148 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [210727722] [2025-03-16 13:51:39,149 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [210727722] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:51:39,149 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [457175772] [2025-03-16 13:51:39,149 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-16 13:51:39,149 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:51:39,149 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:51:39,151 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-16 13:51:39,152 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-16 13:51:39,191 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 42 statements into 2 equivalence classes. [2025-03-16 13:51:39,212 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 42 of 42 statements. [2025-03-16 13:51:39,212 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-03-16 13:51:39,212 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:51:39,213 INFO L256 TraceCheckSpWp]: Trace formula consists of 159 conjuncts, 40 conjuncts are in the unsatisfiable core [2025-03-16 13:51:39,216 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:51:39,502 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 19 treesize of output 13 [2025-03-16 13:51:39,571 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:51:39,571 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 59 treesize of output 35 [2025-03-16 13:51:39,576 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 17 [2025-03-16 13:51:39,676 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:51:39,677 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 35 treesize of output 15 [2025-03-16 13:51:39,698 INFO L134 CoverageAnalysis]: Checked inductivity of 38 backedges. 6 proven. 17 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2025-03-16 13:51:39,698 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:51:39,812 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 97 treesize of output 93 [2025-03-16 13:51:39,822 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:51:39,822 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 1020 treesize of output 972 [2025-03-16 13:51:40,030 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:51:40,030 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 51 treesize of output 49 [2025-03-16 13:51:40,136 INFO L134 CoverageAnalysis]: Checked inductivity of 38 backedges. 2 proven. 12 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-03-16 13:51:40,136 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [457175772] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 13:51:40,136 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 13:51:40,136 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 17, 15] total 41 [2025-03-16 13:51:40,136 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1289292138] [2025-03-16 13:51:40,137 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 13:51:40,137 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 41 states [2025-03-16 13:51:40,137 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:51:40,137 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 41 interpolants. [2025-03-16 13:51:40,138 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=213, Invalid=1427, Unknown=0, NotChecked=0, Total=1640 [2025-03-16 13:51:40,138 INFO L87 Difference]: Start difference. First operand 31 states and 40 transitions. Second operand has 41 states, 41 states have (on average 1.6097560975609757) internal successors, (66), 41 states have internal predecessors, (66), 9 states have call successors, (9), 1 states have call predecessors, (9), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2025-03-16 13:51:41,231 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:51:41,231 INFO L93 Difference]: Finished difference Result 74 states and 101 transitions. [2025-03-16 13:51:41,231 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 40 states. [2025-03-16 13:51:41,231 INFO L78 Accepts]: Start accepts. Automaton has has 41 states, 41 states have (on average 1.6097560975609757) internal successors, (66), 41 states have internal predecessors, (66), 9 states have call successors, (9), 1 states have call predecessors, (9), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Word has length 42 [2025-03-16 13:51:41,232 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:51:41,232 INFO L225 Difference]: With dead ends: 74 [2025-03-16 13:51:41,232 INFO L226 Difference]: Without dead ends: 71 [2025-03-16 13:51:41,234 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 125 GetRequests, 59 SyntacticMatches, 1 SemanticMatches, 65 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1214 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=644, Invalid=3778, Unknown=0, NotChecked=0, Total=4422 [2025-03-16 13:51:41,234 INFO L435 NwaCegarLoop]: 15 mSDtfsCounter, 111 mSDsluCounter, 213 mSDsCounter, 0 mSdLazyCounter, 782 mSolverCounterSat, 61 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 112 SdHoareTripleChecker+Valid, 228 SdHoareTripleChecker+Invalid, 843 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 61 IncrementalHoareTripleChecker+Valid, 782 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2025-03-16 13:51:41,234 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [112 Valid, 228 Invalid, 843 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [61 Valid, 782 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2025-03-16 13:51:41,235 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 71 states. [2025-03-16 13:51:41,241 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 71 to 47. [2025-03-16 13:51:41,241 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 47 states, 39 states have (on average 1.3846153846153846) internal successors, (54), 39 states have internal predecessors, (54), 6 states have call successors, (6), 1 states have call predecessors, (6), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2025-03-16 13:51:41,241 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 66 transitions. [2025-03-16 13:51:41,241 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 66 transitions. Word has length 42 [2025-03-16 13:51:41,241 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:51:41,241 INFO L471 AbstractCegarLoop]: Abstraction has 47 states and 66 transitions. [2025-03-16 13:51:41,242 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 41 states, 41 states have (on average 1.6097560975609757) internal successors, (66), 41 states have internal predecessors, (66), 9 states have call successors, (9), 1 states have call predecessors, (9), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2025-03-16 13:51:41,242 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 66 transitions. [2025-03-16 13:51:41,242 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2025-03-16 13:51:41,242 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:51:41,242 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:51:41,248 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-16 13:51:41,442 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:51:41,443 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:51:41,444 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:51:41,444 INFO L85 PathProgramCache]: Analyzing trace with hash 1618044278, now seen corresponding path program 5 times [2025-03-16 13:51:41,444 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:51:41,444 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [863492322] [2025-03-16 13:51:41,444 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-03-16 13:51:41,444 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:51:41,450 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 43 statements into 4 equivalence classes. [2025-03-16 13:51:41,464 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) and asserted 43 of 43 statements. [2025-03-16 13:51:41,464 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2025-03-16 13:51:41,464 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:51:41,526 INFO L134 CoverageAnalysis]: Checked inductivity of 41 backedges. 6 proven. 8 refuted. 0 times theorem prover too weak. 27 trivial. 0 not checked. [2025-03-16 13:51:41,526 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:51:41,526 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [863492322] [2025-03-16 13:51:41,526 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [863492322] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:51:41,526 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [397206077] [2025-03-16 13:51:41,526 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-03-16 13:51:41,526 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:51:41,526 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:51:41,528 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-16 13:51:41,529 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-16 13:51:41,563 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 43 statements into 4 equivalence classes. [2025-03-16 13:51:41,583 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) and asserted 43 of 43 statements. [2025-03-16 13:51:41,583 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2025-03-16 13:51:41,583 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:51:41,584 INFO L256 TraceCheckSpWp]: Trace formula consists of 164 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-03-16 13:51:41,585 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:51:41,642 INFO L134 CoverageAnalysis]: Checked inductivity of 41 backedges. 6 proven. 8 refuted. 0 times theorem prover too weak. 27 trivial. 0 not checked. [2025-03-16 13:51:41,642 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:51:41,709 INFO L134 CoverageAnalysis]: Checked inductivity of 41 backedges. 6 proven. 8 refuted. 0 times theorem prover too weak. 27 trivial. 0 not checked. [2025-03-16 13:51:41,709 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [397206077] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 13:51:41,710 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 13:51:41,710 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9] total 13 [2025-03-16 13:51:41,710 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [793620806] [2025-03-16 13:51:41,710 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 13:51:41,710 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2025-03-16 13:51:41,710 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:51:41,710 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2025-03-16 13:51:41,710 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=44, Invalid=112, Unknown=0, NotChecked=0, Total=156 [2025-03-16 13:51:41,711 INFO L87 Difference]: Start difference. First operand 47 states and 66 transitions. Second operand has 13 states, 13 states have (on average 2.6923076923076925) internal successors, (35), 13 states have internal predecessors, (35), 4 states have call successors, (5), 1 states have call predecessors, (5), 1 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) [2025-03-16 13:51:41,790 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:51:41,790 INFO L93 Difference]: Finished difference Result 84 states and 118 transitions. [2025-03-16 13:51:41,790 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2025-03-16 13:51:41,790 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 2.6923076923076925) internal successors, (35), 13 states have internal predecessors, (35), 4 states have call successors, (5), 1 states have call predecessors, (5), 1 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) Word has length 43 [2025-03-16 13:51:41,791 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:51:41,791 INFO L225 Difference]: With dead ends: 84 [2025-03-16 13:51:41,791 INFO L226 Difference]: Without dead ends: 65 [2025-03-16 13:51:41,791 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 96 GetRequests, 76 SyntacticMatches, 6 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 73 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=72, Invalid=168, Unknown=0, NotChecked=0, Total=240 [2025-03-16 13:51:41,792 INFO L435 NwaCegarLoop]: 16 mSDtfsCounter, 16 mSDsluCounter, 43 mSDsCounter, 0 mSdLazyCounter, 74 mSolverCounterSat, 38 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 59 SdHoareTripleChecker+Invalid, 112 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 38 IncrementalHoareTripleChecker+Valid, 74 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 13:51:41,792 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 59 Invalid, 112 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [38 Valid, 74 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 13:51:41,792 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 65 states. [2025-03-16 13:51:41,798 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 65 to 52. [2025-03-16 13:51:41,799 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 52 states, 44 states have (on average 1.3181818181818181) internal successors, (58), 44 states have internal predecessors, (58), 6 states have call successors, (6), 1 states have call predecessors, (6), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2025-03-16 13:51:41,799 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52 states to 52 states and 70 transitions. [2025-03-16 13:51:41,799 INFO L78 Accepts]: Start accepts. Automaton has 52 states and 70 transitions. Word has length 43 [2025-03-16 13:51:41,799 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:51:41,799 INFO L471 AbstractCegarLoop]: Abstraction has 52 states and 70 transitions. [2025-03-16 13:51:41,800 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 2.6923076923076925) internal successors, (35), 13 states have internal predecessors, (35), 4 states have call successors, (5), 1 states have call predecessors, (5), 1 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) [2025-03-16 13:51:41,800 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 70 transitions. [2025-03-16 13:51:41,800 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 54 [2025-03-16 13:51:41,800 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:51:41,800 INFO L218 NwaCegarLoop]: trace histogram [5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:51:41,806 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-16 13:51:42,005 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:51:42,005 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:51:42,006 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:51:42,006 INFO L85 PathProgramCache]: Analyzing trace with hash -993865684, now seen corresponding path program 6 times [2025-03-16 13:51:42,006 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:51:42,006 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1783739590] [2025-03-16 13:51:42,006 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-03-16 13:51:42,006 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:51:42,012 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 53 statements into 5 equivalence classes. [2025-03-16 13:51:42,035 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 5 check-sat command(s) and asserted 53 of 53 statements. [2025-03-16 13:51:42,035 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 5 check-sat command(s) [2025-03-16 13:51:42,035 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:51:42,116 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 1 proven. 23 refuted. 0 times theorem prover too weak. 46 trivial. 0 not checked. [2025-03-16 13:51:42,117 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:51:42,117 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1783739590] [2025-03-16 13:51:42,117 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1783739590] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:51:42,117 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [290360541] [2025-03-16 13:51:42,117 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-03-16 13:51:42,117 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:51:42,117 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:51:42,119 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-16 13:51:42,121 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-16 13:51:42,157 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 53 statements into 5 equivalence classes. [2025-03-16 13:51:42,178 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 5 check-sat command(s) and asserted 53 of 53 statements. [2025-03-16 13:51:42,178 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 5 check-sat command(s) [2025-03-16 13:51:42,178 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:51:42,179 INFO L256 TraceCheckSpWp]: Trace formula consists of 192 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-03-16 13:51:42,180 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:51:42,242 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 8 proven. 16 refuted. 0 times theorem prover too weak. 46 trivial. 0 not checked. [2025-03-16 13:51:42,243 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:51:42,316 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 8 proven. 16 refuted. 0 times theorem prover too weak. 46 trivial. 0 not checked. [2025-03-16 13:51:42,317 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [290360541] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 13:51:42,317 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 13:51:42,317 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9] total 14 [2025-03-16 13:51:42,317 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [409366077] [2025-03-16 13:51:42,317 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 13:51:42,317 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2025-03-16 13:51:42,317 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:51:42,318 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2025-03-16 13:51:42,319 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=53, Invalid=129, Unknown=0, NotChecked=0, Total=182 [2025-03-16 13:51:42,319 INFO L87 Difference]: Start difference. First operand 52 states and 70 transitions. Second operand has 14 states, 14 states have (on average 2.9285714285714284) internal successors, (41), 14 states have internal predecessors, (41), 5 states have call successors, (6), 1 states have call predecessors, (6), 1 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) [2025-03-16 13:51:42,470 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:51:42,470 INFO L93 Difference]: Finished difference Result 58 states and 76 transitions. [2025-03-16 13:51:42,470 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2025-03-16 13:51:42,470 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 2.9285714285714284) internal successors, (41), 14 states have internal predecessors, (41), 5 states have call successors, (6), 1 states have call predecessors, (6), 1 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) Word has length 53 [2025-03-16 13:51:42,470 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:51:42,471 INFO L225 Difference]: With dead ends: 58 [2025-03-16 13:51:42,471 INFO L226 Difference]: Without dead ends: 55 [2025-03-16 13:51:42,471 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 119 GetRequests, 95 SyntacticMatches, 6 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 113 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=100, Invalid=280, Unknown=0, NotChecked=0, Total=380 [2025-03-16 13:51:42,471 INFO L435 NwaCegarLoop]: 24 mSDtfsCounter, 28 mSDsluCounter, 105 mSDsCounter, 0 mSdLazyCounter, 186 mSolverCounterSat, 31 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 28 SdHoareTripleChecker+Valid, 129 SdHoareTripleChecker+Invalid, 217 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 31 IncrementalHoareTripleChecker+Valid, 186 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 13:51:42,472 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [28 Valid, 129 Invalid, 217 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [31 Valid, 186 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 13:51:42,472 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2025-03-16 13:51:42,479 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 39. [2025-03-16 13:51:42,479 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 39 states, 32 states have (on average 1.28125) internal successors, (41), 32 states have internal predecessors, (41), 5 states have call successors, (5), 1 states have call predecessors, (5), 1 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2025-03-16 13:51:42,481 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 51 transitions. [2025-03-16 13:51:42,481 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 51 transitions. Word has length 53 [2025-03-16 13:51:42,482 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:51:42,482 INFO L471 AbstractCegarLoop]: Abstraction has 39 states and 51 transitions. [2025-03-16 13:51:42,482 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 2.9285714285714284) internal successors, (41), 14 states have internal predecessors, (41), 5 states have call successors, (6), 1 states have call predecessors, (6), 1 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) [2025-03-16 13:51:42,482 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 51 transitions. [2025-03-16 13:51:42,483 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2025-03-16 13:51:42,483 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:51:42,483 INFO L218 NwaCegarLoop]: trace histogram [5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:51:42,489 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2025-03-16 13:51:42,687 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2025-03-16 13:51:42,687 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:51:42,687 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:51:42,687 INFO L85 PathProgramCache]: Analyzing trace with hash -745033379, now seen corresponding path program 7 times [2025-03-16 13:51:42,687 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:51:42,688 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [296874527] [2025-03-16 13:51:42,688 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-03-16 13:51:42,688 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:51:42,694 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 54 statements into 1 equivalence classes. [2025-03-16 13:51:42,705 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 54 of 54 statements. [2025-03-16 13:51:42,706 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 13:51:42,706 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:51:43,830 INFO L134 CoverageAnalysis]: Checked inductivity of 73 backedges. 0 proven. 33 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2025-03-16 13:51:43,830 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:51:43,830 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [296874527] [2025-03-16 13:51:43,830 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [296874527] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:51:43,830 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [609023064] [2025-03-16 13:51:43,830 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-03-16 13:51:43,830 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:51:43,830 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:51:43,832 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 13:51:43,833 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2025-03-16 13:51:43,873 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 54 statements into 1 equivalence classes. [2025-03-16 13:51:43,890 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 54 of 54 statements. [2025-03-16 13:51:43,890 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 13:51:43,891 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:51:43,892 INFO L256 TraceCheckSpWp]: Trace formula consists of 197 conjuncts, 45 conjuncts are in the unsatisfiable core [2025-03-16 13:51:43,896 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:51:44,352 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 19 treesize of output 13 [2025-03-16 13:51:44,419 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 30 [2025-03-16 13:51:44,481 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:51:44,482 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 3 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 95 treesize of output 55 [2025-03-16 13:51:44,488 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 42 treesize of output 29 [2025-03-16 13:51:44,634 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:51:44,634 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 3 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 53 treesize of output 21 [2025-03-16 13:51:44,668 INFO L134 CoverageAnalysis]: Checked inductivity of 73 backedges. 16 proven. 33 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-03-16 13:51:44,668 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:51:44,869 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 207 treesize of output 201 [2025-03-16 13:51:44,889 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:51:44,890 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 77130 treesize of output 74570 [2025-03-16 13:51:45,298 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:51:45,298 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 6 select indices, 6 select index equivalence classes, 0 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 15 case distinctions, treesize of input 81 treesize of output 99 [2025-03-16 13:51:45,622 INFO L134 CoverageAnalysis]: Checked inductivity of 73 backedges. 10 proven. 23 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2025-03-16 13:51:45,622 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [609023064] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 13:51:45,622 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 13:51:45,622 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [23, 21, 20] total 57 [2025-03-16 13:51:45,622 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1990463755] [2025-03-16 13:51:45,622 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 13:51:45,622 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 57 states [2025-03-16 13:51:45,622 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:51:45,623 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 57 interpolants. [2025-03-16 13:51:45,624 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=327, Invalid=2865, Unknown=0, NotChecked=0, Total=3192 [2025-03-16 13:51:45,624 INFO L87 Difference]: Start difference. First operand 39 states and 51 transitions. Second operand has 57 states, 57 states have (on average 1.543859649122807) internal successors, (88), 57 states have internal predecessors, (88), 13 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2025-03-16 13:51:47,911 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:51:47,911 INFO L93 Difference]: Finished difference Result 125 states and 164 transitions. [2025-03-16 13:51:47,911 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 53 states. [2025-03-16 13:51:47,912 INFO L78 Accepts]: Start accepts. Automaton has has 57 states, 57 states have (on average 1.543859649122807) internal successors, (88), 57 states have internal predecessors, (88), 13 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) Word has length 54 [2025-03-16 13:51:47,912 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:51:47,913 INFO L225 Difference]: With dead ends: 125 [2025-03-16 13:51:47,913 INFO L226 Difference]: Without dead ends: 122 [2025-03-16 13:51:47,914 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 176 GetRequests, 72 SyntacticMatches, 3 SemanticMatches, 101 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3278 ImplicationChecksByTransitivity, 2.8s TimeCoverageRelationStatistics Valid=1242, Invalid=9264, Unknown=0, NotChecked=0, Total=10506 [2025-03-16 13:51:47,915 INFO L435 NwaCegarLoop]: 26 mSDtfsCounter, 137 mSDsluCounter, 500 mSDsCounter, 0 mSdLazyCounter, 1429 mSolverCounterSat, 91 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 138 SdHoareTripleChecker+Valid, 526 SdHoareTripleChecker+Invalid, 1520 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 91 IncrementalHoareTripleChecker+Valid, 1429 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2025-03-16 13:51:47,915 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [138 Valid, 526 Invalid, 1520 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [91 Valid, 1429 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2025-03-16 13:51:47,915 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 122 states. [2025-03-16 13:51:47,930 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 122 to 84. [2025-03-16 13:51:47,930 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 84 states, 71 states have (on average 1.3661971830985915) internal successors, (97), 71 states have internal predecessors, (97), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2025-03-16 13:51:47,931 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 84 states to 84 states and 117 transitions. [2025-03-16 13:51:47,931 INFO L78 Accepts]: Start accepts. Automaton has 84 states and 117 transitions. Word has length 54 [2025-03-16 13:51:47,931 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:51:47,931 INFO L471 AbstractCegarLoop]: Abstraction has 84 states and 117 transitions. [2025-03-16 13:51:47,931 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 57 states, 57 states have (on average 1.543859649122807) internal successors, (88), 57 states have internal predecessors, (88), 13 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2025-03-16 13:51:47,931 INFO L276 IsEmpty]: Start isEmpty. Operand 84 states and 117 transitions. [2025-03-16 13:51:47,932 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2025-03-16 13:51:47,932 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:51:47,932 INFO L218 NwaCegarLoop]: trace histogram [5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:51:47,938 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2025-03-16 13:51:48,132 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:51:48,133 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:51:48,133 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:51:48,133 INFO L85 PathProgramCache]: Analyzing trace with hash -1038436386, now seen corresponding path program 1 times [2025-03-16 13:51:48,134 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:51:48,134 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [831253129] [2025-03-16 13:51:48,134 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 13:51:48,134 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:51:48,139 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 54 statements into 1 equivalence classes. [2025-03-16 13:51:48,149 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 54 of 54 statements. [2025-03-16 13:51:48,149 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 13:51:48,149 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:51:49,106 INFO L134 CoverageAnalysis]: Checked inductivity of 73 backedges. 0 proven. 33 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2025-03-16 13:51:49,106 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:51:49,106 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [831253129] [2025-03-16 13:51:49,106 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [831253129] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:51:49,106 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1581964425] [2025-03-16 13:51:49,106 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 13:51:49,106 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:51:49,106 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:51:49,109 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 13:51:49,109 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2025-03-16 13:51:49,142 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 54 statements into 1 equivalence classes. [2025-03-16 13:51:49,156 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 54 of 54 statements. [2025-03-16 13:51:49,156 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 13:51:49,156 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:51:49,157 INFO L256 TraceCheckSpWp]: Trace formula consists of 193 conjuncts, 46 conjuncts are in the unsatisfiable core [2025-03-16 13:51:49,159 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:51:49,532 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 19 treesize of output 13 [2025-03-16 13:51:49,581 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 30 [2025-03-16 13:51:49,630 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:51:49,631 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 3 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 99 treesize of output 59 [2025-03-16 13:51:49,637 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 36 treesize of output 23 [2025-03-16 13:51:49,774 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:51:49,774 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 3 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 47 treesize of output 19 [2025-03-16 13:51:49,794 INFO L134 CoverageAnalysis]: Checked inductivity of 73 backedges. 16 proven. 33 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-03-16 13:51:49,794 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:51:49,972 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 207 treesize of output 201 [2025-03-16 13:51:49,988 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:51:49,989 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 165654 treesize of output 160534 [2025-03-16 13:51:50,366 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:51:50,366 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 6 select indices, 6 select index equivalence classes, 0 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 15 case distinctions, treesize of input 93 treesize of output 104 [2025-03-16 13:51:50,614 INFO L134 CoverageAnalysis]: Checked inductivity of 73 backedges. 4 proven. 29 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2025-03-16 13:51:50,614 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1581964425] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 13:51:50,614 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 13:51:50,614 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [23, 21, 20] total 57 [2025-03-16 13:51:50,614 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2087165505] [2025-03-16 13:51:50,614 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 13:51:50,615 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 57 states [2025-03-16 13:51:50,615 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:51:50,615 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 57 interpolants. [2025-03-16 13:51:50,616 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=291, Invalid=2901, Unknown=0, NotChecked=0, Total=3192 [2025-03-16 13:51:50,616 INFO L87 Difference]: Start difference. First operand 84 states and 117 transitions. Second operand has 57 states, 57 states have (on average 1.543859649122807) internal successors, (88), 57 states have internal predecessors, (88), 13 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2025-03-16 13:51:52,756 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:51:52,756 INFO L93 Difference]: Finished difference Result 164 states and 225 transitions. [2025-03-16 13:51:52,756 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 47 states. [2025-03-16 13:51:52,757 INFO L78 Accepts]: Start accepts. Automaton has has 57 states, 57 states have (on average 1.543859649122807) internal successors, (88), 57 states have internal predecessors, (88), 13 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) Word has length 54 [2025-03-16 13:51:52,757 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:51:52,757 INFO L225 Difference]: With dead ends: 164 [2025-03-16 13:51:52,758 INFO L226 Difference]: Without dead ends: 161 [2025-03-16 13:51:52,759 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 170 GetRequests, 73 SyntacticMatches, 2 SemanticMatches, 95 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2546 ImplicationChecksByTransitivity, 2.6s TimeCoverageRelationStatistics Valid=1039, Invalid=8273, Unknown=0, NotChecked=0, Total=9312 [2025-03-16 13:51:52,760 INFO L435 NwaCegarLoop]: 27 mSDtfsCounter, 201 mSDsluCounter, 417 mSDsCounter, 0 mSdLazyCounter, 1333 mSolverCounterSat, 123 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 202 SdHoareTripleChecker+Valid, 444 SdHoareTripleChecker+Invalid, 1456 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 123 IncrementalHoareTripleChecker+Valid, 1333 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2025-03-16 13:51:52,760 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [202 Valid, 444 Invalid, 1456 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [123 Valid, 1333 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2025-03-16 13:51:52,760 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 161 states. [2025-03-16 13:51:52,780 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 161 to 96. [2025-03-16 13:51:52,782 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 96 states, 82 states have (on average 1.3780487804878048) internal successors, (113), 82 states have internal predecessors, (113), 11 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2025-03-16 13:51:52,784 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 135 transitions. [2025-03-16 13:51:52,784 INFO L78 Accepts]: Start accepts. Automaton has 96 states and 135 transitions. Word has length 54 [2025-03-16 13:51:52,784 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:51:52,784 INFO L471 AbstractCegarLoop]: Abstraction has 96 states and 135 transitions. [2025-03-16 13:51:52,784 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 57 states, 57 states have (on average 1.543859649122807) internal successors, (88), 57 states have internal predecessors, (88), 13 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2025-03-16 13:51:52,784 INFO L276 IsEmpty]: Start isEmpty. Operand 96 states and 135 transitions. [2025-03-16 13:51:52,785 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2025-03-16 13:51:52,785 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:51:52,787 INFO L218 NwaCegarLoop]: trace histogram [5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:51:52,793 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2025-03-16 13:51:52,987 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2025-03-16 13:51:52,988 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:51:52,988 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:51:52,988 INFO L85 PathProgramCache]: Analyzing trace with hash 499731102, now seen corresponding path program 2 times [2025-03-16 13:51:52,988 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:51:52,988 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1683145127] [2025-03-16 13:51:52,988 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 13:51:52,988 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:51:52,996 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 54 statements into 2 equivalence classes. [2025-03-16 13:51:53,013 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 54 of 54 statements. [2025-03-16 13:51:53,013 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 13:51:53,013 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:51:53,917 INFO L134 CoverageAnalysis]: Checked inductivity of 73 backedges. 0 proven. 33 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2025-03-16 13:51:53,917 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:51:53,917 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1683145127] [2025-03-16 13:51:53,917 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1683145127] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:51:53,917 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [688375213] [2025-03-16 13:51:53,917 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 13:51:53,917 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:51:53,917 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:51:53,919 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 13:51:53,920 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2025-03-16 13:51:53,953 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 54 statements into 2 equivalence classes. [2025-03-16 13:51:53,967 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 54 of 54 statements. [2025-03-16 13:51:53,967 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 13:51:53,967 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:51:53,968 INFO L256 TraceCheckSpWp]: Trace formula consists of 193 conjuncts, 43 conjuncts are in the unsatisfiable core [2025-03-16 13:51:53,970 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:51:54,295 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 13 [2025-03-16 13:51:54,336 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 30 [2025-03-16 13:51:54,387 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:51:54,387 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 3 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 95 treesize of output 55 [2025-03-16 13:51:54,392 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 42 treesize of output 33 [2025-03-16 13:51:54,542 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:51:54,543 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 3 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 53 treesize of output 21 [2025-03-16 13:51:54,585 INFO L134 CoverageAnalysis]: Checked inductivity of 73 backedges. 0 proven. 33 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2025-03-16 13:51:54,585 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:51:54,795 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 207 treesize of output 201 [2025-03-16 13:51:54,811 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:51:54,812 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 82314 treesize of output 79754 [2025-03-16 13:51:55,190 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:51:55,190 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 6 select indices, 6 select index equivalence classes, 0 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 15 case distinctions, treesize of input 81 treesize of output 99 [2025-03-16 13:51:55,428 INFO L134 CoverageAnalysis]: Checked inductivity of 73 backedges. 4 proven. 29 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2025-03-16 13:51:55,428 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [688375213] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 13:51:55,428 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 13:51:55,428 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 20, 20] total 56 [2025-03-16 13:51:55,428 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2100970345] [2025-03-16 13:51:55,428 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 13:51:55,428 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 56 states [2025-03-16 13:51:55,429 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:51:55,429 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 56 interpolants. [2025-03-16 13:51:55,429 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=289, Invalid=2791, Unknown=0, NotChecked=0, Total=3080 [2025-03-16 13:51:55,430 INFO L87 Difference]: Start difference. First operand 96 states and 135 transitions. Second operand has 56 states, 56 states have (on average 1.5178571428571428) internal successors, (85), 56 states have internal predecessors, (85), 13 states have call successors, (13), 1 states have call predecessors, (13), 1 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2025-03-16 13:51:59,299 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:51:59,299 INFO L93 Difference]: Finished difference Result 209 states and 293 transitions. [2025-03-16 13:51:59,299 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 85 states. [2025-03-16 13:51:59,299 INFO L78 Accepts]: Start accepts. Automaton has has 56 states, 56 states have (on average 1.5178571428571428) internal successors, (85), 56 states have internal predecessors, (85), 13 states have call successors, (13), 1 states have call predecessors, (13), 1 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) Word has length 54 [2025-03-16 13:51:59,300 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:51:59,300 INFO L225 Difference]: With dead ends: 209 [2025-03-16 13:51:59,300 INFO L226 Difference]: Without dead ends: 206 [2025-03-16 13:51:59,303 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 203 GetRequests, 74 SyntacticMatches, 2 SemanticMatches, 127 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5057 ImplicationChecksByTransitivity, 4.1s TimeCoverageRelationStatistics Valid=1936, Invalid=14576, Unknown=0, NotChecked=0, Total=16512 [2025-03-16 13:51:59,304 INFO L435 NwaCegarLoop]: 28 mSDtfsCounter, 222 mSDsluCounter, 462 mSDsCounter, 0 mSdLazyCounter, 1790 mSolverCounterSat, 144 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 222 SdHoareTripleChecker+Valid, 490 SdHoareTripleChecker+Invalid, 1934 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 144 IncrementalHoareTripleChecker+Valid, 1790 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2025-03-16 13:51:59,304 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [222 Valid, 490 Invalid, 1934 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [144 Valid, 1790 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2025-03-16 13:51:59,304 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 206 states. [2025-03-16 13:51:59,333 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 206 to 132. [2025-03-16 13:51:59,334 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 132 states, 112 states have (on average 1.4285714285714286) internal successors, (160), 112 states have internal predecessors, (160), 17 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2025-03-16 13:51:59,334 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 132 states to 132 states and 194 transitions. [2025-03-16 13:51:59,335 INFO L78 Accepts]: Start accepts. Automaton has 132 states and 194 transitions. Word has length 54 [2025-03-16 13:51:59,335 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:51:59,335 INFO L471 AbstractCegarLoop]: Abstraction has 132 states and 194 transitions. [2025-03-16 13:51:59,335 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 56 states, 56 states have (on average 1.5178571428571428) internal successors, (85), 56 states have internal predecessors, (85), 13 states have call successors, (13), 1 states have call predecessors, (13), 1 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2025-03-16 13:51:59,335 INFO L276 IsEmpty]: Start isEmpty. Operand 132 states and 194 transitions. [2025-03-16 13:51:59,335 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2025-03-16 13:51:59,335 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:51:59,335 INFO L218 NwaCegarLoop]: trace histogram [5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:51:59,341 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2025-03-16 13:51:59,536 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2025-03-16 13:51:59,536 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:51:59,536 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:51:59,536 INFO L85 PathProgramCache]: Analyzing trace with hash 206328095, now seen corresponding path program 3 times [2025-03-16 13:51:59,536 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:51:59,536 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [129245617] [2025-03-16 13:51:59,536 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 13:51:59,537 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:51:59,542 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 54 statements into 5 equivalence classes. [2025-03-16 13:51:59,563 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) and asserted 54 of 54 statements. [2025-03-16 13:51:59,563 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2025-03-16 13:51:59,563 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:52:00,231 INFO L134 CoverageAnalysis]: Checked inductivity of 73 backedges. 0 proven. 33 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2025-03-16 13:52:00,232 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:52:00,232 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [129245617] [2025-03-16 13:52:00,232 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [129245617] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:52:00,232 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [265346918] [2025-03-16 13:52:00,232 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 13:52:00,232 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:52:00,232 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:52:00,234 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 13:52:00,235 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2025-03-16 13:52:00,273 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 54 statements into 5 equivalence classes. [2025-03-16 13:52:00,293 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) and asserted 54 of 54 statements. [2025-03-16 13:52:00,293 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2025-03-16 13:52:00,293 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:52:00,295 INFO L256 TraceCheckSpWp]: Trace formula consists of 189 conjuncts, 47 conjuncts are in the unsatisfiable core [2025-03-16 13:52:00,297 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:52:00,660 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 19 treesize of output 13 [2025-03-16 13:52:00,713 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 32 [2025-03-16 13:52:00,771 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:52:00,771 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 105 treesize of output 82 [2025-03-16 13:52:00,776 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:52:00,776 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 3 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 91 treesize of output 59 [2025-03-16 13:52:00,918 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:52:00,918 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 49 treesize of output 17 [2025-03-16 13:52:00,960 INFO L134 CoverageAnalysis]: Checked inductivity of 73 backedges. 0 proven. 33 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2025-03-16 13:52:00,961 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:52:01,169 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 87 treesize of output 83 [2025-03-16 13:52:01,173 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:52:01,173 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 652 treesize of output 620 [2025-03-16 13:52:01,538 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:52:01,538 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 6 select indices, 6 select index equivalence classes, 0 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 15 case distinctions, treesize of input 105 treesize of output 109 [2025-03-16 13:52:01,792 INFO L134 CoverageAnalysis]: Checked inductivity of 73 backedges. 10 proven. 23 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2025-03-16 13:52:01,792 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [265346918] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 13:52:01,792 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 13:52:01,793 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 20, 20] total 56 [2025-03-16 13:52:01,793 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [940590120] [2025-03-16 13:52:01,793 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 13:52:01,793 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 56 states [2025-03-16 13:52:01,793 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:52:01,793 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 56 interpolants. [2025-03-16 13:52:01,794 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=371, Invalid=2709, Unknown=0, NotChecked=0, Total=3080 [2025-03-16 13:52:01,794 INFO L87 Difference]: Start difference. First operand 132 states and 194 transitions. Second operand has 56 states, 56 states have (on average 1.5) internal successors, (84), 56 states have internal predecessors, (84), 11 states have call successors, (12), 1 states have call predecessors, (12), 1 states have return successors, (12), 11 states have call predecessors, (12), 11 states have call successors, (12) [2025-03-16 13:52:03,366 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:52:03,367 INFO L93 Difference]: Finished difference Result 196 states and 285 transitions. [2025-03-16 13:52:03,367 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 40 states. [2025-03-16 13:52:03,367 INFO L78 Accepts]: Start accepts. Automaton has has 56 states, 56 states have (on average 1.5) internal successors, (84), 56 states have internal predecessors, (84), 11 states have call successors, (12), 1 states have call predecessors, (12), 1 states have return successors, (12), 11 states have call predecessors, (12), 11 states have call successors, (12) Word has length 54 [2025-03-16 13:52:03,367 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:52:03,368 INFO L225 Difference]: With dead ends: 196 [2025-03-16 13:52:03,368 INFO L226 Difference]: Without dead ends: 185 [2025-03-16 13:52:03,369 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 155 GetRequests, 74 SyntacticMatches, 0 SemanticMatches, 81 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1630 ImplicationChecksByTransitivity, 2.1s TimeCoverageRelationStatistics Valid=1027, Invalid=5779, Unknown=0, NotChecked=0, Total=6806 [2025-03-16 13:52:03,369 INFO L435 NwaCegarLoop]: 24 mSDtfsCounter, 125 mSDsluCounter, 423 mSDsCounter, 0 mSdLazyCounter, 1224 mSolverCounterSat, 121 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 125 SdHoareTripleChecker+Valid, 447 SdHoareTripleChecker+Invalid, 1345 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 121 IncrementalHoareTripleChecker+Valid, 1224 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2025-03-16 13:52:03,369 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [125 Valid, 447 Invalid, 1345 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [121 Valid, 1224 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2025-03-16 13:52:03,369 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 185 states. [2025-03-16 13:52:03,394 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 185 to 99. [2025-03-16 13:52:03,394 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 99 states, 84 states have (on average 1.369047619047619) internal successors, (115), 84 states have internal predecessors, (115), 12 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2025-03-16 13:52:03,394 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 99 states to 99 states and 139 transitions. [2025-03-16 13:52:03,395 INFO L78 Accepts]: Start accepts. Automaton has 99 states and 139 transitions. Word has length 54 [2025-03-16 13:52:03,395 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:52:03,395 INFO L471 AbstractCegarLoop]: Abstraction has 99 states and 139 transitions. [2025-03-16 13:52:03,395 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 56 states, 56 states have (on average 1.5) internal successors, (84), 56 states have internal predecessors, (84), 11 states have call successors, (12), 1 states have call predecessors, (12), 1 states have return successors, (12), 11 states have call predecessors, (12), 11 states have call successors, (12) [2025-03-16 13:52:03,395 INFO L276 IsEmpty]: Start isEmpty. Operand 99 states and 139 transitions. [2025-03-16 13:52:03,395 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2025-03-16 13:52:03,395 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:52:03,395 INFO L218 NwaCegarLoop]: trace histogram [5, 5, 5, 4, 4, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:52:03,401 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2025-03-16 13:52:03,596 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2025-03-16 13:52:03,596 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:52:03,596 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:52:03,596 INFO L85 PathProgramCache]: Analyzing trace with hash 1218833181, now seen corresponding path program 8 times [2025-03-16 13:52:03,596 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:52:03,596 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1716879254] [2025-03-16 13:52:03,596 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 13:52:03,596 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:52:03,602 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 56 statements into 2 equivalence classes. [2025-03-16 13:52:03,608 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 56 of 56 statements. [2025-03-16 13:52:03,608 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 13:52:03,608 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:52:03,681 INFO L134 CoverageAnalysis]: Checked inductivity of 81 backedges. 7 proven. 24 refuted. 0 times theorem prover too weak. 50 trivial. 0 not checked. [2025-03-16 13:52:03,681 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:52:03,681 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1716879254] [2025-03-16 13:52:03,681 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1716879254] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:52:03,681 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1949786079] [2025-03-16 13:52:03,681 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 13:52:03,681 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:52:03,681 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:52:03,683 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 13:52:03,685 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2025-03-16 13:52:03,726 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 56 statements into 2 equivalence classes. [2025-03-16 13:52:03,743 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 56 of 56 statements. [2025-03-16 13:52:03,743 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 13:52:03,743 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:52:03,744 INFO L256 TraceCheckSpWp]: Trace formula consists of 209 conjuncts, 10 conjuncts are in the unsatisfiable core [2025-03-16 13:52:03,745 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:52:03,793 INFO L134 CoverageAnalysis]: Checked inductivity of 81 backedges. 10 proven. 21 refuted. 0 times theorem prover too weak. 50 trivial. 0 not checked. [2025-03-16 13:52:03,793 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:52:03,849 INFO L134 CoverageAnalysis]: Checked inductivity of 81 backedges. 10 proven. 21 refuted. 0 times theorem prover too weak. 50 trivial. 0 not checked. [2025-03-16 13:52:03,849 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1949786079] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 13:52:03,849 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 13:52:03,849 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10, 10] total 16 [2025-03-16 13:52:03,850 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [837444510] [2025-03-16 13:52:03,850 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 13:52:03,850 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2025-03-16 13:52:03,850 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:52:03,850 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2025-03-16 13:52:03,850 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=68, Invalid=172, Unknown=0, NotChecked=0, Total=240 [2025-03-16 13:52:03,852 INFO L87 Difference]: Start difference. First operand 99 states and 139 transitions. Second operand has 16 states, 16 states have (on average 2.75) internal successors, (44), 16 states have internal predecessors, (44), 5 states have call successors, (6), 1 states have call predecessors, (6), 1 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) [2025-03-16 13:52:03,954 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:52:03,954 INFO L93 Difference]: Finished difference Result 161 states and 226 transitions. [2025-03-16 13:52:03,954 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-03-16 13:52:03,954 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 2.75) internal successors, (44), 16 states have internal predecessors, (44), 5 states have call successors, (6), 1 states have call predecessors, (6), 1 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) Word has length 56 [2025-03-16 13:52:03,954 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:52:03,955 INFO L225 Difference]: With dead ends: 161 [2025-03-16 13:52:03,955 INFO L226 Difference]: Without dead ends: 136 [2025-03-16 13:52:03,955 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 123 GetRequests, 100 SyntacticMatches, 6 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 132 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=98, Invalid=244, Unknown=0, NotChecked=0, Total=342 [2025-03-16 13:52:03,956 INFO L435 NwaCegarLoop]: 18 mSDtfsCounter, 14 mSDsluCounter, 80 mSDsCounter, 0 mSdLazyCounter, 111 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 98 SdHoareTripleChecker+Invalid, 125 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 111 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 13:52:03,956 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 98 Invalid, 125 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 111 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 13:52:03,956 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 136 states. [2025-03-16 13:52:03,982 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 136 to 111. [2025-03-16 13:52:03,982 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 111 states, 95 states have (on average 1.3473684210526315) internal successors, (128), 95 states have internal predecessors, (128), 13 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2025-03-16 13:52:03,983 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 111 states to 111 states and 154 transitions. [2025-03-16 13:52:03,983 INFO L78 Accepts]: Start accepts. Automaton has 111 states and 154 transitions. Word has length 56 [2025-03-16 13:52:03,983 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:52:03,983 INFO L471 AbstractCegarLoop]: Abstraction has 111 states and 154 transitions. [2025-03-16 13:52:03,983 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 2.75) internal successors, (44), 16 states have internal predecessors, (44), 5 states have call successors, (6), 1 states have call predecessors, (6), 1 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) [2025-03-16 13:52:03,983 INFO L276 IsEmpty]: Start isEmpty. Operand 111 states and 154 transitions. [2025-03-16 13:52:03,984 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 67 [2025-03-16 13:52:03,984 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:52:03,984 INFO L218 NwaCegarLoop]: trace histogram [6, 6, 6, 4, 4, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:52:03,989 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2025-03-16 13:52:04,184 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2025-03-16 13:52:04,184 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:52:04,185 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:52:04,185 INFO L85 PathProgramCache]: Analyzing trace with hash -472784889, now seen corresponding path program 9 times [2025-03-16 13:52:04,185 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:52:04,185 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [270622946] [2025-03-16 13:52:04,185 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 13:52:04,185 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:52:04,191 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 66 statements into 6 equivalence classes. [2025-03-16 13:52:04,202 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) and asserted 58 of 66 statements. [2025-03-16 13:52:04,202 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2025-03-16 13:52:04,202 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:52:05,137 INFO L134 CoverageAnalysis]: Checked inductivity of 120 backedges. 0 proven. 60 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2025-03-16 13:52:05,137 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:52:05,137 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [270622946] [2025-03-16 13:52:05,138 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [270622946] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:52:05,138 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [56334102] [2025-03-16 13:52:05,138 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 13:52:05,138 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:52:05,138 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:52:05,140 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 13:52:05,141 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2025-03-16 13:52:05,183 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 66 statements into 6 equivalence classes. [2025-03-16 13:52:05,208 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) and asserted 58 of 66 statements. [2025-03-16 13:52:05,208 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2025-03-16 13:52:05,208 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:52:05,210 INFO L256 TraceCheckSpWp]: Trace formula consists of 194 conjuncts, 63 conjuncts are in the unsatisfiable core [2025-03-16 13:52:05,212 INFO L279 TraceCheckSpWp]: Computing forward predicates...