./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 e2fb8bed Calling Ultimate with: /root/.sdkman/candidates/java/21.0.5-tem/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/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-?-e2fb8be-m [2025-03-08 00:41:49,477 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-08 00:41:49,526 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2025-03-08 00:41:49,530 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-08 00:41:49,530 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-08 00:41:49,553 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-08 00:41:49,554 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-08 00:41:49,554 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-08 00:41:49,554 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-08 00:41:49,555 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-08 00:41:49,555 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-03-08 00:41:49,555 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-03-08 00:41:49,555 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-08 00:41:49,555 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-08 00:41:49,555 INFO L153 SettingsManager]: * Use SBE=true [2025-03-08 00:41:49,556 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-08 00:41:49,556 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-03-08 00:41:49,556 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-08 00:41:49,556 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-08 00:41:49,556 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-08 00:41:49,556 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-08 00:41:49,556 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-03-08 00:41:49,556 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-03-08 00:41:49,556 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-03-08 00:41:49,556 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-08 00:41:49,556 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-08 00:41:49,556 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-08 00:41:49,556 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-08 00:41:49,557 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-08 00:41:49,557 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-08 00:41:49,557 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-03-08 00:41:49,557 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-03-08 00:41:49,557 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-08 00:41:49,557 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-08 00:41:49,557 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-03-08 00:41:49,557 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-03-08 00:41:49,557 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-03-08 00:41:49,557 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-08 00:41:49,557 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-03-08 00:41:49,557 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-03-08 00:41:49,557 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-03-08 00:41:49,557 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-03-08 00:41:49,557 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-03-08 00:41:49,557 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-08 00:41:49,794 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-08 00:41:49,800 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-08 00:41:49,802 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-08 00:41:49,803 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-08 00:41:49,803 INFO L274 PluginConnector]: CDTParser initialized [2025-03-08 00:41:49,805 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-08 00:41:50,951 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/0d90b01a8/e0065c8042d2402790536c37bd59dcde/FLAG000782929 [2025-03-08 00:41:51,150 INFO L384 CDTParser]: Found 1 translation units. [2025-03-08 00:41:51,151 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/array-cav19/array_min_and_copy_shift_sum_add.c [2025-03-08 00:41:51,157 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/0d90b01a8/e0065c8042d2402790536c37bd59dcde/FLAG000782929 [2025-03-08 00:41:51,518 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/0d90b01a8/e0065c8042d2402790536c37bd59dcde [2025-03-08 00:41:51,519 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-08 00:41:51,520 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-08 00:41:51,521 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-08 00:41:51,521 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-08 00:41:51,524 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-08 00:41:51,524 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.03 12:41:51" (1/1) ... [2025-03-08 00:41:51,525 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@34dc6e07 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 12:41:51, skipping insertion in model container [2025-03-08 00:41:51,525 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.03 12:41:51" (1/1) ... [2025-03-08 00:41:51,533 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-08 00:41:51,618 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-08 00:41:51,629 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-08 00:41:51,635 INFO L200 MainTranslator]: Completed pre-run [2025-03-08 00:41:51,641 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-08 00:41:51,646 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-08 00:41:51,653 INFO L204 MainTranslator]: Completed translation [2025-03-08 00:41:51,654 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 12:41:51 WrapperNode [2025-03-08 00:41:51,654 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-08 00:41:51,655 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-08 00:41:51,655 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-08 00:41:51,655 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-08 00:41:51,658 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 12:41:51" (1/1) ... [2025-03-08 00:41:51,662 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 12:41:51" (1/1) ... [2025-03-08 00:41:51,671 INFO L138 Inliner]: procedures = 15, calls = 24, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 75 [2025-03-08 00:41:51,672 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-08 00:41:51,672 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-08 00:41:51,672 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-08 00:41:51,672 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-08 00:41:51,677 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 12:41:51" (1/1) ... [2025-03-08 00:41:51,677 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 12:41:51" (1/1) ... [2025-03-08 00:41:51,678 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 12:41:51" (1/1) ... [2025-03-08 00:41:51,685 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-08 00:41:51,685 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 12:41:51" (1/1) ... [2025-03-08 00:41:51,685 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 12:41:51" (1/1) ... [2025-03-08 00:41:51,688 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 12:41:51" (1/1) ... [2025-03-08 00:41:51,688 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 12:41:51" (1/1) ... [2025-03-08 00:41:51,689 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 12:41:51" (1/1) ... [2025-03-08 00:41:51,689 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 12:41:51" (1/1) ... [2025-03-08 00:41:51,690 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-08 00:41:51,691 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-08 00:41:51,691 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-08 00:41:51,691 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-08 00:41:51,692 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 12:41:51" (1/1) ... [2025-03-08 00:41:51,695 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-08 00:41:51,705 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 00:41:51,719 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2025-03-08 00:41:51,722 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2025-03-08 00:41:51,737 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-08 00:41:51,737 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2025-03-08 00:41:51,738 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2025-03-08 00:41:51,738 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-03-08 00:41:51,738 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2025-03-08 00:41:51,738 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2025-03-08 00:41:51,738 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2025-03-08 00:41:51,738 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2025-03-08 00:41:51,738 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2025-03-08 00:41:51,738 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#2 [2025-03-08 00:41:51,738 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-08 00:41:51,738 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-08 00:41:51,738 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2025-03-08 00:41:51,738 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2025-03-08 00:41:51,738 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#2 [2025-03-08 00:41:51,738 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2025-03-08 00:41:51,783 INFO L256 CfgBuilder]: Building ICFG [2025-03-08 00:41:51,784 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-08 00:41:51,914 INFO L1307 $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-08 00:41:51,922 INFO L? ?]: Removed 12 outVars from TransFormulas that were not future-live. [2025-03-08 00:41:51,922 INFO L307 CfgBuilder]: Performing block encoding [2025-03-08 00:41:51,931 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-08 00:41:51,932 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-08 00:41:51,932 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 08.03 12:41:51 BoogieIcfgContainer [2025-03-08 00:41:51,933 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-08 00:41:51,935 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-03-08 00:41:51,935 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-03-08 00:41:51,938 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-03-08 00:41:51,939 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 08.03 12:41:51" (1/3) ... [2025-03-08 00:41:51,939 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@72b4fa03 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.03 12:41:51, skipping insertion in model container [2025-03-08 00:41:51,940 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 12:41:51" (2/3) ... [2025-03-08 00:41:51,940 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@72b4fa03 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.03 12:41:51, skipping insertion in model container [2025-03-08 00:41:51,940 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 08.03 12:41:51" (3/3) ... [2025-03-08 00:41:51,941 INFO L128 eAbstractionObserver]: Analyzing ICFG array_min_and_copy_shift_sum_add.c [2025-03-08 00:41:51,951 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-03-08 00:41:51,953 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG array_min_and_copy_shift_sum_add.c that has 2 procedures, 25 locations, 1 initial locations, 3 loop locations, and 1 error locations. [2025-03-08 00:41:51,996 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-03-08 00:41:52,005 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;@4dba72bb, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-03-08 00:41:52,005 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-03-08 00:41:52,009 INFO L276 IsEmpty]: Start isEmpty. Operand has 25 states, 19 states have (on average 1.4210526315789473) internal successors, (27), 20 states have internal predecessors, (27), 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-08 00:41:52,013 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2025-03-08 00:41:52,013 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 00:41:52,014 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 00:41:52,014 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 00:41:52,017 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 00:41:52,017 INFO L85 PathProgramCache]: Analyzing trace with hash -1660025251, now seen corresponding path program 1 times [2025-03-08 00:41:52,023 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 00:41:52,024 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1104365033] [2025-03-08 00:41:52,025 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 00:41:52,025 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 00:41:52,085 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 19 statements into 1 equivalence classes. [2025-03-08 00:41:52,095 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 19 of 19 statements. [2025-03-08 00:41:52,096 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 00:41:52,096 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:41:52,127 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2025-03-08 00:41:52,128 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 00:41:52,128 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1104365033] [2025-03-08 00:41:52,128 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1104365033] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 00:41:52,128 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [187980362] [2025-03-08 00:41:52,128 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 00:41:52,128 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 00:41:52,128 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 00:41:52,131 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-08 00:41:52,133 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2025-03-08 00:41:52,178 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 19 statements into 1 equivalence classes. [2025-03-08 00:41:52,192 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 19 of 19 statements. [2025-03-08 00:41:52,192 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 00:41:52,192 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:41:52,193 INFO L256 TraceCheckSpWp]: Trace formula consists of 83 conjuncts, 1 conjuncts are in the unsatisfiable core [2025-03-08 00:41:52,195 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 00:41:52,202 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2025-03-08 00:41:52,203 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-08 00:41:52,203 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [187980362] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 00:41:52,203 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-08 00:41:52,203 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [2] total 2 [2025-03-08 00:41:52,205 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1701976872] [2025-03-08 00:41:52,205 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 00:41:52,207 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2025-03-08 00:41:52,208 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 00:41:52,220 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2025-03-08 00:41:52,221 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-03-08 00:41:52,224 INFO L87 Difference]: Start difference. First operand has 25 states, 19 states have (on average 1.4210526315789473) internal successors, (27), 20 states have internal predecessors, (27), 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 7.0) internal successors, (14), 2 states have internal predecessors, (14), 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-08 00:41:52,233 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 00:41:52,234 INFO L93 Difference]: Finished difference Result 47 states and 65 transitions. [2025-03-08 00:41:52,234 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2025-03-08 00:41:52,235 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 7.0) internal successors, (14), 2 states have internal predecessors, (14), 2 states have call successors, (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 19 [2025-03-08 00:41:52,235 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 00:41:52,238 INFO L225 Difference]: With dead ends: 47 [2025-03-08 00:41:52,238 INFO L226 Difference]: Without dead ends: 21 [2025-03-08 00:41:52,240 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 20 GetRequests, 20 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-03-08 00:41:52,242 INFO L435 NwaCegarLoop]: 31 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, 31 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-08 00:41:52,242 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 31 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-08 00:41:52,251 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 21 states. [2025-03-08 00:41:52,258 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 21 to 21. [2025-03-08 00:41:52,259 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-08 00:41:52,261 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 27 transitions. [2025-03-08 00:41:52,262 INFO L78 Accepts]: Start accepts. Automaton has 21 states and 27 transitions. Word has length 19 [2025-03-08 00:41:52,263 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 00:41:52,263 INFO L471 AbstractCegarLoop]: Abstraction has 21 states and 27 transitions. [2025-03-08 00:41:52,263 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 7.0) internal successors, (14), 2 states have internal predecessors, (14), 2 states have call successors, (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-08 00:41:52,263 INFO L276 IsEmpty]: Start isEmpty. Operand 21 states and 27 transitions. [2025-03-08 00:41:52,264 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2025-03-08 00:41:52,264 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 00:41:52,264 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 00:41:52,270 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-08 00:41:52,464 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable0 [2025-03-08 00:41:52,465 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 00:41:52,465 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 00:41:52,465 INFO L85 PathProgramCache]: Analyzing trace with hash -1959927905, now seen corresponding path program 1 times [2025-03-08 00:41:52,465 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 00:41:52,465 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1450158984] [2025-03-08 00:41:52,465 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 00:41:52,465 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 00:41:52,474 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 19 statements into 1 equivalence classes. [2025-03-08 00:41:52,490 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 19 of 19 statements. [2025-03-08 00:41:52,490 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 00:41:52,490 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:41:52,640 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-08 00:41:52,641 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 00:41:52,641 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1450158984] [2025-03-08 00:41:52,641 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1450158984] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 00:41:52,641 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-08 00:41:52,641 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2025-03-08 00:41:52,641 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1758661783] [2025-03-08 00:41:52,641 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 00:41:52,642 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2025-03-08 00:41:52,642 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 00:41:52,642 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2025-03-08 00:41:52,642 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2025-03-08 00:41:52,643 INFO L87 Difference]: Start difference. First operand 21 states and 27 transitions. Second operand has 4 states, 4 states have (on average 3.0) internal successors, (12), 4 states have internal predecessors, (12), 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-08 00:41:52,655 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 00:41:52,655 INFO L93 Difference]: Finished difference Result 25 states and 31 transitions. [2025-03-08 00:41:52,655 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2025-03-08 00:41:52,655 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 3.0) internal successors, (12), 4 states have internal predecessors, (12), 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 19 [2025-03-08 00:41:52,656 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 00:41:52,656 INFO L225 Difference]: With dead ends: 25 [2025-03-08 00:41:52,656 INFO L226 Difference]: Without dead ends: 22 [2025-03-08 00:41:52,656 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-08 00:41:52,657 INFO L435 NwaCegarLoop]: 25 mSDtfsCounter, 8 mSDsluCounter, 34 mSDsCounter, 0 mSdLazyCounter, 8 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 59 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-08 00:41:52,657 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 59 Invalid, 8 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 8 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-08 00:41:52,658 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 22 states. [2025-03-08 00:41:52,660 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 22 to 22. [2025-03-08 00:41:52,661 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 22 states, 17 states have (on average 1.2941176470588236) internal successors, (22), 17 states have internal predecessors, (22), 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-08 00:41:52,661 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 22 states to 22 states and 28 transitions. [2025-03-08 00:41:52,661 INFO L78 Accepts]: Start accepts. Automaton has 22 states and 28 transitions. Word has length 19 [2025-03-08 00:41:52,662 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 00:41:52,662 INFO L471 AbstractCegarLoop]: Abstraction has 22 states and 28 transitions. [2025-03-08 00:41:52,662 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 3.0) internal successors, (12), 4 states have internal predecessors, (12), 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-08 00:41:52,662 INFO L276 IsEmpty]: Start isEmpty. Operand 22 states and 28 transitions. [2025-03-08 00:41:52,663 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2025-03-08 00:41:52,663 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 00:41:52,663 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 00:41:52,663 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2025-03-08 00:41:52,663 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 00:41:52,663 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 00:41:52,664 INFO L85 PathProgramCache]: Analyzing trace with hash -628191158, now seen corresponding path program 1 times [2025-03-08 00:41:52,664 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 00:41:52,664 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [543395230] [2025-03-08 00:41:52,664 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 00:41:52,664 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 00:41:52,672 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 20 statements into 1 equivalence classes. [2025-03-08 00:41:52,686 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 20 of 20 statements. [2025-03-08 00:41:52,686 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 00:41:52,686 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:41:52,773 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-08 00:41:52,773 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 00:41:52,773 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [543395230] [2025-03-08 00:41:52,773 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [543395230] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 00:41:52,773 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-08 00:41:52,774 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-08 00:41:52,774 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1572971018] [2025-03-08 00:41:52,774 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 00:41:52,774 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-08 00:41:52,774 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 00:41:52,774 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-08 00:41:52,775 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2025-03-08 00:41:52,775 INFO L87 Difference]: Start difference. First operand 22 states and 28 transitions. Second operand has 5 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 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-08 00:41:52,821 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 00:41:52,821 INFO L93 Difference]: Finished difference Result 37 states and 50 transitions. [2025-03-08 00:41:52,821 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2025-03-08 00:41:52,821 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 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 20 [2025-03-08 00:41:52,822 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 00:41:52,822 INFO L225 Difference]: With dead ends: 37 [2025-03-08 00:41:52,822 INFO L226 Difference]: Without dead ends: 29 [2025-03-08 00:41:52,822 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-08 00:41:52,823 INFO L435 NwaCegarLoop]: 18 mSDtfsCounter, 6 mSDsluCounter, 31 mSDsCounter, 0 mSdLazyCounter, 39 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 49 SdHoareTripleChecker+Invalid, 46 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 39 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-08 00:41:52,823 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 49 Invalid, 46 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-08 00:41:52,823 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 29 states. [2025-03-08 00:41:52,828 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 29 to 24. [2025-03-08 00:41:52,829 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24 states, 19 states have (on average 1.263157894736842) internal successors, (24), 19 states have internal predecessors, (24), 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-08 00:41:52,830 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 30 transitions. [2025-03-08 00:41:52,830 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 30 transitions. Word has length 20 [2025-03-08 00:41:52,830 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 00:41:52,830 INFO L471 AbstractCegarLoop]: Abstraction has 24 states and 30 transitions. [2025-03-08 00:41:52,830 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 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-08 00:41:52,830 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 30 transitions. [2025-03-08 00:41:52,830 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2025-03-08 00:41:52,831 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 00:41:52,831 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, 1] [2025-03-08 00:41:52,831 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2025-03-08 00:41:52,831 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 00:41:52,831 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 00:41:52,831 INFO L85 PathProgramCache]: Analyzing trace with hash -1551076341, now seen corresponding path program 1 times [2025-03-08 00:41:52,831 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 00:41:52,832 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [222653033] [2025-03-08 00:41:52,832 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 00:41:52,832 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 00:41:52,841 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-03-08 00:41:52,861 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-03-08 00:41:52,861 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 00:41:52,861 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:41:53,409 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-08 00:41:53,410 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 00:41:53,410 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [222653033] [2025-03-08 00:41:53,410 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [222653033] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 00:41:53,410 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [939966326] [2025-03-08 00:41:53,410 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 00:41:53,410 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 00:41:53,410 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 00:41:53,413 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-08 00:41:53,414 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2025-03-08 00:41:53,451 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-03-08 00:41:53,468 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-03-08 00:41:53,468 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 00:41:53,468 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:41:53,469 INFO L256 TraceCheckSpWp]: Trace formula consists of 121 conjuncts, 19 conjuncts are in the unsatisfiable core [2025-03-08 00:41:53,471 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 00:41:53,648 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-03-08 00:41:53,685 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2025-03-08 00:41:53,698 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-08 00:41:53,699 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 00:41:53,745 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-08 00:41:53,749 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-08 00:41:53,794 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:41:53,795 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-08 00:41:53,849 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-08 00:41:53,849 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [939966326] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 00:41:53,849 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-08 00:41:53,849 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 9, 9] total 21 [2025-03-08 00:41:53,849 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1026057448] [2025-03-08 00:41:53,849 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-08 00:41:53,849 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2025-03-08 00:41:53,849 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 00:41:53,850 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2025-03-08 00:41:53,850 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=90, Invalid=330, Unknown=0, NotChecked=0, Total=420 [2025-03-08 00:41:53,850 INFO L87 Difference]: Start difference. First operand 24 states and 30 transitions. Second operand has 21 states, 21 states have (on average 2.0) internal successors, (42), 21 states have internal predecessors, (42), 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-08 00:41:54,021 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 00:41:54,022 INFO L93 Difference]: Finished difference Result 43 states and 57 transitions. [2025-03-08 00:41:54,023 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2025-03-08 00:41:54,023 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 21 states have (on average 2.0) internal successors, (42), 21 states have internal predecessors, (42), 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 31 [2025-03-08 00:41:54,023 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 00:41:54,024 INFO L225 Difference]: With dead ends: 43 [2025-03-08 00:41:54,025 INFO L226 Difference]: Without dead ends: 40 [2025-03-08 00:41:54,025 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 76 GetRequests, 50 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-08 00:41:54,026 INFO L435 NwaCegarLoop]: 22 mSDtfsCounter, 42 mSDsluCounter, 110 mSDsCounter, 0 mSdLazyCounter, 140 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 44 SdHoareTripleChecker+Valid, 132 SdHoareTripleChecker+Invalid, 151 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 140 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 00:41:54,027 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [44 Valid, 132 Invalid, 151 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 140 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 00:41:54,027 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40 states. [2025-03-08 00:41:54,032 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40 to 37. [2025-03-08 00:41:54,032 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 30 states have (on average 1.3666666666666667) internal successors, (41), 30 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-08 00:41:54,034 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 51 transitions. [2025-03-08 00:41:54,034 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 51 transitions. Word has length 31 [2025-03-08 00:41:54,034 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 00:41:54,034 INFO L471 AbstractCegarLoop]: Abstraction has 37 states and 51 transitions. [2025-03-08 00:41:54,035 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 21 states have (on average 2.0) internal successors, (42), 21 states have internal predecessors, (42), 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-08 00:41:54,035 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 51 transitions. [2025-03-08 00:41:54,036 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2025-03-08 00:41:54,036 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 00:41:54,036 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, 1] [2025-03-08 00:41:54,042 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2025-03-08 00:41:54,241 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-08 00:41:54,241 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 00:41:54,241 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 00:41:54,241 INFO L85 PathProgramCache]: Analyzing trace with hash 936436492, now seen corresponding path program 1 times [2025-03-08 00:41:54,242 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 00:41:54,242 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [518897430] [2025-03-08 00:41:54,242 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 00:41:54,242 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 00:41:54,247 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-03-08 00:41:54,258 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-03-08 00:41:54,258 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 00:41:54,258 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:41:54,564 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-08 00:41:54,564 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 00:41:54,564 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [518897430] [2025-03-08 00:41:54,564 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [518897430] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 00:41:54,564 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1898107401] [2025-03-08 00:41:54,564 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 00:41:54,565 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 00:41:54,565 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 00:41:54,566 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-08 00:41:54,568 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2025-03-08 00:41:54,602 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-03-08 00:41:54,614 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-03-08 00:41:54,614 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 00:41:54,614 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:41:54,615 INFO L256 TraceCheckSpWp]: Trace formula consists of 117 conjuncts, 19 conjuncts are in the unsatisfiable core [2025-03-08 00:41:54,617 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 00:41:54,754 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-03-08 00:41:54,788 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2025-03-08 00:41:54,801 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-08 00:41:54,801 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 00:41:54,835 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-08 00:41:54,837 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-08 00:41:54,883 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:41:54,883 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-08 00:41:54,921 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-08 00:41:54,921 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1898107401] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 00:41:54,921 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-08 00:41:54,921 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 10, 10] total 24 [2025-03-08 00:41:54,921 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [445396716] [2025-03-08 00:41:54,921 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-08 00:41:54,922 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2025-03-08 00:41:54,922 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 00:41:54,922 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2025-03-08 00:41:54,922 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=105, Invalid=447, Unknown=0, NotChecked=0, Total=552 [2025-03-08 00:41:54,923 INFO L87 Difference]: Start difference. First operand 37 states and 51 transitions. Second operand has 24 states, 24 states have (on average 1.75) internal successors, (42), 24 states have internal predecessors, (42), 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-08 00:41:55,121 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 00:41:55,121 INFO L93 Difference]: Finished difference Result 53 states and 72 transitions. [2025-03-08 00:41:55,122 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2025-03-08 00:41:55,122 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 24 states have (on average 1.75) internal successors, (42), 24 states have internal predecessors, (42), 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 31 [2025-03-08 00:41:55,122 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 00:41:55,123 INFO L225 Difference]: With dead ends: 53 [2025-03-08 00:41:55,123 INFO L226 Difference]: Without dead ends: 50 [2025-03-08 00:41:55,123 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 77 GetRequests, 48 SyntacticMatches, 3 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 323 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=154, Invalid=602, Unknown=0, NotChecked=0, Total=756 [2025-03-08 00:41:55,124 INFO L435 NwaCegarLoop]: 21 mSDtfsCounter, 52 mSDsluCounter, 121 mSDsCounter, 0 mSdLazyCounter, 237 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 54 SdHoareTripleChecker+Valid, 142 SdHoareTripleChecker+Invalid, 252 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 237 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 00:41:55,124 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [54 Valid, 142 Invalid, 252 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 237 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 00:41:55,124 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2025-03-08 00:41:55,131 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 37. [2025-03-08 00:41:55,132 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 30 states have (on average 1.3666666666666667) internal successors, (41), 30 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-08 00:41:55,133 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 51 transitions. [2025-03-08 00:41:55,134 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 51 transitions. Word has length 31 [2025-03-08 00:41:55,134 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 00:41:55,134 INFO L471 AbstractCegarLoop]: Abstraction has 37 states and 51 transitions. [2025-03-08 00:41:55,134 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 24 states have (on average 1.75) internal successors, (42), 24 states have internal predecessors, (42), 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-08 00:41:55,135 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 51 transitions. [2025-03-08 00:41:55,135 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2025-03-08 00:41:55,135 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 00:41:55,136 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, 1] [2025-03-08 00:41:55,142 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2025-03-08 00:41:55,340 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-08 00:41:55,340 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 00:41:55,340 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 00:41:55,340 INFO L85 PathProgramCache]: Analyzing trace with hash -838694562, now seen corresponding path program 2 times [2025-03-08 00:41:55,340 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 00:41:55,340 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [233807465] [2025-03-08 00:41:55,341 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-08 00:41:55,341 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 00:41:55,349 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 32 statements into 2 equivalence classes. [2025-03-08 00:41:55,359 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 32 of 32 statements. [2025-03-08 00:41:55,359 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-08 00:41:55,359 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:41:55,409 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-08 00:41:55,410 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 00:41:55,410 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [233807465] [2025-03-08 00:41:55,410 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [233807465] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 00:41:55,410 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [597612929] [2025-03-08 00:41:55,410 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-08 00:41:55,410 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 00:41:55,410 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 00:41:55,413 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-08 00:41:55,414 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2025-03-08 00:41:55,446 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 32 statements into 2 equivalence classes. [2025-03-08 00:41:55,459 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 32 of 32 statements. [2025-03-08 00:41:55,459 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-08 00:41:55,459 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:41:55,460 INFO L256 TraceCheckSpWp]: Trace formula consists of 126 conjuncts, 6 conjuncts are in the unsatisfiable core [2025-03-08 00:41:55,461 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 00:41:55,504 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-08 00:41:55,505 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 00:41:55,537 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-08 00:41:55,537 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [597612929] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 00:41:55,537 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-08 00:41:55,537 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 10 [2025-03-08 00:41:55,537 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [573043825] [2025-03-08 00:41:55,537 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-08 00:41:55,539 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2025-03-08 00:41:55,539 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 00:41:55,540 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2025-03-08 00:41:55,540 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=60, Unknown=0, NotChecked=0, Total=90 [2025-03-08 00:41:55,540 INFO L87 Difference]: Start difference. First operand 37 states and 51 transitions. Second operand has 10 states, 10 states have (on average 2.5) internal successors, (25), 10 states have internal predecessors, (25), 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-08 00:41:55,600 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 00:41:55,601 INFO L93 Difference]: Finished difference Result 62 states and 86 transitions. [2025-03-08 00:41:55,601 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-08 00:41:55,601 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.5) internal successors, (25), 10 states have internal predecessors, (25), 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 32 [2025-03-08 00:41:55,601 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 00:41:55,602 INFO L225 Difference]: With dead ends: 62 [2025-03-08 00:41:55,603 INFO L226 Difference]: Without dead ends: 51 [2025-03-08 00:41:55,603 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 70 GetRequests, 58 SyntacticMatches, 3 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 25 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=38, Invalid=72, Unknown=0, NotChecked=0, Total=110 [2025-03-08 00:41:55,604 INFO L435 NwaCegarLoop]: 17 mSDtfsCounter, 8 mSDsluCounter, 56 mSDsCounter, 0 mSdLazyCounter, 60 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 73 SdHoareTripleChecker+Invalid, 73 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 60 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-08 00:41:55,604 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 73 Invalid, 73 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 60 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-08 00:41:55,604 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2025-03-08 00:41:55,609 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 43. [2025-03-08 00:41:55,610 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 43 states, 36 states have (on average 1.3333333333333333) internal successors, (48), 36 states have internal predecessors, (48), 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-08 00:41:55,611 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 58 transitions. [2025-03-08 00:41:55,611 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 58 transitions. Word has length 32 [2025-03-08 00:41:55,611 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 00:41:55,611 INFO L471 AbstractCegarLoop]: Abstraction has 43 states and 58 transitions. [2025-03-08 00:41:55,611 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.5) internal successors, (25), 10 states have internal predecessors, (25), 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-08 00:41:55,612 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 58 transitions. [2025-03-08 00:41:55,613 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2025-03-08 00:41:55,613 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 00:41:55,613 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, 1] [2025-03-08 00:41:55,619 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2025-03-08 00:41:55,813 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-08 00:41:55,814 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 00:41:55,814 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 00:41:55,814 INFO L85 PathProgramCache]: Analyzing trace with hash 1238191095, now seen corresponding path program 3 times [2025-03-08 00:41:55,814 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 00:41:55,814 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2104953404] [2025-03-08 00:41:55,814 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-08 00:41:55,814 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 00:41:55,823 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 41 statements into 4 equivalence classes. [2025-03-08 00:41:55,840 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) and asserted 35 of 41 statements. [2025-03-08 00:41:55,840 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2025-03-08 00:41:55,840 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:41:55,906 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-08 00:41:55,907 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 00:41:55,907 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2104953404] [2025-03-08 00:41:55,907 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2104953404] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 00:41:55,908 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [363923038] [2025-03-08 00:41:55,908 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-08 00:41:55,908 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 00:41:55,908 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 00:41:55,910 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-08 00:41:55,911 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2025-03-08 00:41:55,951 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 41 statements into 4 equivalence classes. [2025-03-08 00:41:55,965 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) and asserted 35 of 41 statements. [2025-03-08 00:41:55,965 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2025-03-08 00:41:55,965 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:41:55,966 INFO L256 TraceCheckSpWp]: Trace formula consists of 134 conjuncts, 6 conjuncts are in the unsatisfiable core [2025-03-08 00:41:55,967 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 00:41:56,011 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-08 00:41:56,011 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 00:41:56,054 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-08 00:41:56,055 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [363923038] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 00:41:56,055 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-08 00:41:56,055 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 10 [2025-03-08 00:41:56,055 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [278152480] [2025-03-08 00:41:56,055 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-08 00:41:56,055 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2025-03-08 00:41:56,055 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 00:41:56,056 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2025-03-08 00:41:56,056 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=31, Invalid=59, Unknown=0, NotChecked=0, Total=90 [2025-03-08 00:41:56,056 INFO L87 Difference]: Start difference. First operand 43 states and 58 transitions. Second operand has 10 states, 10 states have (on average 2.9) internal successors, (29), 10 states have internal predecessors, (29), 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-08 00:41:56,141 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 00:41:56,142 INFO L93 Difference]: Finished difference Result 48 states and 63 transitions. [2025-03-08 00:41:56,142 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-03-08 00:41:56,142 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.9) internal successors, (29), 10 states have internal predecessors, (29), 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 41 [2025-03-08 00:41:56,142 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 00:41:56,143 INFO L225 Difference]: With dead ends: 48 [2025-03-08 00:41:56,143 INFO L226 Difference]: Without dead ends: 43 [2025-03-08 00:41:56,143 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 91 GetRequests, 75 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-08 00:41:56,143 INFO L435 NwaCegarLoop]: 21 mSDtfsCounter, 21 mSDsluCounter, 49 mSDsCounter, 0 mSdLazyCounter, 76 mSolverCounterSat, 20 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 21 SdHoareTripleChecker+Valid, 70 SdHoareTripleChecker+Invalid, 96 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 20 IncrementalHoareTripleChecker+Valid, 76 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 00:41:56,144 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [21 Valid, 70 Invalid, 96 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [20 Valid, 76 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 00:41:56,144 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2025-03-08 00:41:56,148 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 32. [2025-03-08 00:41:56,148 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 26 states have (on average 1.2692307692307692) internal successors, (33), 26 states have internal predecessors, (33), 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-08 00:41:56,149 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 41 transitions. [2025-03-08 00:41:56,149 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 41 transitions. Word has length 41 [2025-03-08 00:41:56,149 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 00:41:56,149 INFO L471 AbstractCegarLoop]: Abstraction has 32 states and 41 transitions. [2025-03-08 00:41:56,149 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.9) internal successors, (29), 10 states have internal predecessors, (29), 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-08 00:41:56,149 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 41 transitions. [2025-03-08 00:41:56,150 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2025-03-08 00:41:56,150 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 00:41:56,150 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, 1] [2025-03-08 00:41:56,156 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2025-03-08 00:41:56,354 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-08 00:41:56,354 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 00:41:56,354 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 00:41:56,354 INFO L85 PathProgramCache]: Analyzing trace with hash 1112850231, now seen corresponding path program 4 times [2025-03-08 00:41:56,355 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 00:41:56,355 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1550818424] [2025-03-08 00:41:56,355 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-08 00:41:56,355 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 00:41:56,362 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 43 statements into 2 equivalence classes. [2025-03-08 00:41:56,383 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 43 of 43 statements. [2025-03-08 00:41:56,383 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-03-08 00:41:56,383 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:41:56,998 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-08 00:41:56,998 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 00:41:56,999 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1550818424] [2025-03-08 00:41:56,999 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1550818424] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 00:41:56,999 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1990195124] [2025-03-08 00:41:56,999 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-08 00:41:56,999 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 00:41:56,999 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 00:41:57,001 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-08 00:41:57,002 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2025-03-08 00:41:57,034 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 43 statements into 2 equivalence classes. [2025-03-08 00:41:57,050 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 43 of 43 statements. [2025-03-08 00:41:57,050 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-03-08 00:41:57,050 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:41:57,051 INFO L256 TraceCheckSpWp]: Trace formula consists of 159 conjuncts, 40 conjuncts are in the unsatisfiable core [2025-03-08 00:41:57,054 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 00:41:57,332 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-08 00:41:57,394 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:41:57,394 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-08 00:41:57,400 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-08 00:41:57,519 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:41:57,520 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-08 00:41:57,546 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-08 00:41:57,546 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 00:41:57,651 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-08 00:41:57,656 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:41:57,656 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-08 00:41:57,851 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:41:57,852 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-08 00:41:57,953 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-08 00:41:57,954 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1990195124] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 00:41:57,954 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-08 00:41:57,954 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 17, 15] total 41 [2025-03-08 00:41:57,954 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2058389876] [2025-03-08 00:41:57,954 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-08 00:41:57,954 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 41 states [2025-03-08 00:41:57,954 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 00:41:57,955 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 41 interpolants. [2025-03-08 00:41:57,955 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=213, Invalid=1427, Unknown=0, NotChecked=0, Total=1640 [2025-03-08 00:41:57,955 INFO L87 Difference]: Start difference. First operand 32 states and 41 transitions. Second operand has 41 states, 41 states have (on average 1.6341463414634145) internal successors, (67), 41 states have internal predecessors, (67), 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-08 00:41:59,042 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 00:41:59,042 INFO L93 Difference]: Finished difference Result 75 states and 102 transitions. [2025-03-08 00:41:59,043 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 40 states. [2025-03-08 00:41:59,043 INFO L78 Accepts]: Start accepts. Automaton has has 41 states, 41 states have (on average 1.6341463414634145) internal successors, (67), 41 states have internal predecessors, (67), 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 43 [2025-03-08 00:41:59,043 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 00:41:59,044 INFO L225 Difference]: With dead ends: 75 [2025-03-08 00:41:59,044 INFO L226 Difference]: Without dead ends: 72 [2025-03-08 00:41:59,045 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 127 GetRequests, 61 SyntacticMatches, 1 SemanticMatches, 65 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1213 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=644, Invalid=3778, Unknown=0, NotChecked=0, Total=4422 [2025-03-08 00:41:59,046 INFO L435 NwaCegarLoop]: 16 mSDtfsCounter, 99 mSDsluCounter, 193 mSDsCounter, 0 mSdLazyCounter, 726 mSolverCounterSat, 60 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 100 SdHoareTripleChecker+Valid, 209 SdHoareTripleChecker+Invalid, 786 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 60 IncrementalHoareTripleChecker+Valid, 726 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2025-03-08 00:41:59,046 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [100 Valid, 209 Invalid, 786 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [60 Valid, 726 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2025-03-08 00:41:59,049 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 72 states. [2025-03-08 00:41:59,057 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 72 to 48. [2025-03-08 00:41:59,058 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 48 states, 40 states have (on average 1.375) internal successors, (55), 40 states have internal predecessors, (55), 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-08 00:41:59,058 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 67 transitions. [2025-03-08 00:41:59,059 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 67 transitions. Word has length 43 [2025-03-08 00:41:59,059 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 00:41:59,059 INFO L471 AbstractCegarLoop]: Abstraction has 48 states and 67 transitions. [2025-03-08 00:41:59,059 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 41 states, 41 states have (on average 1.6341463414634145) internal successors, (67), 41 states have internal predecessors, (67), 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-08 00:41:59,060 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 67 transitions. [2025-03-08 00:41:59,061 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2025-03-08 00:41:59,061 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 00:41:59,061 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, 1] [2025-03-08 00:41:59,067 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2025-03-08 00:41:59,265 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-08 00:41:59,265 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 00:41:59,265 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 00:41:59,265 INFO L85 PathProgramCache]: Analyzing trace with hash 138650546, now seen corresponding path program 5 times [2025-03-08 00:41:59,265 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 00:41:59,265 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [271796284] [2025-03-08 00:41:59,265 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-03-08 00:41:59,265 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 00:41:59,273 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 44 statements into 4 equivalence classes. [2025-03-08 00:41:59,283 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) and asserted 44 of 44 statements. [2025-03-08 00:41:59,283 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2025-03-08 00:41:59,283 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:41:59,342 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-08 00:41:59,342 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 00:41:59,343 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [271796284] [2025-03-08 00:41:59,343 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [271796284] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 00:41:59,343 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1765288747] [2025-03-08 00:41:59,343 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-03-08 00:41:59,343 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 00:41:59,343 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 00:41:59,345 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-08 00:41:59,346 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2025-03-08 00:41:59,377 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 44 statements into 4 equivalence classes. [2025-03-08 00:41:59,396 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) and asserted 44 of 44 statements. [2025-03-08 00:41:59,397 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2025-03-08 00:41:59,397 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:41:59,397 INFO L256 TraceCheckSpWp]: Trace formula consists of 164 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-03-08 00:41:59,399 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 00:41:59,447 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-08 00:41:59,447 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 00:41:59,494 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-08 00:41:59,494 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1765288747] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 00:41:59,494 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-08 00:41:59,494 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9] total 13 [2025-03-08 00:41:59,494 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1961056476] [2025-03-08 00:41:59,495 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-08 00:41:59,495 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2025-03-08 00:41:59,495 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 00:41:59,495 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2025-03-08 00:41:59,495 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=44, Invalid=112, Unknown=0, NotChecked=0, Total=156 [2025-03-08 00:41:59,496 INFO L87 Difference]: Start difference. First operand 48 states and 67 transitions. Second operand has 13 states, 13 states have (on average 2.769230769230769) internal successors, (36), 13 states have internal predecessors, (36), 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-08 00:41:59,579 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 00:41:59,579 INFO L93 Difference]: Finished difference Result 85 states and 119 transitions. [2025-03-08 00:41:59,580 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2025-03-08 00:41:59,580 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 2.769230769230769) internal successors, (36), 13 states have internal predecessors, (36), 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 44 [2025-03-08 00:41:59,580 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 00:41:59,580 INFO L225 Difference]: With dead ends: 85 [2025-03-08 00:41:59,580 INFO L226 Difference]: Without dead ends: 66 [2025-03-08 00:41:59,581 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 98 GetRequests, 78 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-08 00:41:59,581 INFO L435 NwaCegarLoop]: 17 mSDtfsCounter, 14 mSDsluCounter, 61 mSDsCounter, 0 mSdLazyCounter, 96 mSolverCounterSat, 32 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 78 SdHoareTripleChecker+Invalid, 128 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 32 IncrementalHoareTripleChecker+Valid, 96 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 00:41:59,581 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 78 Invalid, 128 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [32 Valid, 96 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 00:41:59,582 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 66 states. [2025-03-08 00:41:59,588 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 66 to 53. [2025-03-08 00:41:59,588 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 53 states, 45 states have (on average 1.3111111111111111) internal successors, (59), 45 states have internal predecessors, (59), 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-08 00:41:59,588 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 71 transitions. [2025-03-08 00:41:59,589 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 71 transitions. Word has length 44 [2025-03-08 00:41:59,589 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 00:41:59,589 INFO L471 AbstractCegarLoop]: Abstraction has 53 states and 71 transitions. [2025-03-08 00:41:59,589 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 2.769230769230769) internal successors, (36), 13 states have internal predecessors, (36), 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-08 00:41:59,589 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 71 transitions. [2025-03-08 00:41:59,589 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2025-03-08 00:41:59,590 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 00:41:59,590 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-08 00:41:59,595 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2025-03-08 00:41:59,794 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-08 00:41:59,794 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 00:41:59,795 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 00:41:59,795 INFO L85 PathProgramCache]: Analyzing trace with hash 1030299430, now seen corresponding path program 6 times [2025-03-08 00:41:59,795 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 00:41:59,795 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [142341150] [2025-03-08 00:41:59,795 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-03-08 00:41:59,795 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 00:41:59,801 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 54 statements into 5 equivalence classes. [2025-03-08 00:41:59,812 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 5 check-sat command(s) and asserted 54 of 54 statements. [2025-03-08 00:41:59,812 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 5 check-sat command(s) [2025-03-08 00:41:59,813 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:41:59,900 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-08 00:41:59,901 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 00:41:59,901 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [142341150] [2025-03-08 00:41:59,901 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [142341150] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 00:41:59,901 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1127538457] [2025-03-08 00:41:59,901 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-03-08 00:41:59,901 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 00:41:59,901 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 00:41:59,903 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-08 00:41:59,905 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2025-03-08 00:41:59,937 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 54 statements into 5 equivalence classes. [2025-03-08 00:41:59,958 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 5 check-sat command(s) and asserted 54 of 54 statements. [2025-03-08 00:41:59,958 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 5 check-sat command(s) [2025-03-08 00:41:59,958 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:41:59,959 INFO L256 TraceCheckSpWp]: Trace formula consists of 192 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-03-08 00:41:59,960 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 00:42:00,011 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-08 00:42:00,012 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 00:42:00,075 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-08 00:42:00,075 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1127538457] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 00:42:00,075 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-08 00:42:00,075 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9] total 14 [2025-03-08 00:42:00,075 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1867605652] [2025-03-08 00:42:00,075 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-08 00:42:00,076 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2025-03-08 00:42:00,076 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 00:42:00,076 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2025-03-08 00:42:00,076 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=53, Invalid=129, Unknown=0, NotChecked=0, Total=182 [2025-03-08 00:42:00,076 INFO L87 Difference]: Start difference. First operand 53 states and 71 transitions. Second operand has 14 states, 14 states have (on average 3.0) internal successors, (42), 14 states have internal predecessors, (42), 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-08 00:42:00,201 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 00:42:00,201 INFO L93 Difference]: Finished difference Result 59 states and 77 transitions. [2025-03-08 00:42:00,202 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2025-03-08 00:42:00,202 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 3.0) internal successors, (42), 14 states have internal predecessors, (42), 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 54 [2025-03-08 00:42:00,202 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 00:42:00,203 INFO L225 Difference]: With dead ends: 59 [2025-03-08 00:42:00,203 INFO L226 Difference]: Without dead ends: 56 [2025-03-08 00:42:00,203 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 121 GetRequests, 97 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-08 00:42:00,203 INFO L435 NwaCegarLoop]: 25 mSDtfsCounter, 28 mSDsluCounter, 102 mSDsCounter, 0 mSdLazyCounter, 182 mSolverCounterSat, 35 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 28 SdHoareTripleChecker+Valid, 127 SdHoareTripleChecker+Invalid, 217 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 35 IncrementalHoareTripleChecker+Valid, 182 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 00:42:00,204 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [28 Valid, 127 Invalid, 217 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [35 Valid, 182 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 00:42:00,204 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 56 states. [2025-03-08 00:42:00,209 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 56 to 40. [2025-03-08 00:42:00,210 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 40 states, 33 states have (on average 1.2727272727272727) internal successors, (42), 33 states have internal predecessors, (42), 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-08 00:42:00,210 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 40 states to 40 states and 52 transitions. [2025-03-08 00:42:00,210 INFO L78 Accepts]: Start accepts. Automaton has 40 states and 52 transitions. Word has length 54 [2025-03-08 00:42:00,210 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 00:42:00,210 INFO L471 AbstractCegarLoop]: Abstraction has 40 states and 52 transitions. [2025-03-08 00:42:00,211 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 3.0) internal successors, (42), 14 states have internal predecessors, (42), 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-08 00:42:00,211 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 52 transitions. [2025-03-08 00:42:00,211 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2025-03-08 00:42:00,211 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 00:42:00,211 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, 1] [2025-03-08 00:42:00,217 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2025-03-08 00:42:00,411 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-08 00:42:00,412 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 00:42:00,412 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 00:42:00,413 INFO L85 PathProgramCache]: Analyzing trace with hash 1874543011, now seen corresponding path program 7 times [2025-03-08 00:42:00,413 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 00:42:00,413 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [967276207] [2025-03-08 00:42:00,413 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-03-08 00:42:00,413 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 00:42:00,419 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 55 statements into 1 equivalence classes. [2025-03-08 00:42:00,433 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 55 of 55 statements. [2025-03-08 00:42:00,433 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 00:42:00,433 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:42:01,627 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-08 00:42:01,627 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 00:42:01,627 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [967276207] [2025-03-08 00:42:01,627 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [967276207] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 00:42:01,627 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1439429023] [2025-03-08 00:42:01,628 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-03-08 00:42:01,628 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 00:42:01,628 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 00:42:01,630 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-08 00:42:01,632 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-08 00:42:01,668 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 55 statements into 1 equivalence classes. [2025-03-08 00:42:01,686 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 55 of 55 statements. [2025-03-08 00:42:01,686 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 00:42:01,686 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:42:01,687 INFO L256 TraceCheckSpWp]: Trace formula consists of 197 conjuncts, 45 conjuncts are in the unsatisfiable core [2025-03-08 00:42:01,690 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 00:42:02,164 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-08 00:42:02,236 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-08 00:42:02,286 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:42:02,286 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-08 00:42:02,292 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-08 00:42:02,465 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:42:02,466 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-08 00:42:02,487 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-08 00:42:02,488 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 00:42:02,704 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-08 00:42:02,742 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:42:02,743 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-08 00:42:03,184 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:42:03,185 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-08 00:42:03,501 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-08 00:42:03,501 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1439429023] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 00:42:03,501 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-08 00:42:03,502 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 21, 20] total 56 [2025-03-08 00:42:03,502 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [941998568] [2025-03-08 00:42:03,502 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-08 00:42:03,502 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 56 states [2025-03-08 00:42:03,502 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 00:42:03,503 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 56 interpolants. [2025-03-08 00:42:03,503 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=302, Invalid=2778, Unknown=0, NotChecked=0, Total=3080 [2025-03-08 00:42:03,504 INFO L87 Difference]: Start difference. First operand 40 states and 52 transitions. Second operand has 56 states, 56 states have (on average 1.5892857142857142) internal successors, (89), 56 states have internal predecessors, (89), 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-08 00:42:06,761 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 00:42:06,761 INFO L93 Difference]: Finished difference Result 136 states and 179 transitions. [2025-03-08 00:42:06,762 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 68 states. [2025-03-08 00:42:06,762 INFO L78 Accepts]: Start accepts. Automaton has has 56 states, 56 states have (on average 1.5892857142857142) internal successors, (89), 56 states have internal predecessors, (89), 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 55 [2025-03-08 00:42:06,762 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 00:42:06,763 INFO L225 Difference]: With dead ends: 136 [2025-03-08 00:42:06,763 INFO L226 Difference]: Without dead ends: 133 [2025-03-08 00:42:06,765 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 194 GetRequests, 75 SyntacticMatches, 3 SemanticMatches, 116 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4130 ImplicationChecksByTransitivity, 3.8s TimeCoverageRelationStatistics Valid=1617, Invalid=12189, Unknown=0, NotChecked=0, Total=13806 [2025-03-08 00:42:06,766 INFO L435 NwaCegarLoop]: 27 mSDtfsCounter, 188 mSDsluCounter, 395 mSDsCounter, 0 mSdLazyCounter, 1186 mSolverCounterSat, 156 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 189 SdHoareTripleChecker+Valid, 422 SdHoareTripleChecker+Invalid, 1342 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 156 IncrementalHoareTripleChecker+Valid, 1186 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2025-03-08 00:42:06,766 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [189 Valid, 422 Invalid, 1342 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [156 Valid, 1186 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2025-03-08 00:42:06,766 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 133 states. [2025-03-08 00:42:06,780 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 133 to 83. [2025-03-08 00:42:06,780 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 83 states, 70 states have (on average 1.3428571428571427) internal successors, (94), 70 states have internal predecessors, (94), 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-08 00:42:06,781 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 83 states to 83 states and 114 transitions. [2025-03-08 00:42:06,781 INFO L78 Accepts]: Start accepts. Automaton has 83 states and 114 transitions. Word has length 55 [2025-03-08 00:42:06,781 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 00:42:06,781 INFO L471 AbstractCegarLoop]: Abstraction has 83 states and 114 transitions. [2025-03-08 00:42:06,782 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 56 states, 56 states have (on average 1.5892857142857142) internal successors, (89), 56 states have internal predecessors, (89), 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-08 00:42:06,782 INFO L276 IsEmpty]: Start isEmpty. Operand 83 states and 114 transitions. [2025-03-08 00:42:06,782 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2025-03-08 00:42:06,782 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 00:42:06,782 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, 1] [2025-03-08 00:42:06,788 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-08 00:42:06,982 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-08 00:42:06,983 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 00:42:06,983 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 00:42:06,983 INFO L85 PathProgramCache]: Analyzing trace with hash 1581140004, now seen corresponding path program 1 times [2025-03-08 00:42:06,983 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 00:42:06,983 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1215689935] [2025-03-08 00:42:06,983 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 00:42:06,983 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 00:42:06,989 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 55 statements into 1 equivalence classes. [2025-03-08 00:42:06,998 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 55 of 55 statements. [2025-03-08 00:42:06,999 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 00:42:06,999 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:42:07,993 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-08 00:42:07,994 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 00:42:07,994 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1215689935] [2025-03-08 00:42:07,994 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1215689935] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 00:42:07,994 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [155154302] [2025-03-08 00:42:07,994 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 00:42:07,994 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 00:42:07,994 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 00:42:07,996 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-08 00:42:07,996 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-08 00:42:08,033 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 55 statements into 1 equivalence classes. [2025-03-08 00:42:08,050 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 55 of 55 statements. [2025-03-08 00:42:08,050 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 00:42:08,050 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:42:08,052 INFO L256 TraceCheckSpWp]: Trace formula consists of 193 conjuncts, 46 conjuncts are in the unsatisfiable core [2025-03-08 00:42:08,054 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 00:42:08,457 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-08 00:42:08,518 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-08 00:42:08,573 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:42:08,573 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-08 00:42:08,581 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-08 00:42:08,733 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:42:08,733 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-08 00:42:08,759 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-08 00:42:08,760 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 00:42:08,938 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-08 00:42:08,960 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:42:08,961 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-08 00:42:09,342 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:42:09,343 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-08 00:42:09,600 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-08 00:42:09,600 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [155154302] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 00:42:09,600 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-08 00:42:09,600 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [23, 21, 20] total 57 [2025-03-08 00:42:09,600 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1606279374] [2025-03-08 00:42:09,600 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-08 00:42:09,601 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 57 states [2025-03-08 00:42:09,601 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 00:42:09,601 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 57 interpolants. [2025-03-08 00:42:09,602 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=294, Invalid=2898, Unknown=0, NotChecked=0, Total=3192 [2025-03-08 00:42:09,602 INFO L87 Difference]: Start difference. First operand 83 states and 114 transitions. Second operand has 57 states, 57 states have (on average 1.5614035087719298) internal successors, (89), 57 states have internal predecessors, (89), 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-08 00:42:11,746 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 00:42:11,746 INFO L93 Difference]: Finished difference Result 138 states and 185 transitions. [2025-03-08 00:42:11,747 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 47 states. [2025-03-08 00:42:11,747 INFO L78 Accepts]: Start accepts. Automaton has has 57 states, 57 states have (on average 1.5614035087719298) internal successors, (89), 57 states have internal predecessors, (89), 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 55 [2025-03-08 00:42:11,747 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 00:42:11,748 INFO L225 Difference]: With dead ends: 138 [2025-03-08 00:42:11,748 INFO L226 Difference]: Without dead ends: 135 [2025-03-08 00:42:11,750 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 172 GetRequests, 75 SyntacticMatches, 2 SemanticMatches, 95 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2551 ImplicationChecksByTransitivity, 2.6s TimeCoverageRelationStatistics Valid=1044, Invalid=8268, Unknown=0, NotChecked=0, Total=9312 [2025-03-08 00:42:11,750 INFO L435 NwaCegarLoop]: 28 mSDtfsCounter, 144 mSDsluCounter, 591 mSDsCounter, 0 mSdLazyCounter, 1528 mSolverCounterSat, 103 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 145 SdHoareTripleChecker+Valid, 619 SdHoareTripleChecker+Invalid, 1631 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 103 IncrementalHoareTripleChecker+Valid, 1528 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2025-03-08 00:42:11,750 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [145 Valid, 619 Invalid, 1631 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [103 Valid, 1528 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2025-03-08 00:42:11,751 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 135 states. [2025-03-08 00:42:11,771 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 135 to 77. [2025-03-08 00:42:11,774 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 77 states, 65 states have (on average 1.323076923076923) internal successors, (86), 65 states have internal predecessors, (86), 9 states have call successors, (9), 2 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-08 00:42:11,774 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 77 states to 77 states and 104 transitions. [2025-03-08 00:42:11,775 INFO L78 Accepts]: Start accepts. Automaton has 77 states and 104 transitions. Word has length 55 [2025-03-08 00:42:11,775 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 00:42:11,775 INFO L471 AbstractCegarLoop]: Abstraction has 77 states and 104 transitions. [2025-03-08 00:42:11,775 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 57 states, 57 states have (on average 1.5614035087719298) internal successors, (89), 57 states have internal predecessors, (89), 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-08 00:42:11,775 INFO L276 IsEmpty]: Start isEmpty. Operand 77 states and 104 transitions. [2025-03-08 00:42:11,776 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2025-03-08 00:42:11,776 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 00:42:11,776 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, 1] [2025-03-08 00:42:11,785 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2025-03-08 00:42:11,976 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-08 00:42:11,976 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 00:42:11,977 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 00:42:11,977 INFO L85 PathProgramCache]: Analyzing trace with hash -1175659804, now seen corresponding path program 2 times [2025-03-08 00:42:11,977 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 00:42:11,977 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1162778614] [2025-03-08 00:42:11,977 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-08 00:42:11,977 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 00:42:11,985 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 55 statements into 2 equivalence classes. [2025-03-08 00:42:12,003 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 55 of 55 statements. [2025-03-08 00:42:12,004 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-08 00:42:12,004 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:42:12,873 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-08 00:42:12,873 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 00:42:12,873 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1162778614] [2025-03-08 00:42:12,873 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1162778614] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 00:42:12,873 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1082672903] [2025-03-08 00:42:12,873 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-08 00:42:12,873 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 00:42:12,873 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 00:42:12,875 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-08 00:42:12,876 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-08 00:42:12,911 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 55 statements into 2 equivalence classes. [2025-03-08 00:42:12,926 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 55 of 55 statements. [2025-03-08 00:42:12,926 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-08 00:42:12,926 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:42:12,927 INFO L256 TraceCheckSpWp]: Trace formula consists of 193 conjuncts, 43 conjuncts are in the unsatisfiable core [2025-03-08 00:42:12,929 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 00:42:13,271 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-08 00:42:13,313 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-08 00:42:13,360 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:42:13,361 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-08 00:42:13,367 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-08 00:42:13,498 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:42:13,498 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-08 00:42:13,533 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-08 00:42:13,533 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 00:42:13,720 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-08 00:42:13,735 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:42:13,735 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-08 00:42:14,124 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:42:14,124 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-08 00:42:14,351 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-08 00:42:14,352 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1082672903] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 00:42:14,352 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-08 00:42:14,352 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 20, 20] total 56 [2025-03-08 00:42:14,352 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1766729681] [2025-03-08 00:42:14,352 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-08 00:42:14,352 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 56 states [2025-03-08 00:42:14,352 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 00:42:14,353 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 56 interpolants. [2025-03-08 00:42:14,353 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=289, Invalid=2791, Unknown=0, NotChecked=0, Total=3080 [2025-03-08 00:42:14,353 INFO L87 Difference]: Start difference. First operand 77 states and 104 transitions. Second operand has 56 states, 56 states have (on average 1.5357142857142858) internal successors, (86), 56 states have internal predecessors, (86), 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-08 00:42:18,037 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 00:42:18,038 INFO L93 Difference]: Finished difference Result 190 states and 262 transitions. [2025-03-08 00:42:18,038 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 85 states. [2025-03-08 00:42:18,038 INFO L78 Accepts]: Start accepts. Automaton has has 56 states, 56 states have (on average 1.5357142857142858) internal successors, (86), 56 states have internal predecessors, (86), 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 55 [2025-03-08 00:42:18,038 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 00:42:18,039 INFO L225 Difference]: With dead ends: 190 [2025-03-08 00:42:18,039 INFO L226 Difference]: Without dead ends: 187 [2025-03-08 00:42:18,042 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 205 GetRequests, 76 SyntacticMatches, 2 SemanticMatches, 127 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5155 ImplicationChecksByTransitivity, 3.9s TimeCoverageRelationStatistics Valid=1934, Invalid=14578, Unknown=0, NotChecked=0, Total=16512 [2025-03-08 00:42:18,043 INFO L435 NwaCegarLoop]: 29 mSDtfsCounter, 244 mSDsluCounter, 454 mSDsCounter, 0 mSdLazyCounter, 1482 mSolverCounterSat, 213 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 244 SdHoareTripleChecker+Valid, 483 SdHoareTripleChecker+Invalid, 1695 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 213 IncrementalHoareTripleChecker+Valid, 1482 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2025-03-08 00:42:18,043 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [244 Valid, 483 Invalid, 1695 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [213 Valid, 1482 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2025-03-08 00:42:18,043 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 187 states. [2025-03-08 00:42:18,073 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 187 to 113. [2025-03-08 00:42:18,074 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 113 states, 95 states have (on average 1.4) internal successors, (133), 95 states have internal predecessors, (133), 15 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2025-03-08 00:42:18,074 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 113 states to 113 states and 163 transitions. [2025-03-08 00:42:18,074 INFO L78 Accepts]: Start accepts. Automaton has 113 states and 163 transitions. Word has length 55 [2025-03-08 00:42:18,075 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 00:42:18,075 INFO L471 AbstractCegarLoop]: Abstraction has 113 states and 163 transitions. [2025-03-08 00:42:18,075 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 56 states, 56 states have (on average 1.5357142857142858) internal successors, (86), 56 states have internal predecessors, (86), 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-08 00:42:18,075 INFO L276 IsEmpty]: Start isEmpty. Operand 113 states and 163 transitions. [2025-03-08 00:42:18,075 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2025-03-08 00:42:18,075 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 00:42:18,076 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, 1] [2025-03-08 00:42:18,081 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-08 00:42:18,276 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-08 00:42:18,276 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 00:42:18,276 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 00:42:18,277 INFO L85 PathProgramCache]: Analyzing trace with hash -1469062811, now seen corresponding path program 3 times [2025-03-08 00:42:18,277 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 00:42:18,277 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [629309204] [2025-03-08 00:42:18,277 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-08 00:42:18,277 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 00:42:18,282 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 55 statements into 5 equivalence classes. [2025-03-08 00:42:18,303 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) and asserted 55 of 55 statements. [2025-03-08 00:42:18,304 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2025-03-08 00:42:18,305 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:42:18,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-08 00:42:18,917 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 00:42:18,917 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [629309204] [2025-03-08 00:42:18,917 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [629309204] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 00:42:18,917 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [941214238] [2025-03-08 00:42:18,917 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-08 00:42:18,917 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 00:42:18,917 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 00:42:18,920 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-08 00:42:18,921 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-08 00:42:18,958 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 55 statements into 5 equivalence classes. [2025-03-08 00:42:18,980 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) and asserted 55 of 55 statements. [2025-03-08 00:42:18,981 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2025-03-08 00:42:18,981 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:42:18,982 INFO L256 TraceCheckSpWp]: Trace formula consists of 189 conjuncts, 52 conjuncts are in the unsatisfiable core [2025-03-08 00:42:18,985 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 00:42:19,321 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-08 00:42:19,367 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-08 00:42:19,422 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:42:19,422 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-08 00:42:19,426 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:42:19,427 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-08 00:42:19,571 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:42:19,571 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-08 00:42:19,616 INFO L134 CoverageAnalysis]: Checked inductivity of 73 backedges. 6 proven. 39 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2025-03-08 00:42:19,616 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 00:42:19,840 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-08 00:42:19,845 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:42:19,845 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-08 00:42:20,280 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 00:42:20,281 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-08 00:42:20,533 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-08 00:42:20,533 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [941214238] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 00:42:20,533 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-08 00:42:20,533 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 22, 20] total 58 [2025-03-08 00:42:20,533 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1347356590] [2025-03-08 00:42:20,533 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-08 00:42:20,534 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 58 states [2025-03-08 00:42:20,534 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 00:42:20,534 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 58 interpolants. [2025-03-08 00:42:20,535 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=375, Invalid=2931, Unknown=0, NotChecked=0, Total=3306 [2025-03-08 00:42:20,535 INFO L87 Difference]: Start difference. First operand 113 states and 163 transitions. Second operand has 58 states, 58 states have (on average 1.5172413793103448) internal successors, (88), 58 states have internal predecessors, (88), 11 states have call successors, (12), 1 states have call predecessors, (12), 2 states have return successors, (12), 11 states have call predecessors, (12), 11 states have call successors, (12) [2025-03-08 00:42:22,186 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 00:42:22,186 INFO L93 Difference]: Finished difference Result 169 states and 241 transitions. [2025-03-08 00:42:22,186 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 42 states. [2025-03-08 00:42:22,186 INFO L78 Accepts]: Start accepts. Automaton has has 58 states, 58 states have (on average 1.5172413793103448) internal successors, (88), 58 states have internal predecessors, (88), 11 states have call successors, (12), 1 states have call predecessors, (12), 2 states have return successors, (12), 11 states have call predecessors, (12), 11 states have call successors, (12) Word has length 55 [2025-03-08 00:42:22,186 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 00:42:22,187 INFO L225 Difference]: With dead ends: 169 [2025-03-08 00:42:22,187 INFO L226 Difference]: Without dead ends: 158 [2025-03-08 00:42:22,188 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 157 GetRequests, 74 SyntacticMatches, 0 SemanticMatches, 83 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1648 ImplicationChecksByTransitivity, 2.2s TimeCoverageRelationStatistics Valid=1031, Invalid=6109, Unknown=0, NotChecked=0, Total=7140 [2025-03-08 00:42:22,188 INFO L435 NwaCegarLoop]: 18 mSDtfsCounter, 113 mSDsluCounter, 360 mSDsCounter, 0 mSdLazyCounter, 1421 mSolverCounterSat, 153 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 113 SdHoareTripleChecker+Valid, 378 SdHoareTripleChecker+Invalid, 1574 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 153 IncrementalHoareTripleChecker+Valid, 1421 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2025-03-08 00:42:22,188 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [113 Valid, 378 Invalid, 1574 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [153 Valid, 1421 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2025-03-08 00:42:22,189 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 158 states. [2025-03-08 00:42:22,214 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 158 to 89. [2025-03-08 00:42:22,214 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 89 states, 75 states have (on average 1.36) internal successors, (102), 75 states have internal predecessors, (102), 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-08 00:42:22,215 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 89 states to 89 states and 124 transitions. [2025-03-08 00:42:22,215 INFO L78 Accepts]: Start accepts. Automaton has 89 states and 124 transitions. Word has length 55 [2025-03-08 00:42:22,215 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 00:42:22,215 INFO L471 AbstractCegarLoop]: Abstraction has 89 states and 124 transitions. [2025-03-08 00:42:22,215 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 58 states, 58 states have (on average 1.5172413793103448) internal successors, (88), 58 states have internal predecessors, (88), 11 states have call successors, (12), 1 states have call predecessors, (12), 2 states have return successors, (12), 11 states have call predecessors, (12), 11 states have call successors, (12) [2025-03-08 00:42:22,215 INFO L276 IsEmpty]: Start isEmpty. Operand 89 states and 124 transitions. [2025-03-08 00:42:22,215 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 58 [2025-03-08 00:42:22,215 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 00:42:22,216 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, 1] [2025-03-08 00:42:22,222 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2025-03-08 00:42:22,420 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-08 00:42:22,420 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 00:42:22,420 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 00:42:22,420 INFO L85 PathProgramCache]: Analyzing trace with hash 1780908515, now seen corresponding path program 8 times [2025-03-08 00:42:22,420 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 00:42:22,420 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1869216186] [2025-03-08 00:42:22,420 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-08 00:42:22,420 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 00:42:22,426 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 57 statements into 2 equivalence classes. [2025-03-08 00:42:22,431 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 57 of 57 statements. [2025-03-08 00:42:22,431 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-08 00:42:22,431 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:42:22,501 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-08 00:42:22,501 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 00:42:22,502 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1869216186] [2025-03-08 00:42:22,502 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1869216186] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 00:42:22,502 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1018898206] [2025-03-08 00:42:22,502 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-08 00:42:22,502 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 00:42:22,502 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 00:42:22,504 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-08 00:42:22,505 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-08 00:42:22,547 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 57 statements into 2 equivalence classes. [2025-03-08 00:42:22,565 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 57 of 57 statements. [2025-03-08 00:42:22,565 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-08 00:42:22,565 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:42:22,566 INFO L256 TraceCheckSpWp]: Trace formula consists of 209 conjuncts, 10 conjuncts are in the unsatisfiable core [2025-03-08 00:42:22,567 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 00:42:22,624 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-08 00:42:22,624 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 00:42:22,678 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-08 00:42:22,678 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1018898206] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 00:42:22,678 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-08 00:42:22,678 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10, 10] total 16 [2025-03-08 00:42:22,679 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1856241624] [2025-03-08 00:42:22,679 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-08 00:42:22,679 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2025-03-08 00:42:22,679 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 00:42:22,679 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2025-03-08 00:42:22,679 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=68, Invalid=172, Unknown=0, NotChecked=0, Total=240 [2025-03-08 00:42:22,680 INFO L87 Difference]: Start difference. First operand 89 states and 124 transitions. Second operand has 16 states, 16 states have (on average 2.8125) internal successors, (45), 16 states have internal predecessors, (45), 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-08 00:42:22,787 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 00:42:22,787 INFO L93 Difference]: Finished difference Result 139 states and 194 transitions. [2025-03-08 00:42:22,787 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-03-08 00:42:22,787 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 2.8125) internal successors, (45), 16 states have internal predecessors, (45), 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 57 [2025-03-08 00:42:22,787 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 00:42:22,788 INFO L225 Difference]: With dead ends: 139 [2025-03-08 00:42:22,788 INFO L226 Difference]: Without dead ends: 119 [2025-03-08 00:42:22,788 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 125 GetRequests, 102 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-08 00:42:22,789 INFO L435 NwaCegarLoop]: 19 mSDtfsCounter, 18 mSDsluCounter, 74 mSDsCounter, 0 mSdLazyCounter, 105 mSolverCounterSat, 18 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 93 SdHoareTripleChecker+Invalid, 123 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 18 IncrementalHoareTripleChecker+Valid, 105 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 00:42:22,789 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 93 Invalid, 123 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [18 Valid, 105 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 00:42:22,789 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 119 states. [2025-03-08 00:42:22,815 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 119 to 99. [2025-03-08 00:42:22,815 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 99 states, 84 states have (on average 1.3452380952380953) internal successors, (113), 84 states have internal predecessors, (113), 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-08 00:42:22,818 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 99 states to 99 states and 137 transitions. [2025-03-08 00:42:22,819 INFO L78 Accepts]: Start accepts. Automaton has 99 states and 137 transitions. Word has length 57 [2025-03-08 00:42:22,819 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 00:42:22,819 INFO L471 AbstractCegarLoop]: Abstraction has 99 states and 137 transitions. [2025-03-08 00:42:22,820 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 2.8125) internal successors, (45), 16 states have internal predecessors, (45), 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-08 00:42:22,820 INFO L276 IsEmpty]: Start isEmpty. Operand 99 states and 137 transitions. [2025-03-08 00:42:22,820 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 68 [2025-03-08 00:42:22,820 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 00:42:22,820 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, 1] [2025-03-08 00:42:22,827 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-08 00:42:23,025 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-08 00:42:23,025 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 00:42:23,025 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 00:42:23,026 INFO L85 PathProgramCache]: Analyzing trace with hash -1405875505, now seen corresponding path program 9 times [2025-03-08 00:42:23,026 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 00:42:23,026 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1672826954] [2025-03-08 00:42:23,026 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-08 00:42:23,026 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 00:42:23,044 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 67 statements into 6 equivalence classes. [2025-03-08 00:42:23,059 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) and asserted 59 of 67 statements. [2025-03-08 00:42:23,059 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2025-03-08 00:42:23,059 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:42:23,920 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-08 00:42:23,920 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 00:42:23,920 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1672826954] [2025-03-08 00:42:23,920 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1672826954] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 00:42:23,920 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1952122266] [2025-03-08 00:42:23,920 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-08 00:42:23,921 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 00:42:23,921 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 00:42:23,922 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-08 00:42:23,923 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-08 00:42:23,963 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 67 statements into 6 equivalence classes. [2025-03-08 00:42:23,984 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) and asserted 59 of 67 statements. [2025-03-08 00:42:23,984 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2025-03-08 00:42:23,984 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 00:42:23,985 INFO L256 TraceCheckSpWp]: Trace formula consists of 194 conjuncts, 58 conjuncts are in the unsatisfiable core [2025-03-08 00:42:23,987 INFO L279 TraceCheckSpWp]: Computing forward predicates...