./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/array-patterns/array2_pattern.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 8fc3dc66 Calling Ultimate with: /root/.sdkman/candidates/java/21.0.5-tem/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/array-patterns/array2_pattern.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 1a25becec148beba97bef86c2a84619bb26dfafe7c127e8d70246837f0d2d470 --- Real Ultimate output --- This is Ultimate 0.3.0-?-8fc3dc6-m [2025-03-16 13:49:22,845 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-16 13:49:22,896 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2025-03-16 13:49:22,902 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-16 13:49:22,902 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-16 13:49:22,920 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-16 13:49:22,921 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-16 13:49:22,921 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-16 13:49:22,922 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-16 13:49:22,922 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-16 13:49:22,923 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-03-16 13:49:22,923 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-03-16 13:49:22,923 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-16 13:49:22,923 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-16 13:49:22,923 INFO L153 SettingsManager]: * Use SBE=true [2025-03-16 13:49:22,924 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-16 13:49:22,924 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-03-16 13:49:22,924 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-16 13:49:22,924 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-16 13:49:22,924 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-16 13:49:22,924 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-16 13:49:22,924 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-03-16 13:49:22,924 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-03-16 13:49:22,925 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-03-16 13:49:22,925 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-16 13:49:22,925 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-16 13:49:22,925 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-16 13:49:22,925 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-16 13:49:22,925 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-16 13:49:22,925 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-16 13:49:22,925 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-03-16 13:49:22,925 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-03-16 13:49:22,926 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-16 13:49:22,926 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-16 13:49:22,926 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-03-16 13:49:22,926 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-03-16 13:49:22,926 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-03-16 13:49:22,926 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-16 13:49:22,926 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-03-16 13:49:22,926 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-03-16 13:49:22,926 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-03-16 13:49:22,926 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-03-16 13:49:22,926 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-03-16 13:49:22,926 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 -> 1a25becec148beba97bef86c2a84619bb26dfafe7c127e8d70246837f0d2d470 [2025-03-16 13:49:23,128 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-16 13:49:23,133 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-16 13:49:23,136 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-16 13:49:23,136 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-16 13:49:23,136 INFO L274 PluginConnector]: CDTParser initialized [2025-03-16 13:49:23,137 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/array-patterns/array2_pattern.c [2025-03-16 13:49:24,217 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/7eea58f89/1f33c9a394e74936836de4a9e9710890/FLAG44790ae6e [2025-03-16 13:49:24,447 INFO L384 CDTParser]: Found 1 translation units. [2025-03-16 13:49:24,448 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/array-patterns/array2_pattern.c [2025-03-16 13:49:24,454 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/7eea58f89/1f33c9a394e74936836de4a9e9710890/FLAG44790ae6e [2025-03-16 13:49:24,797 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/7eea58f89/1f33c9a394e74936836de4a9e9710890 [2025-03-16 13:49:24,799 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-16 13:49:24,800 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-16 13:49:24,801 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-16 13:49:24,801 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-16 13:49:24,804 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-16 13:49:24,805 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.03 01:49:24" (1/1) ... [2025-03-16 13:49:24,805 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@189c1b86 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:49:24, skipping insertion in model container [2025-03-16 13:49:24,806 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.03 01:49:24" (1/1) ... [2025-03-16 13:49:24,815 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-16 13:49:24,911 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-patterns/array2_pattern.c[1322,1335] [2025-03-16 13:49:24,927 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-16 13:49:24,934 INFO L200 MainTranslator]: Completed pre-run [2025-03-16 13:49:24,941 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-patterns/array2_pattern.c[1322,1335] [2025-03-16 13:49:24,949 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-16 13:49:24,961 INFO L204 MainTranslator]: Completed translation [2025-03-16 13:49:24,962 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:49:24 WrapperNode [2025-03-16 13:49:24,962 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-16 13:49:24,963 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-16 13:49:24,963 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-16 13:49:24,963 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-16 13:49:24,967 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:49:24" (1/1) ... [2025-03-16 13:49:24,972 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:49:24" (1/1) ... [2025-03-16 13:49:24,985 INFO L138 Inliner]: procedures = 16, calls = 24, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 73 [2025-03-16 13:49:24,985 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-16 13:49:24,985 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-16 13:49:24,985 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-16 13:49:24,985 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-16 13:49:24,991 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:49:24" (1/1) ... [2025-03-16 13:49:24,991 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:49:24" (1/1) ... [2025-03-16 13:49:24,996 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:49:24" (1/1) ... [2025-03-16 13:49:25,007 INFO L175 MemorySlicer]: Split 10 memory accesses to 3 slices as follows [2, 4, 4]. 40 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2, 0, 0]. The 4 writes are split as follows [0, 2, 2]. [2025-03-16 13:49:25,008 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:49:24" (1/1) ... [2025-03-16 13:49:25,009 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:49:24" (1/1) ... [2025-03-16 13:49:25,013 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:49:24" (1/1) ... [2025-03-16 13:49:25,015 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:49:24" (1/1) ... [2025-03-16 13:49:25,016 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:49:24" (1/1) ... [2025-03-16 13:49:25,017 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:49:24" (1/1) ... [2025-03-16 13:49:25,019 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-16 13:49:25,023 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-16 13:49:25,023 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-16 13:49:25,023 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-16 13:49:25,024 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:49:24" (1/1) ... [2025-03-16 13:49:25,027 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-16 13:49:25,034 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:49:25,043 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2025-03-16 13:49:25,046 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2025-03-16 13:49:25,059 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-16 13:49:25,059 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2025-03-16 13:49:25,059 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2025-03-16 13:49:25,059 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-03-16 13:49:25,059 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2025-03-16 13:49:25,059 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2025-03-16 13:49:25,059 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2025-03-16 13:49:25,059 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2025-03-16 13:49:25,059 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2025-03-16 13:49:25,059 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#2 [2025-03-16 13:49:25,059 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-16 13:49:25,059 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-16 13:49:25,059 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2025-03-16 13:49:25,060 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2025-03-16 13:49:25,060 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#2 [2025-03-16 13:49:25,060 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2025-03-16 13:49:25,103 INFO L256 CfgBuilder]: Building ICFG [2025-03-16 13:49:25,104 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-16 13:49:25,209 INFO L1322 $ProcedureCfgBuilder]: dead code at ProgramPoint L41: call ULTIMATE.dealloc(main_~#array1~0#1.base, main_~#array1~0#1.offset);havoc main_~#array1~0#1.base, main_~#array1~0#1.offset;call ULTIMATE.dealloc(main_~#array2~0#1.base, main_~#array2~0#1.offset);havoc main_~#array2~0#1.base, main_~#array2~0#1.offset; [2025-03-16 13:49:25,215 INFO L? ?]: Removed 12 outVars from TransFormulas that were not future-live. [2025-03-16 13:49:25,215 INFO L307 CfgBuilder]: Performing block encoding [2025-03-16 13:49:25,220 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-16 13:49:25,221 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-16 13:49:25,221 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 16.03 01:49:25 BoogieIcfgContainer [2025-03-16 13:49:25,221 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-16 13:49:25,223 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-03-16 13:49:25,223 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-03-16 13:49:25,226 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-03-16 13:49:25,226 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 16.03 01:49:24" (1/3) ... [2025-03-16 13:49:25,226 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@19fb0afd and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.03 01:49:25, skipping insertion in model container [2025-03-16 13:49:25,226 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:49:24" (2/3) ... [2025-03-16 13:49:25,226 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@19fb0afd and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.03 01:49:25, skipping insertion in model container [2025-03-16 13:49:25,227 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 16.03 01:49:25" (3/3) ... [2025-03-16 13:49:25,227 INFO L128 eAbstractionObserver]: Analyzing ICFG array2_pattern.c [2025-03-16 13:49:25,236 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-03-16 13:49:25,237 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG array2_pattern.c that has 2 procedures, 21 locations, 1 initial locations, 3 loop locations, and 1 error locations. [2025-03-16 13:49:25,269 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-03-16 13:49:25,278 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;@523b0b9a, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-03-16 13:49:25,279 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-03-16 13:49:25,281 INFO L276 IsEmpty]: Start isEmpty. Operand has 21 states, 16 states have (on average 1.4375) internal successors, (23), 17 states have internal predecessors, (23), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-16 13:49:25,285 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2025-03-16 13:49:25,285 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:49:25,286 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:49:25,286 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:49:25,289 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:49:25,290 INFO L85 PathProgramCache]: Analyzing trace with hash 102592180, now seen corresponding path program 1 times [2025-03-16 13:49:25,295 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:49:25,295 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1284781348] [2025-03-16 13:49:25,295 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 13:49:25,296 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:49:25,340 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 13 statements into 1 equivalence classes. [2025-03-16 13:49:25,350 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 13 of 13 statements. [2025-03-16 13:49:25,350 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 13:49:25,350 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:49:25,386 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-16 13:49:25,386 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:49:25,387 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1284781348] [2025-03-16 13:49:25,387 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1284781348] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 13:49:25,387 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 13:49:25,388 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2025-03-16 13:49:25,389 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1957030165] [2025-03-16 13:49:25,389 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 13:49:25,391 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2025-03-16 13:49:25,391 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:49:25,404 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2025-03-16 13:49:25,404 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-03-16 13:49:25,405 INFO L87 Difference]: Start difference. First operand has 21 states, 16 states have (on average 1.4375) internal successors, (23), 17 states have internal predecessors, (23), 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) Second operand has 2 states, 2 states have (on average 5.5) internal successors, (11), 2 states have internal predecessors, (11), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-03-16 13:49:25,413 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:49:25,414 INFO L93 Difference]: Finished difference Result 40 states and 53 transitions. [2025-03-16 13:49:25,414 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2025-03-16 13:49:25,415 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 5.5) internal successors, (11), 2 states have internal predecessors, (11), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 13 [2025-03-16 13:49:25,415 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:49:25,418 INFO L225 Difference]: With dead ends: 40 [2025-03-16 13:49:25,418 INFO L226 Difference]: Without dead ends: 17 [2025-03-16 13:49:25,420 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-03-16 13:49:25,421 INFO L435 NwaCegarLoop]: 24 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, 24 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-16 13:49:25,422 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 24 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 13:49:25,431 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 17 states. [2025-03-16 13:49:25,439 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 17 to 17. [2025-03-16 13:49:25,439 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 17 states, 13 states have (on average 1.2307692307692308) internal successors, (16), 13 states have internal predecessors, (16), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-16 13:49:25,442 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 17 states to 17 states and 20 transitions. [2025-03-16 13:49:25,443 INFO L78 Accepts]: Start accepts. Automaton has 17 states and 20 transitions. Word has length 13 [2025-03-16 13:49:25,443 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:49:25,443 INFO L471 AbstractCegarLoop]: Abstraction has 17 states and 20 transitions. [2025-03-16 13:49:25,443 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 5.5) internal successors, (11), 2 states have internal predecessors, (11), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-03-16 13:49:25,443 INFO L276 IsEmpty]: Start isEmpty. Operand 17 states and 20 transitions. [2025-03-16 13:49:25,444 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2025-03-16 13:49:25,444 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:49:25,444 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:49:25,444 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2025-03-16 13:49:25,444 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:49:25,444 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:49:25,444 INFO L85 PathProgramCache]: Analyzing trace with hash -1443818119, now seen corresponding path program 1 times [2025-03-16 13:49:25,444 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:49:25,444 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1363732426] [2025-03-16 13:49:25,445 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 13:49:25,445 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:49:25,460 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 20 statements into 1 equivalence classes. [2025-03-16 13:49:25,482 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 20 of 20 statements. [2025-03-16 13:49:25,482 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 13:49:25,482 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:49:25,639 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-16 13:49:25,639 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:49:25,639 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1363732426] [2025-03-16 13:49:25,639 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1363732426] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 13:49:25,639 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 13:49:25,640 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2025-03-16 13:49:25,640 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [498129240] [2025-03-16 13:49:25,640 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 13:49:25,640 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2025-03-16 13:49:25,640 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:49:25,641 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2025-03-16 13:49:25,641 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2025-03-16 13:49:25,641 INFO L87 Difference]: Start difference. First operand 17 states and 20 transitions. Second operand has 4 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-16 13:49:25,654 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:49:25,654 INFO L93 Difference]: Finished difference Result 21 states and 24 transitions. [2025-03-16 13:49:25,655 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2025-03-16 13:49:25,655 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 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 20 [2025-03-16 13:49:25,655 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:49:25,655 INFO L225 Difference]: With dead ends: 21 [2025-03-16 13:49:25,655 INFO L226 Difference]: Without dead ends: 18 [2025-03-16 13:49:25,655 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2025-03-16 13:49:25,656 INFO L435 NwaCegarLoop]: 18 mSDtfsCounter, 2 mSDsluCounter, 25 mSDsCounter, 0 mSdLazyCounter, 8 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 43 SdHoareTripleChecker+Invalid, 8 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 8 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-16 13:49:25,656 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [2 Valid, 43 Invalid, 8 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 8 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 13:49:25,656 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 18 states. [2025-03-16 13:49:25,658 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 18 to 18. [2025-03-16 13:49:25,658 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 18 states, 14 states have (on average 1.2142857142857142) internal successors, (17), 14 states have internal predecessors, (17), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-16 13:49:25,663 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 18 states to 18 states and 21 transitions. [2025-03-16 13:49:25,663 INFO L78 Accepts]: Start accepts. Automaton has 18 states and 21 transitions. Word has length 20 [2025-03-16 13:49:25,664 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:49:25,664 INFO L471 AbstractCegarLoop]: Abstraction has 18 states and 21 transitions. [2025-03-16 13:49:25,664 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-16 13:49:25,664 INFO L276 IsEmpty]: Start isEmpty. Operand 18 states and 21 transitions. [2025-03-16 13:49:25,664 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2025-03-16 13:49:25,664 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:49:25,664 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:49:25,664 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2025-03-16 13:49:25,664 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:49:25,665 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:49:25,665 INFO L85 PathProgramCache]: Analyzing trace with hash -1808656976, now seen corresponding path program 1 times [2025-03-16 13:49:25,665 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:49:25,665 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1023996009] [2025-03-16 13:49:25,665 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 13:49:25,665 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:49:25,681 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 21 statements into 1 equivalence classes. [2025-03-16 13:49:25,697 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 21 of 21 statements. [2025-03-16 13:49:25,697 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 13:49:25,697 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:49:25,802 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-16 13:49:25,802 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:49:25,802 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1023996009] [2025-03-16 13:49:25,802 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1023996009] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 13:49:25,802 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 13:49:25,802 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-16 13:49:25,802 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1167702354] [2025-03-16 13:49:25,802 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 13:49:25,803 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-16 13:49:25,803 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:49:25,803 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-16 13:49:25,803 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2025-03-16 13:49:25,803 INFO L87 Difference]: Start difference. First operand 18 states and 21 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-16 13:49:25,838 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:49:25,838 INFO L93 Difference]: Finished difference Result 33 states and 38 transitions. [2025-03-16 13:49:25,839 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-16 13:49:25,839 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 5 states have internal predecessors, (14), 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 21 [2025-03-16 13:49:25,839 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:49:25,839 INFO L225 Difference]: With dead ends: 33 [2025-03-16 13:49:25,839 INFO L226 Difference]: Without dead ends: 19 [2025-03-16 13:49:25,840 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2025-03-16 13:49:25,840 INFO L435 NwaCegarLoop]: 18 mSDtfsCounter, 5 mSDsluCounter, 24 mSDsCounter, 0 mSdLazyCounter, 24 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 42 SdHoareTripleChecker+Invalid, 25 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 24 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-16 13:49:25,841 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 42 Invalid, 25 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 24 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 13:49:25,841 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 19 states. [2025-03-16 13:49:25,845 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 19 to 19. [2025-03-16 13:49:25,848 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 19 states, 15 states have (on average 1.2) internal successors, (18), 15 states have internal predecessors, (18), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-16 13:49:25,848 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 19 states to 19 states and 22 transitions. [2025-03-16 13:49:25,848 INFO L78 Accepts]: Start accepts. Automaton has 19 states and 22 transitions. Word has length 21 [2025-03-16 13:49:25,848 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:49:25,848 INFO L471 AbstractCegarLoop]: Abstraction has 19 states and 22 transitions. [2025-03-16 13:49:25,848 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-16 13:49:25,848 INFO L276 IsEmpty]: Start isEmpty. Operand 19 states and 22 transitions. [2025-03-16 13:49:25,848 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2025-03-16 13:49:25,849 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:49:25,849 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:49:25,849 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2025-03-16 13:49:25,849 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:49:25,849 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:49:25,849 INFO L85 PathProgramCache]: Analyzing trace with hash -1645261099, now seen corresponding path program 1 times [2025-03-16 13:49:25,849 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:49:25,849 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1674562301] [2025-03-16 13:49:25,849 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 13:49:25,849 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:49:25,860 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 22 statements into 1 equivalence classes. [2025-03-16 13:49:25,882 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 22 of 22 statements. [2025-03-16 13:49:25,883 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 13:49:25,883 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 13:49:25,886 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2101306385] [2025-03-16 13:49:25,886 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 13:49:25,886 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:49:25,886 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:49:25,888 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 13:49:25,890 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2025-03-16 13:49:25,928 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 22 statements into 1 equivalence classes. [2025-03-16 13:49:25,951 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 22 of 22 statements. [2025-03-16 13:49:25,951 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 13:49:25,951 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:49:25,956 INFO L256 TraceCheckSpWp]: Trace formula consists of 110 conjuncts, 43 conjuncts are in the unsatisfiable core [2025-03-16 13:49:25,961 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:49:26,064 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-16 13:49:26,071 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-16 13:49:26,388 INFO L349 Elim1Store]: treesize reduction 25, result has 21.9 percent of original size [2025-03-16 13:49:26,388 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 26 treesize of output 21 [2025-03-16 13:49:26,408 INFO L349 Elim1Store]: treesize reduction 25, result has 21.9 percent of original size [2025-03-16 13:49:26,408 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 26 treesize of output 21 [2025-03-16 13:49:26,548 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 4 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-16 13:49:26,549 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:49:27,626 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:49:27,627 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1674562301] [2025-03-16 13:49:27,628 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 13:49:27,628 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2101306385] [2025-03-16 13:49:27,628 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2101306385] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:49:27,628 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-16 13:49:27,628 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16] total 16 [2025-03-16 13:49:27,628 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1237065175] [2025-03-16 13:49:27,628 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-16 13:49:27,629 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2025-03-16 13:49:27,629 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:49:27,630 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2025-03-16 13:49:27,631 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=73, Invalid=347, Unknown=0, NotChecked=0, Total=420 [2025-03-16 13:49:27,631 INFO L87 Difference]: Start difference. First operand 19 states and 22 transitions. Second operand has 16 states, 16 states have (on average 1.125) internal successors, (18), 13 states have internal predecessors, (18), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-16 13:49:28,075 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:49:28,075 INFO L93 Difference]: Finished difference Result 45 states and 50 transitions. [2025-03-16 13:49:28,076 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2025-03-16 13:49:28,076 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 1.125) internal successors, (18), 13 states have internal predecessors, (18), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 22 [2025-03-16 13:49:28,076 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:49:28,076 INFO L225 Difference]: With dead ends: 45 [2025-03-16 13:49:28,077 INFO L226 Difference]: Without dead ends: 42 [2025-03-16 13:49:28,077 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 36 GetRequests, 10 SyntacticMatches, 0 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 150 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=135, Invalid=621, Unknown=0, NotChecked=0, Total=756 [2025-03-16 13:49:28,078 INFO L435 NwaCegarLoop]: 15 mSDtfsCounter, 45 mSDsluCounter, 76 mSDsCounter, 0 mSdLazyCounter, 112 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 45 SdHoareTripleChecker+Valid, 91 SdHoareTripleChecker+Invalid, 127 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 112 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 13:49:28,079 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [45 Valid, 91 Invalid, 127 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 112 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 13:49:28,079 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states. [2025-03-16 13:49:28,085 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 34. [2025-03-16 13:49:28,087 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 34 states, 27 states have (on average 1.1851851851851851) internal successors, (32), 27 states have internal predecessors, (32), 3 states have call successors, (3), 3 states have call predecessors, (3), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2025-03-16 13:49:28,087 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 38 transitions. [2025-03-16 13:49:28,087 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 38 transitions. Word has length 22 [2025-03-16 13:49:28,088 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:49:28,088 INFO L471 AbstractCegarLoop]: Abstraction has 34 states and 38 transitions. [2025-03-16 13:49:28,089 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 1.125) internal successors, (18), 13 states have internal predecessors, (18), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-16 13:49:28,089 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 38 transitions. [2025-03-16 13:49:28,089 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2025-03-16 13:49:28,089 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:49:28,090 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:49:28,096 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2025-03-16 13:49:28,290 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:49:28,290 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:49:28,291 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:49:28,291 INFO L85 PathProgramCache]: Analyzing trace with hash -874956208, now seen corresponding path program 2 times [2025-03-16 13:49:28,291 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:49:28,291 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1271114924] [2025-03-16 13:49:28,291 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 13:49:28,291 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:49:28,299 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 23 statements into 2 equivalence classes. [2025-03-16 13:49:28,312 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 23 of 23 statements. [2025-03-16 13:49:28,314 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 13:49:28,314 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:49:28,396 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-16 13:49:28,397 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:49:28,397 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1271114924] [2025-03-16 13:49:28,397 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1271114924] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:49:28,397 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [592059057] [2025-03-16 13:49:28,397 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 13:49:28,397 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:49:28,398 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:49:28,399 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 13:49:28,401 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2025-03-16 13:49:28,432 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 23 statements into 2 equivalence classes. [2025-03-16 13:49:28,444 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 23 of 23 statements. [2025-03-16 13:49:28,445 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 13:49:28,445 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:49:28,445 INFO L256 TraceCheckSpWp]: Trace formula consists of 121 conjuncts, 6 conjuncts are in the unsatisfiable core [2025-03-16 13:49:28,446 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:49:28,483 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 5 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-16 13:49:28,483 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:49:28,522 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 1 proven. 3 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-16 13:49:28,522 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [592059057] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 13:49:28,522 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 13:49:28,522 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 11 [2025-03-16 13:49:28,522 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [719556849] [2025-03-16 13:49:28,522 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 13:49:28,523 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2025-03-16 13:49:28,523 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:49:28,523 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2025-03-16 13:49:28,523 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=75, Unknown=0, NotChecked=0, Total=110 [2025-03-16 13:49:28,523 INFO L87 Difference]: Start difference. First operand 34 states and 38 transitions. Second operand has 11 states, 11 states have (on average 2.3636363636363638) internal successors, (26), 11 states have internal predecessors, (26), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-16 13:49:28,600 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:49:28,601 INFO L93 Difference]: Finished difference Result 39 states and 43 transitions. [2025-03-16 13:49:28,601 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2025-03-16 13:49:28,601 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 2.3636363636363638) internal successors, (26), 11 states have internal predecessors, (26), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 23 [2025-03-16 13:49:28,601 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:49:28,601 INFO L225 Difference]: With dead ends: 39 [2025-03-16 13:49:28,602 INFO L226 Difference]: Without dead ends: 36 [2025-03-16 13:49:28,602 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 53 GetRequests, 38 SyntacticMatches, 4 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 35 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=48, Invalid=108, Unknown=0, NotChecked=0, Total=156 [2025-03-16 13:49:28,602 INFO L435 NwaCegarLoop]: 24 mSDtfsCounter, 4 mSDsluCounter, 106 mSDsCounter, 0 mSdLazyCounter, 97 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 130 SdHoareTripleChecker+Invalid, 101 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 97 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 13:49:28,603 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 130 Invalid, 101 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 97 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 13:49:28,603 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36 states. [2025-03-16 13:49:28,606 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36 to 24. [2025-03-16 13:49:28,606 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24 states, 19 states have (on average 1.1578947368421053) internal successors, (22), 19 states have internal predecessors, (22), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-16 13:49:28,606 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 26 transitions. [2025-03-16 13:49:28,607 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 26 transitions. Word has length 23 [2025-03-16 13:49:28,607 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:49:28,607 INFO L471 AbstractCegarLoop]: Abstraction has 24 states and 26 transitions. [2025-03-16 13:49:28,607 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 2.3636363636363638) internal successors, (26), 11 states have internal predecessors, (26), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-16 13:49:28,607 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 26 transitions. [2025-03-16 13:49:28,609 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2025-03-16 13:49:28,609 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:49:28,610 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:49:28,615 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-16 13:49:28,810 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:49:28,810 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:49:28,811 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:49:28,811 INFO L85 PathProgramCache]: Analyzing trace with hash 536545236, now seen corresponding path program 3 times [2025-03-16 13:49:28,811 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:49:28,811 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [328188216] [2025-03-16 13:49:28,811 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 13:49:28,811 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:49:28,817 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 23 statements into 3 equivalence classes. [2025-03-16 13:49:28,826 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) and asserted 23 of 23 statements. [2025-03-16 13:49:28,826 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2025-03-16 13:49:28,826 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:49:28,892 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-16 13:49:28,892 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:49:28,892 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [328188216] [2025-03-16 13:49:28,893 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [328188216] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:49:28,893 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1107175701] [2025-03-16 13:49:28,893 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 13:49:28,893 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:49:28,893 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:49:28,894 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 13:49:28,896 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2025-03-16 13:49:28,927 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 23 statements into 3 equivalence classes. [2025-03-16 13:49:28,950 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) and asserted 23 of 23 statements. [2025-03-16 13:49:28,951 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2025-03-16 13:49:28,951 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:49:28,951 INFO L256 TraceCheckSpWp]: Trace formula consists of 115 conjuncts, 6 conjuncts are in the unsatisfiable core [2025-03-16 13:49:28,952 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:49:28,986 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 7 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-16 13:49:28,986 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:49:29,018 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 3 proven. 1 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-16 13:49:29,018 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1107175701] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 13:49:29,018 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 13:49:29,018 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 11 [2025-03-16 13:49:29,019 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1366797200] [2025-03-16 13:49:29,019 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 13:49:29,019 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2025-03-16 13:49:29,019 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:49:29,019 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2025-03-16 13:49:29,020 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=75, Unknown=0, NotChecked=0, Total=110 [2025-03-16 13:49:29,020 INFO L87 Difference]: Start difference. First operand 24 states and 26 transitions. Second operand has 11 states, 11 states have (on average 2.3636363636363638) internal successors, (26), 11 states have internal predecessors, (26), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-16 13:49:29,069 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:49:29,070 INFO L93 Difference]: Finished difference Result 40 states and 44 transitions. [2025-03-16 13:49:29,070 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2025-03-16 13:49:29,070 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 2.3636363636363638) internal successors, (26), 11 states have internal predecessors, (26), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 23 [2025-03-16 13:49:29,070 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:49:29,071 INFO L225 Difference]: With dead ends: 40 [2025-03-16 13:49:29,071 INFO L226 Difference]: Without dead ends: 25 [2025-03-16 13:49:29,071 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 52 GetRequests, 39 SyntacticMatches, 3 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 39 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=43, Invalid=89, Unknown=0, NotChecked=0, Total=132 [2025-03-16 13:49:29,071 INFO L435 NwaCegarLoop]: 18 mSDtfsCounter, 1 mSDsluCounter, 73 mSDsCounter, 0 mSdLazyCounter, 67 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 91 SdHoareTripleChecker+Invalid, 70 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 67 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-16 13:49:29,071 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 91 Invalid, 70 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 67 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 13:49:29,072 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states. [2025-03-16 13:49:29,075 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 25. [2025-03-16 13:49:29,075 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 25 states, 20 states have (on average 1.15) internal successors, (23), 20 states have internal predecessors, (23), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-16 13:49:29,078 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 25 states to 25 states and 27 transitions. [2025-03-16 13:49:29,079 INFO L78 Accepts]: Start accepts. Automaton has 25 states and 27 transitions. Word has length 23 [2025-03-16 13:49:29,079 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:49:29,079 INFO L471 AbstractCegarLoop]: Abstraction has 25 states and 27 transitions. [2025-03-16 13:49:29,079 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 2.3636363636363638) internal successors, (26), 11 states have internal predecessors, (26), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-16 13:49:29,079 INFO L276 IsEmpty]: Start isEmpty. Operand 25 states and 27 transitions. [2025-03-16 13:49:29,079 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2025-03-16 13:49:29,079 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:49:29,079 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:49:29,085 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-16 13:49:29,279 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:49:29,280 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:49:29,280 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:49:29,280 INFO L85 PathProgramCache]: Analyzing trace with hash -1353806919, now seen corresponding path program 4 times [2025-03-16 13:49:29,280 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:49:29,280 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1135075810] [2025-03-16 13:49:29,280 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-16 13:49:29,280 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:49:29,286 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 24 statements into 2 equivalence classes. [2025-03-16 13:49:29,317 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 24 of 24 statements. [2025-03-16 13:49:29,317 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-03-16 13:49:29,317 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 13:49:29,318 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2101981576] [2025-03-16 13:49:29,318 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-16 13:49:29,318 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:49:29,318 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:49:29,320 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 13:49:29,321 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2025-03-16 13:49:29,354 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 24 statements into 2 equivalence classes. [2025-03-16 13:49:29,376 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 24 of 24 statements. [2025-03-16 13:49:29,376 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-03-16 13:49:29,377 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:49:29,378 INFO L256 TraceCheckSpWp]: Trace formula consists of 126 conjuncts, 47 conjuncts are in the unsatisfiable core [2025-03-16 13:49:29,384 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:49:29,421 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-16 13:49:29,429 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-16 13:49:29,466 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 19 treesize of output 18 [2025-03-16 13:49:29,476 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 19 treesize of output 18 [2025-03-16 13:49:29,795 INFO L349 Elim1Store]: treesize reduction 12, result has 60.0 percent of original size [2025-03-16 13:49:29,795 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 130 treesize of output 123 [2025-03-16 13:49:29,866 INFO L349 Elim1Store]: treesize reduction 133, result has 23.1 percent of original size [2025-03-16 13:49:29,866 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 5 select indices, 5 select index equivalence classes, 1 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 14 case distinctions, treesize of input 50 treesize of output 63 [2025-03-16 13:49:29,917 INFO L349 Elim1Store]: treesize reduction 94, result has 1.1 percent of original size [2025-03-16 13:49:29,917 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 2 stores, 4 select indices, 4 select index equivalence classes, 4 disjoint index pairs (out of 6 index pairs), introduced 6 new quantified variables, introduced 4 case distinctions, treesize of input 96 treesize of output 157 [2025-03-16 13:49:30,408 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:49:30,409 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 185 treesize of output 169 [2025-03-16 13:49:30,416 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 116 treesize of output 100 [2025-03-16 13:49:30,422 INFO L173 IndexEqualityManager]: detected equality via solver [2025-03-16 13:49:30,423 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-16 13:49:30,424 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-16 13:49:30,425 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-16 13:49:30,426 INFO L173 IndexEqualityManager]: detected equality via solver [2025-03-16 13:49:30,427 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 31 treesize of output 19 [2025-03-16 13:49:30,448 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 4 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-16 13:49:30,448 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:49:31,882 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:49:31,882 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1135075810] [2025-03-16 13:49:31,882 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 13:49:31,882 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2101981576] [2025-03-16 13:49:31,882 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2101981576] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:49:31,882 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-16 13:49:31,882 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2025-03-16 13:49:31,882 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [497727817] [2025-03-16 13:49:31,882 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-16 13:49:31,883 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2025-03-16 13:49:31,883 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:49:31,883 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2025-03-16 13:49:31,883 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=77, Invalid=343, Unknown=0, NotChecked=0, Total=420 [2025-03-16 13:49:31,884 INFO L87 Difference]: Start difference. First operand 25 states and 27 transitions. Second operand has 16 states, 16 states have (on average 1.25) internal successors, (20), 13 states have internal predecessors, (20), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-16 13:49:32,058 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:49:32,058 INFO L93 Difference]: Finished difference Result 44 states and 49 transitions. [2025-03-16 13:49:32,058 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2025-03-16 13:49:32,059 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 1.25) internal successors, (20), 13 states have internal predecessors, (20), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 24 [2025-03-16 13:49:32,059 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:49:32,059 INFO L225 Difference]: With dead ends: 44 [2025-03-16 13:49:32,059 INFO L226 Difference]: Without dead ends: 41 [2025-03-16 13:49:32,059 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 12 SyntacticMatches, 1 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 150 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=92, Invalid=414, Unknown=0, NotChecked=0, Total=506 [2025-03-16 13:49:32,060 INFO L435 NwaCegarLoop]: 14 mSDtfsCounter, 28 mSDsluCounter, 57 mSDsCounter, 0 mSdLazyCounter, 113 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 29 SdHoareTripleChecker+Valid, 71 SdHoareTripleChecker+Invalid, 116 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 113 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 13:49:32,060 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [29 Valid, 71 Invalid, 116 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 113 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 13:49:32,060 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2025-03-16 13:49:32,065 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 36. [2025-03-16 13:49:32,065 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 36 states, 29 states have (on average 1.1724137931034482) internal successors, (34), 29 states have internal predecessors, (34), 3 states have call successors, (3), 3 states have call predecessors, (3), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2025-03-16 13:49:32,066 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 40 transitions. [2025-03-16 13:49:32,066 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 40 transitions. Word has length 24 [2025-03-16 13:49:32,066 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:49:32,066 INFO L471 AbstractCegarLoop]: Abstraction has 36 states and 40 transitions. [2025-03-16 13:49:32,066 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 1.25) internal successors, (20), 13 states have internal predecessors, (20), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-16 13:49:32,066 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 40 transitions. [2025-03-16 13:49:32,067 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2025-03-16 13:49:32,067 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:49:32,067 INFO L218 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:49:32,072 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2025-03-16 13:49:32,271 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:49:32,271 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:49:32,271 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:49:32,271 INFO L85 PathProgramCache]: Analyzing trace with hash 174818420, now seen corresponding path program 5 times [2025-03-16 13:49:32,271 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:49:32,271 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1397907015] [2025-03-16 13:49:32,271 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-03-16 13:49:32,271 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:49:32,280 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 25 statements into 4 equivalence classes. [2025-03-16 13:49:32,291 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) and asserted 25 of 25 statements. [2025-03-16 13:49:32,292 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2025-03-16 13:49:32,292 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:49:32,361 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-16 13:49:32,361 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:49:32,361 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1397907015] [2025-03-16 13:49:32,361 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1397907015] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:49:32,361 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1443999903] [2025-03-16 13:49:32,361 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-03-16 13:49:32,362 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:49:32,362 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:49:32,363 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 13:49:32,365 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2025-03-16 13:49:32,401 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 25 statements into 4 equivalence classes. [2025-03-16 13:49:32,429 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) and asserted 25 of 25 statements. [2025-03-16 13:49:32,429 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2025-03-16 13:49:32,429 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:49:32,430 INFO L256 TraceCheckSpWp]: Trace formula consists of 137 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-03-16 13:49:32,431 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:49:32,462 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 7 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-16 13:49:32,462 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:49:32,499 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-16 13:49:32,499 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1443999903] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 13:49:32,499 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 13:49:32,499 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9] total 12 [2025-03-16 13:49:32,499 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1571949617] [2025-03-16 13:49:32,499 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 13:49:32,499 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2025-03-16 13:49:32,499 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:49:32,500 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2025-03-16 13:49:32,500 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=39, Invalid=93, Unknown=0, NotChecked=0, Total=132 [2025-03-16 13:49:32,500 INFO L87 Difference]: Start difference. First operand 36 states and 40 transitions. Second operand has 12 states, 12 states have (on average 2.0833333333333335) internal successors, (25), 12 states have internal predecessors, (25), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-16 13:49:32,581 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:49:32,581 INFO L93 Difference]: Finished difference Result 57 states and 62 transitions. [2025-03-16 13:49:32,581 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-03-16 13:49:32,581 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 2.0833333333333335) internal successors, (25), 12 states have internal predecessors, (25), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 25 [2025-03-16 13:49:32,581 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:49:32,582 INFO L225 Difference]: With dead ends: 57 [2025-03-16 13:49:32,582 INFO L226 Difference]: Without dead ends: 54 [2025-03-16 13:49:32,582 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 61 GetRequests, 40 SyntacticMatches, 7 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 70 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=73, Invalid=167, Unknown=0, NotChecked=0, Total=240 [2025-03-16 13:49:32,583 INFO L435 NwaCegarLoop]: 24 mSDtfsCounter, 4 mSDsluCounter, 81 mSDsCounter, 0 mSdLazyCounter, 88 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 105 SdHoareTripleChecker+Invalid, 92 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 88 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 13:49:32,583 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 105 Invalid, 92 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 88 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 13:49:32,583 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2025-03-16 13:49:32,594 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 44. [2025-03-16 13:49:32,594 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 44 states, 35 states have (on average 1.1714285714285715) internal successors, (41), 35 states have internal predecessors, (41), 4 states have call successors, (4), 4 states have call predecessors, (4), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2025-03-16 13:49:32,594 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 49 transitions. [2025-03-16 13:49:32,595 INFO L78 Accepts]: Start accepts. Automaton has 44 states and 49 transitions. Word has length 25 [2025-03-16 13:49:32,595 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:49:32,595 INFO L471 AbstractCegarLoop]: Abstraction has 44 states and 49 transitions. [2025-03-16 13:49:32,596 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 2.0833333333333335) internal successors, (25), 12 states have internal predecessors, (25), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-16 13:49:32,596 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 49 transitions. [2025-03-16 13:49:32,597 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2025-03-16 13:49:32,597 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:49:32,597 INFO L218 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:49:32,603 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2025-03-16 13:49:32,797 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:49:32,798 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:49:32,798 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:49:32,798 INFO L85 PathProgramCache]: Analyzing trace with hash 981690224, now seen corresponding path program 6 times [2025-03-16 13:49:32,798 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:49:32,798 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [18247224] [2025-03-16 13:49:32,798 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-03-16 13:49:32,798 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:49:32,803 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 25 statements into 3 equivalence classes. [2025-03-16 13:49:32,810 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 3 check-sat command(s) and asserted 25 of 25 statements. [2025-03-16 13:49:32,810 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 3 check-sat command(s) [2025-03-16 13:49:32,810 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:49:32,885 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 4 proven. 5 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-16 13:49:32,885 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:49:32,885 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [18247224] [2025-03-16 13:49:32,885 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [18247224] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:49:32,885 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1033166375] [2025-03-16 13:49:32,885 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-03-16 13:49:32,885 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:49:32,885 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:49:32,889 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 13:49:32,890 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2025-03-16 13:49:32,921 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 25 statements into 3 equivalence classes. [2025-03-16 13:49:32,941 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 3 check-sat command(s) and asserted 25 of 25 statements. [2025-03-16 13:49:32,941 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 3 check-sat command(s) [2025-03-16 13:49:32,941 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:49:32,942 INFO L256 TraceCheckSpWp]: Trace formula consists of 131 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-03-16 13:49:32,942 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:49:32,979 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 10 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-16 13:49:32,979 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:49:33,014 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 6 proven. 3 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-16 13:49:33,014 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1033166375] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 13:49:33,014 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 13:49:33,014 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9] total 13 [2025-03-16 13:49:33,014 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1906343618] [2025-03-16 13:49:33,014 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 13:49:33,014 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2025-03-16 13:49:33,015 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:49:33,015 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2025-03-16 13:49:33,015 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=47, Invalid=109, Unknown=0, NotChecked=0, Total=156 [2025-03-16 13:49:33,015 INFO L87 Difference]: Start difference. First operand 44 states and 49 transitions. Second operand has 13 states, 13 states have (on average 2.076923076923077) internal successors, (27), 13 states have internal predecessors, (27), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-16 13:49:33,076 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:49:33,076 INFO L93 Difference]: Finished difference Result 58 states and 63 transitions. [2025-03-16 13:49:33,077 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-03-16 13:49:33,077 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 2.076923076923077) internal successors, (27), 13 states have internal predecessors, (27), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 25 [2025-03-16 13:49:33,077 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:49:33,077 INFO L225 Difference]: With dead ends: 58 [2025-03-16 13:49:33,077 INFO L226 Difference]: Without dead ends: 50 [2025-03-16 13:49:33,077 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 59 GetRequests, 41 SyntacticMatches, 5 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 63 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=66, Invalid=144, Unknown=0, NotChecked=0, Total=210 [2025-03-16 13:49:33,078 INFO L435 NwaCegarLoop]: 20 mSDtfsCounter, 4 mSDsluCounter, 99 mSDsCounter, 0 mSdLazyCounter, 86 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 119 SdHoareTripleChecker+Invalid, 92 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 86 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-16 13:49:33,078 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 119 Invalid, 92 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 86 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 13:49:33,078 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2025-03-16 13:49:33,088 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 47. [2025-03-16 13:49:33,088 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 47 states, 38 states have (on average 1.131578947368421) internal successors, (43), 38 states have internal predecessors, (43), 4 states have call successors, (4), 4 states have call predecessors, (4), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2025-03-16 13:49:33,089 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 51 transitions. [2025-03-16 13:49:33,089 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 51 transitions. Word has length 25 [2025-03-16 13:49:33,089 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:49:33,089 INFO L471 AbstractCegarLoop]: Abstraction has 47 states and 51 transitions. [2025-03-16 13:49:33,089 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 2.076923076923077) internal successors, (27), 13 states have internal predecessors, (27), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-16 13:49:33,089 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 51 transitions. [2025-03-16 13:49:33,089 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2025-03-16 13:49:33,089 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:49:33,089 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:49:33,100 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2025-03-16 13:49:33,290 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:49:33,290 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:49:33,290 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:49:33,290 INFO L85 PathProgramCache]: Analyzing trace with hash 1124435477, now seen corresponding path program 7 times [2025-03-16 13:49:33,290 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:49:33,290 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2005701892] [2025-03-16 13:49:33,290 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-03-16 13:49:33,291 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:49:33,298 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 26 statements into 1 equivalence classes. [2025-03-16 13:49:33,340 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 26 of 26 statements. [2025-03-16 13:49:33,343 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 13:49:33,343 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 13:49:33,344 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1548918388] [2025-03-16 13:49:33,345 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-03-16 13:49:33,345 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:49:33,345 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:49:33,347 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 13:49:33,349 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2025-03-16 13:49:33,388 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 26 statements into 1 equivalence classes. [2025-03-16 13:49:33,426 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 26 of 26 statements. [2025-03-16 13:49:33,426 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 13:49:33,426 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:49:33,427 INFO L256 TraceCheckSpWp]: Trace formula consists of 142 conjuncts, 67 conjuncts are in the unsatisfiable core [2025-03-16 13:49:33,430 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:49:33,476 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-16 13:49:33,483 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-16 13:49:33,520 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 19 treesize of output 18 [2025-03-16 13:49:33,529 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 19 treesize of output 18 [2025-03-16 13:49:33,578 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:49:33,578 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 1 case distinctions, treesize of input 26 treesize of output 28 [2025-03-16 13:49:33,589 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:49:33,589 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 1 case distinctions, treesize of input 26 treesize of output 28 [2025-03-16 13:49:34,025 INFO L349 Elim1Store]: treesize reduction 197, result has 23.9 percent of original size [2025-03-16 13:49:34,025 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 7 select indices, 7 select index equivalence classes, 3 disjoint index pairs (out of 21 index pairs), introduced 7 new quantified variables, introduced 27 case distinctions, treesize of input 64 treesize of output 91 [2025-03-16 13:49:34,058 INFO L349 Elim1Store]: treesize reduction 12, result has 60.0 percent of original size [2025-03-16 13:49:34,058 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 201 treesize of output 186 [2025-03-16 13:49:34,106 INFO L349 Elim1Store]: treesize reduction 141, result has 0.7 percent of original size [2025-03-16 13:49:34,106 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 2 stores, 5 select indices, 5 select index equivalence classes, 7 disjoint index pairs (out of 10 index pairs), introduced 7 new quantified variables, introduced 6 case distinctions, treesize of input 101 treesize of output 165 [2025-03-16 13:49:34,128 WARN L214 Elim1Store]: Array PQE input equivalent to false [2025-03-16 13:49:34,856 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:49:34,856 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 300 treesize of output 268 [2025-03-16 13:49:34,863 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 172 treesize of output 148 [2025-03-16 13:49:34,865 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-16 13:49:34,866 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-16 13:49:34,866 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-16 13:49:34,867 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-16 13:49:34,867 INFO L173 IndexEqualityManager]: detected equality via solver [2025-03-16 13:49:34,869 INFO L173 IndexEqualityManager]: detected equality via solver [2025-03-16 13:49:34,869 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 39 treesize of output 23 [2025-03-16 13:49:34,895 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 4 proven. 12 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-16 13:49:34,895 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:49:36,412 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:49:36,412 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2005701892] [2025-03-16 13:49:36,412 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 13:49:36,412 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1548918388] [2025-03-16 13:49:36,412 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1548918388] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:49:36,412 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-16 13:49:36,412 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20] total 20 [2025-03-16 13:49:36,413 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1068688263] [2025-03-16 13:49:36,413 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-16 13:49:36,413 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2025-03-16 13:49:36,413 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:49:36,413 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2025-03-16 13:49:36,414 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=105, Invalid=651, Unknown=0, NotChecked=0, Total=756 [2025-03-16 13:49:36,414 INFO L87 Difference]: Start difference. First operand 47 states and 51 transitions. Second operand has 21 states, 21 states have (on average 1.0476190476190477) internal successors, (22), 17 states have internal predecessors, (22), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-16 13:49:37,500 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:49:37,500 INFO L93 Difference]: Finished difference Result 68 states and 76 transitions. [2025-03-16 13:49:37,500 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2025-03-16 13:49:37,500 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 21 states have (on average 1.0476190476190477) internal successors, (22), 17 states have internal predecessors, (22), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 26 [2025-03-16 13:49:37,501 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:49:37,501 INFO L225 Difference]: With dead ends: 68 [2025-03-16 13:49:37,501 INFO L226 Difference]: Without dead ends: 65 [2025-03-16 13:49:37,502 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 43 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 283 ImplicationChecksByTransitivity, 2.3s TimeCoverageRelationStatistics Valid=168, Invalid=1092, Unknown=0, NotChecked=0, Total=1260 [2025-03-16 13:49:37,502 INFO L435 NwaCegarLoop]: 18 mSDtfsCounter, 57 mSDsluCounter, 115 mSDsCounter, 0 mSdLazyCounter, 245 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 57 SdHoareTripleChecker+Valid, 133 SdHoareTripleChecker+Invalid, 253 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 245 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-16 13:49:37,502 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [57 Valid, 133 Invalid, 253 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 245 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-16 13:49:37,502 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 65 states. [2025-03-16 13:49:37,514 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 65 to 58. [2025-03-16 13:49:37,515 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 58 states, 47 states have (on average 1.148936170212766) internal successors, (54), 47 states have internal predecessors, (54), 5 states have call successors, (5), 5 states have call predecessors, (5), 5 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2025-03-16 13:49:37,516 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 64 transitions. [2025-03-16 13:49:37,516 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 64 transitions. Word has length 26 [2025-03-16 13:49:37,516 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:49:37,517 INFO L471 AbstractCegarLoop]: Abstraction has 58 states and 64 transitions. [2025-03-16 13:49:37,517 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 21 states have (on average 1.0476190476190477) internal successors, (22), 17 states have internal predecessors, (22), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-16 13:49:37,517 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 64 transitions. [2025-03-16 13:49:37,517 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2025-03-16 13:49:37,517 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:49:37,518 INFO L218 NwaCegarLoop]: trace histogram [4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:49:37,524 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2025-03-16 13:49:37,722 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:49:37,722 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:49:37,723 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:49:37,723 INFO L85 PathProgramCache]: Analyzing trace with hash 1254571024, now seen corresponding path program 8 times [2025-03-16 13:49:37,723 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:49:37,723 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1136854457] [2025-03-16 13:49:37,723 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 13:49:37,723 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:49:37,729 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 27 statements into 2 equivalence classes. [2025-03-16 13:49:37,736 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 27 of 27 statements. [2025-03-16 13:49:37,736 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 13:49:37,736 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:49:37,842 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 3 proven. 13 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-16 13:49:37,842 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:49:37,842 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1136854457] [2025-03-16 13:49:37,843 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1136854457] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:49:37,843 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1787966626] [2025-03-16 13:49:37,843 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 13:49:37,843 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:49:37,843 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:49:37,844 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 13:49:37,846 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2025-03-16 13:49:37,885 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 27 statements into 2 equivalence classes. [2025-03-16 13:49:37,901 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 27 of 27 statements. [2025-03-16 13:49:37,901 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 13:49:37,901 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:49:37,902 INFO L256 TraceCheckSpWp]: Trace formula consists of 153 conjuncts, 10 conjuncts are in the unsatisfiable core [2025-03-16 13:49:37,903 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:49:37,959 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 10 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-16 13:49:37,959 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:49:38,017 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 10 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-16 13:49:38,018 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1787966626] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 13:49:38,018 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 13:49:38,018 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11, 11] total 17 [2025-03-16 13:49:38,018 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [508747875] [2025-03-16 13:49:38,019 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 13:49:38,019 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2025-03-16 13:49:38,019 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:49:38,019 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2025-03-16 13:49:38,019 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=75, Invalid=197, Unknown=0, NotChecked=0, Total=272 [2025-03-16 13:49:38,019 INFO L87 Difference]: Start difference. First operand 58 states and 64 transitions. Second operand has 17 states, 17 states have (on average 1.8823529411764706) internal successors, (32), 17 states have internal predecessors, (32), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-16 13:49:38,146 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:49:38,146 INFO L93 Difference]: Finished difference Result 81 states and 88 transitions. [2025-03-16 13:49:38,146 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2025-03-16 13:49:38,147 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 1.8823529411764706) internal successors, (32), 17 states have internal predecessors, (32), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 27 [2025-03-16 13:49:38,147 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:49:38,147 INFO L225 Difference]: With dead ends: 81 [2025-03-16 13:49:38,147 INFO L226 Difference]: Without dead ends: 78 [2025-03-16 13:49:38,147 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 67 GetRequests, 40 SyntacticMatches, 8 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 161 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=113, Invalid=307, Unknown=0, NotChecked=0, Total=420 [2025-03-16 13:49:38,148 INFO L435 NwaCegarLoop]: 24 mSDtfsCounter, 4 mSDsluCounter, 105 mSDsCounter, 0 mSdLazyCounter, 163 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 129 SdHoareTripleChecker+Invalid, 172 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 163 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 13:49:38,148 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 129 Invalid, 172 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 163 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 13:49:38,148 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 78 states. [2025-03-16 13:49:38,159 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 78 to 66. [2025-03-16 13:49:38,159 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 66 states, 53 states have (on average 1.150943396226415) internal successors, (61), 53 states have internal predecessors, (61), 6 states have call successors, (6), 6 states have call predecessors, (6), 6 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2025-03-16 13:49:38,159 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 66 states to 66 states and 73 transitions. [2025-03-16 13:49:38,160 INFO L78 Accepts]: Start accepts. Automaton has 66 states and 73 transitions. Word has length 27 [2025-03-16 13:49:38,160 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:49:38,160 INFO L471 AbstractCegarLoop]: Abstraction has 66 states and 73 transitions. [2025-03-16 13:49:38,160 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 1.8823529411764706) internal successors, (32), 17 states have internal predecessors, (32), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-16 13:49:38,160 INFO L276 IsEmpty]: Start isEmpty. Operand 66 states and 73 transitions. [2025-03-16 13:49:38,160 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2025-03-16 13:49:38,160 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:49:38,160 INFO L218 NwaCegarLoop]: trace histogram [4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:49:38,166 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2025-03-16 13:49:38,361 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,SelfDestructingSolverStorable10 [2025-03-16 13:49:38,361 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:49:38,361 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:49:38,361 INFO L85 PathProgramCache]: Analyzing trace with hash 497793172, now seen corresponding path program 9 times [2025-03-16 13:49:38,361 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:49:38,361 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [628525633] [2025-03-16 13:49:38,361 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 13:49:38,362 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:49:38,366 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 27 statements into 4 equivalence classes. [2025-03-16 13:49:38,382 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) and asserted 27 of 27 statements. [2025-03-16 13:49:38,382 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2025-03-16 13:49:38,382 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:49:38,479 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 7 proven. 9 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-16 13:49:38,479 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:49:38,479 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [628525633] [2025-03-16 13:49:38,479 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [628525633] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:49:38,479 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [231855705] [2025-03-16 13:49:38,479 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 13:49:38,480 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:49:38,480 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:49:38,481 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 13:49:38,483 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2025-03-16 13:49:38,518 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 27 statements into 4 equivalence classes. [2025-03-16 13:49:38,555 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) and asserted 27 of 27 statements. [2025-03-16 13:49:38,555 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2025-03-16 13:49:38,555 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:49:38,556 INFO L256 TraceCheckSpWp]: Trace formula consists of 147 conjuncts, 10 conjuncts are in the unsatisfiable core [2025-03-16 13:49:38,557 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:49:38,603 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 14 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-16 13:49:38,603 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:49:38,646 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 10 proven. 6 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-16 13:49:38,646 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [231855705] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 13:49:38,646 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 13:49:38,646 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11, 11] total 17 [2025-03-16 13:49:38,646 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1423383574] [2025-03-16 13:49:38,646 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 13:49:38,647 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2025-03-16 13:49:38,647 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:49:38,647 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2025-03-16 13:49:38,647 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=75, Invalid=197, Unknown=0, NotChecked=0, Total=272 [2025-03-16 13:49:38,647 INFO L87 Difference]: Start difference. First operand 66 states and 73 transitions. Second operand has 17 states, 17 states have (on average 1.8823529411764706) internal successors, (32), 17 states have internal predecessors, (32), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-16 13:49:38,713 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:49:38,713 INFO L93 Difference]: Finished difference Result 82 states and 89 transitions. [2025-03-16 13:49:38,713 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2025-03-16 13:49:38,713 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 1.8823529411764706) internal successors, (32), 17 states have internal predecessors, (32), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 27 [2025-03-16 13:49:38,713 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:49:38,714 INFO L225 Difference]: With dead ends: 82 [2025-03-16 13:49:38,714 INFO L226 Difference]: Without dead ends: 73 [2025-03-16 13:49:38,714 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 66 GetRequests, 41 SyntacticMatches, 7 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 156 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=108, Invalid=272, Unknown=0, NotChecked=0, Total=380 [2025-03-16 13:49:38,714 INFO L435 NwaCegarLoop]: 20 mSDtfsCounter, 5 mSDsluCounter, 97 mSDsCounter, 0 mSdLazyCounter, 98 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 117 SdHoareTripleChecker+Invalid, 109 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 98 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-16 13:49:38,714 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 117 Invalid, 109 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 98 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 13:49:38,715 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 73 states. [2025-03-16 13:49:38,726 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 73 to 67. [2025-03-16 13:49:38,726 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 67 states, 54 states have (on average 1.1296296296296295) internal successors, (61), 54 states have internal predecessors, (61), 6 states have call successors, (6), 6 states have call predecessors, (6), 6 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2025-03-16 13:49:38,727 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 67 states to 67 states and 73 transitions. [2025-03-16 13:49:38,727 INFO L78 Accepts]: Start accepts. Automaton has 67 states and 73 transitions. Word has length 27 [2025-03-16 13:49:38,727 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:49:38,727 INFO L471 AbstractCegarLoop]: Abstraction has 67 states and 73 transitions. [2025-03-16 13:49:38,727 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 1.8823529411764706) internal successors, (32), 17 states have internal predecessors, (32), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-16 13:49:38,727 INFO L276 IsEmpty]: Start isEmpty. Operand 67 states and 73 transitions. [2025-03-16 13:49:38,727 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2025-03-16 13:49:38,727 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:49:38,727 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:49:38,734 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2025-03-16 13:49:38,928 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:49:38,928 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:49:38,928 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:49:38,928 INFO L85 PathProgramCache]: Analyzing trace with hash 237027833, now seen corresponding path program 10 times [2025-03-16 13:49:38,928 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:49:38,928 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [757245493] [2025-03-16 13:49:38,928 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-16 13:49:38,929 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:49:38,935 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 28 statements into 2 equivalence classes. [2025-03-16 13:49:38,952 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 28 of 28 statements. [2025-03-16 13:49:38,952 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-03-16 13:49:38,952 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 13:49:38,953 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [45148462] [2025-03-16 13:49:38,953 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-16 13:49:38,953 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:49:38,953 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:49:38,955 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 13:49:38,956 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2025-03-16 13:49:38,997 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 28 statements into 2 equivalence classes. [2025-03-16 13:49:39,089 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 28 of 28 statements. [2025-03-16 13:49:39,089 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-03-16 13:49:39,090 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:49:39,097 INFO L256 TraceCheckSpWp]: Trace formula consists of 158 conjuncts, 66 conjuncts are in the unsatisfiable core [2025-03-16 13:49:39,099 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:49:39,122 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-16 13:49:39,126 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-16 13:49:39,146 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 21 treesize of output 20 [2025-03-16 13:49:39,155 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 21 treesize of output 20 [2025-03-16 13:49:39,180 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:49:39,180 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 30 treesize of output 32 [2025-03-16 13:49:39,193 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:49:39,193 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 30 treesize of output 32 [2025-03-16 13:49:39,230 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:49:39,230 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 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 39 treesize of output 44 [2025-03-16 13:49:39,245 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:49:39,246 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 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 39 treesize of output 44 [2025-03-16 13:49:39,897 INFO L349 Elim1Store]: treesize reduction 481, result has 22.3 percent of original size [2025-03-16 13:49:39,897 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 9 select indices, 9 select index equivalence classes, 0 disjoint index pairs (out of 36 index pairs), introduced 9 new quantified variables, introduced 44 case distinctions, treesize of input 94 treesize of output 175 [2025-03-16 13:49:39,946 INFO L349 Elim1Store]: treesize reduction 12, result has 60.0 percent of original size [2025-03-16 13:49:39,947 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 236 treesize of output 217 [2025-03-16 13:49:40,327 INFO L349 Elim1Store]: treesize reduction 718, result has 19.4 percent of original size [2025-03-16 13:49:40,328 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 2 stores, 10 select indices, 10 select index equivalence classes, 0 disjoint index pairs (out of 45 index pairs), introduced 12 new quantified variables, introduced 57 case distinctions, treesize of input 185 treesize of output 416 [2025-03-16 13:49:41,334 INFO L349 Elim1Store]: treesize reduction 197, result has 25.7 percent of original size [2025-03-16 13:49:41,334 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 6 select indices, 6 select index equivalence classes, 0 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 19 case distinctions, treesize of input 152 treesize of output 119 [2025-03-16 13:50:02,723 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:50:02,724 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 247 treesize of output 171 [2025-03-16 13:50:02,728 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:50:02,728 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 172 treesize of output 86 [2025-03-16 13:50:02,756 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 4 proven. 20 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-16 13:50:02,756 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:50:05,341 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:50:05,341 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [757245493] [2025-03-16 13:50:05,341 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 13:50:05,341 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [45148462] [2025-03-16 13:50:05,341 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [45148462] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:50:05,341 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-16 13:50:05,341 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20] total 20 [2025-03-16 13:50:05,341 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1522277044] [2025-03-16 13:50:05,341 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-16 13:50:05,341 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2025-03-16 13:50:05,341 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:50:05,342 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2025-03-16 13:50:05,342 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=112, Invalid=639, Unknown=5, NotChecked=0, Total=756 [2025-03-16 13:50:05,342 INFO L87 Difference]: Start difference. First operand 67 states and 73 transitions. Second operand has 21 states, 21 states have (on average 1.1428571428571428) internal successors, (24), 18 states have internal predecessors, (24), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-16 13:50:13,699 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-03-16 13:50:17,705 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-03-16 13:50:21,725 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-03-16 13:50:25,737 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-03-16 13:50:29,745 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-03-16 13:50:33,765 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-03-16 13:50:37,784 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-03-16 13:50:41,888 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.08s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-03-16 13:50:45,905 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-03-16 13:50:49,933 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-03-16 13:50:49,995 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:50:49,995 INFO L93 Difference]: Finished difference Result 89 states and 98 transitions. [2025-03-16 13:50:49,996 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2025-03-16 13:50:49,996 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 21 states have (on average 1.1428571428571428) internal successors, (24), 18 states have internal predecessors, (24), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 28 [2025-03-16 13:50:49,996 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:50:49,997 INFO L225 Difference]: With dead ends: 89 [2025-03-16 13:50:49,997 INFO L226 Difference]: Without dead ends: 86 [2025-03-16 13:50:49,997 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 41 GetRequests, 11 SyntacticMatches, 2 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 1 DeprecatedPredicates, 265 ImplicationChecksByTransitivity, 26.8s TimeCoverageRelationStatistics Valid=130, Invalid=735, Unknown=5, NotChecked=0, Total=870 [2025-03-16 13:50:49,997 INFO L435 NwaCegarLoop]: 17 mSDtfsCounter, 29 mSDsluCounter, 160 mSDsCounter, 0 mSdLazyCounter, 334 mSolverCounterSat, 4 mSolverCounterUnsat, 10 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 40.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 29 SdHoareTripleChecker+Valid, 177 SdHoareTripleChecker+Invalid, 348 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 334 IncrementalHoareTripleChecker+Invalid, 10 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 40.6s IncrementalHoareTripleChecker+Time [2025-03-16 13:50:49,997 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [29 Valid, 177 Invalid, 348 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 334 Invalid, 10 Unknown, 0 Unchecked, 40.6s Time] [2025-03-16 13:50:49,998 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 86 states. [2025-03-16 13:50:50,014 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 86 to 78. [2025-03-16 13:50:50,014 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 78 states, 63 states have (on average 1.1428571428571428) internal successors, (72), 63 states have internal predecessors, (72), 7 states have call successors, (7), 7 states have call predecessors, (7), 7 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2025-03-16 13:50:50,014 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 78 states to 78 states and 86 transitions. [2025-03-16 13:50:50,014 INFO L78 Accepts]: Start accepts. Automaton has 78 states and 86 transitions. Word has length 28 [2025-03-16 13:50:50,015 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:50:50,015 INFO L471 AbstractCegarLoop]: Abstraction has 78 states and 86 transitions. [2025-03-16 13:50:50,015 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 21 states have (on average 1.1428571428571428) internal successors, (24), 18 states have internal predecessors, (24), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-16 13:50:50,015 INFO L276 IsEmpty]: Start isEmpty. Operand 78 states and 86 transitions. [2025-03-16 13:50:50,015 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2025-03-16 13:50:50,015 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:50:50,015 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:50:50,022 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2025-03-16 13:50:50,216 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,SelfDestructingSolverStorable12 [2025-03-16 13:50:50,216 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:50:50,216 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:50:50,216 INFO L85 PathProgramCache]: Analyzing trace with hash 743236916, now seen corresponding path program 11 times [2025-03-16 13:50:50,217 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:50:50,217 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2049277026] [2025-03-16 13:50:50,217 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-03-16 13:50:50,217 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:50:50,222 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 29 statements into 5 equivalence classes. [2025-03-16 13:50:50,236 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 5 check-sat command(s) and asserted 29 of 29 statements. [2025-03-16 13:50:50,237 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 5 check-sat command(s) [2025-03-16 13:50:50,237 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:50:50,346 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 10 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-16 13:50:50,346 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:50:50,346 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2049277026] [2025-03-16 13:50:50,346 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2049277026] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:50:50,347 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2111594435] [2025-03-16 13:50:50,347 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-03-16 13:50:50,347 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:50:50,347 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:50:50,349 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 13:50:50,350 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2025-03-16 13:50:50,391 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 29 statements into 5 equivalence classes. [2025-03-16 13:50:50,447 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 5 check-sat command(s) and asserted 29 of 29 statements. [2025-03-16 13:50:50,447 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 5 check-sat command(s) [2025-03-16 13:50:50,447 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:50:50,449 INFO L256 TraceCheckSpWp]: Trace formula consists of 169 conjuncts, 12 conjuncts are in the unsatisfiable core [2025-03-16 13:50:50,449 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:50:50,506 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 14 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-16 13:50:50,506 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:50:50,559 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 10 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-16 13:50:50,560 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2111594435] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 13:50:50,560 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 13:50:50,560 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13, 13] total 18 [2025-03-16 13:50:50,560 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1953505696] [2025-03-16 13:50:50,560 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 13:50:50,560 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2025-03-16 13:50:50,560 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:50:50,560 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2025-03-16 13:50:50,560 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=83, Invalid=223, Unknown=0, NotChecked=0, Total=306 [2025-03-16 13:50:50,561 INFO L87 Difference]: Start difference. First operand 78 states and 86 transitions. Second operand has 18 states, 18 states have (on average 1.7222222222222223) internal successors, (31), 18 states have internal predecessors, (31), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-16 13:50:50,673 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:50:50,673 INFO L93 Difference]: Finished difference Result 106 states and 115 transitions. [2025-03-16 13:50:50,673 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2025-03-16 13:50:50,673 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 18 states have (on average 1.7222222222222223) internal successors, (31), 18 states have internal predecessors, (31), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 29 [2025-03-16 13:50:50,673 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:50:50,674 INFO L225 Difference]: With dead ends: 106 [2025-03-16 13:50:50,674 INFO L226 Difference]: Without dead ends: 103 [2025-03-16 13:50:50,674 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 75 GetRequests, 42 SyntacticMatches, 11 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 208 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=152, Invalid=400, Unknown=0, NotChecked=0, Total=552 [2025-03-16 13:50:50,675 INFO L435 NwaCegarLoop]: 24 mSDtfsCounter, 4 mSDsluCounter, 70 mSDsCounter, 0 mSdLazyCounter, 144 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 94 SdHoareTripleChecker+Invalid, 151 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 144 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 13:50:50,675 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 94 Invalid, 151 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 144 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 13:50:50,675 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 103 states. [2025-03-16 13:50:50,692 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 103 to 86. [2025-03-16 13:50:50,692 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 86 states, 69 states have (on average 1.144927536231884) internal successors, (79), 69 states have internal predecessors, (79), 8 states have call successors, (8), 8 states have call predecessors, (8), 8 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2025-03-16 13:50:50,692 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 86 states to 86 states and 95 transitions. [2025-03-16 13:50:50,693 INFO L78 Accepts]: Start accepts. Automaton has 86 states and 95 transitions. Word has length 29 [2025-03-16 13:50:50,693 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:50:50,693 INFO L471 AbstractCegarLoop]: Abstraction has 86 states and 95 transitions. [2025-03-16 13:50:50,693 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 18 states have (on average 1.7222222222222223) internal successors, (31), 18 states have internal predecessors, (31), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-16 13:50:50,693 INFO L276 IsEmpty]: Start isEmpty. Operand 86 states and 95 transitions. [2025-03-16 13:50:50,693 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2025-03-16 13:50:50,693 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:50:50,693 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:50:50,699 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2025-03-16 13:50:50,896 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,SelfDestructingSolverStorable13 [2025-03-16 13:50:50,896 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:50:50,897 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:50:50,897 INFO L85 PathProgramCache]: Analyzing trace with hash -1242040016, now seen corresponding path program 12 times [2025-03-16 13:50:50,897 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:50:50,897 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [112539905] [2025-03-16 13:50:50,897 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-03-16 13:50:50,897 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:50:50,901 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 29 statements into 4 equivalence classes. [2025-03-16 13:50:50,914 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) and asserted 29 of 29 statements. [2025-03-16 13:50:50,914 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2025-03-16 13:50:50,914 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:50:51,027 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 11 proven. 14 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-16 13:50:51,027 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:50:51,027 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [112539905] [2025-03-16 13:50:51,027 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [112539905] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:50:51,027 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [21215843] [2025-03-16 13:50:51,028 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-03-16 13:50:51,028 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:50:51,028 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:50:51,029 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 13:50:51,031 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2025-03-16 13:50:51,076 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 29 statements into 4 equivalence classes. [2025-03-16 13:50:51,145 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) and asserted 29 of 29 statements. [2025-03-16 13:50:51,146 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2025-03-16 13:50:51,146 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:50:51,146 INFO L256 TraceCheckSpWp]: Trace formula consists of 163 conjuncts, 12 conjuncts are in the unsatisfiable core [2025-03-16 13:50:51,147 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:50:51,225 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 19 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-16 13:50:51,226 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:50:51,293 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 15 proven. 10 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-16 13:50:51,293 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [21215843] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 13:50:51,293 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 13:50:51,293 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13, 13] total 20 [2025-03-16 13:50:51,293 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2042346331] [2025-03-16 13:50:51,293 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 13:50:51,293 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2025-03-16 13:50:51,293 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:50:51,294 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2025-03-16 13:50:51,294 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=101, Invalid=279, Unknown=0, NotChecked=0, Total=380 [2025-03-16 13:50:51,294 INFO L87 Difference]: Start difference. First operand 86 states and 95 transitions. Second operand has 20 states, 20 states have (on average 1.75) internal successors, (35), 20 states have internal predecessors, (35), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-16 13:50:51,384 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:50:51,384 INFO L93 Difference]: Finished difference Result 107 states and 116 transitions. [2025-03-16 13:50:51,385 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2025-03-16 13:50:51,386 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 20 states have (on average 1.75) internal successors, (35), 20 states have internal predecessors, (35), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 29 [2025-03-16 13:50:51,386 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:50:51,386 INFO L225 Difference]: With dead ends: 107 [2025-03-16 13:50:51,386 INFO L226 Difference]: Without dead ends: 97 [2025-03-16 13:50:51,386 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 73 GetRequests, 42 SyntacticMatches, 9 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 237 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=151, Invalid=401, Unknown=0, NotChecked=0, Total=552 [2025-03-16 13:50:51,387 INFO L435 NwaCegarLoop]: 20 mSDtfsCounter, 6 mSDsluCounter, 69 mSDsCounter, 0 mSdLazyCounter, 86 mSolverCounterSat, 19 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 89 SdHoareTripleChecker+Invalid, 105 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 19 IncrementalHoareTripleChecker+Valid, 86 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-16 13:50:51,387 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 89 Invalid, 105 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [19 Valid, 86 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 13:50:51,387 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 97 states. [2025-03-16 13:50:51,406 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 97 to 87. [2025-03-16 13:50:51,406 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 87 states, 70 states have (on average 1.1285714285714286) internal successors, (79), 70 states have internal predecessors, (79), 8 states have call successors, (8), 8 states have call predecessors, (8), 8 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2025-03-16 13:50:51,406 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 87 states to 87 states and 95 transitions. [2025-03-16 13:50:51,407 INFO L78 Accepts]: Start accepts. Automaton has 87 states and 95 transitions. Word has length 29 [2025-03-16 13:50:51,407 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:50:51,407 INFO L471 AbstractCegarLoop]: Abstraction has 87 states and 95 transitions. [2025-03-16 13:50:51,407 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 20 states have (on average 1.75) internal successors, (35), 20 states have internal predecessors, (35), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-16 13:50:51,407 INFO L276 IsEmpty]: Start isEmpty. Operand 87 states and 95 transitions. [2025-03-16 13:50:51,407 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2025-03-16 13:50:51,407 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:50:51,407 INFO L218 NwaCegarLoop]: trace histogram [5, 5, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:50:51,414 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-16 13:50:51,607 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,SelfDestructingSolverStorable14 [2025-03-16 13:50:51,608 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:50:51,608 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:50:51,608 INFO L85 PathProgramCache]: Analyzing trace with hash 1565539669, now seen corresponding path program 13 times [2025-03-16 13:50:51,608 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:50:51,608 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1756380241] [2025-03-16 13:50:51,608 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-03-16 13:50:51,608 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:50:51,618 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 30 statements into 1 equivalence classes. [2025-03-16 13:50:51,629 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 30 of 30 statements. [2025-03-16 13:50:51,630 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 13:50:51,630 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 13:50:51,630 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [376578832] [2025-03-16 13:50:51,631 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-03-16 13:50:51,631 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:50:51,631 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:50:51,632 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 13:50:51,634 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2025-03-16 13:50:51,679 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 30 statements into 1 equivalence classes. [2025-03-16 13:50:51,870 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 30 of 30 statements. [2025-03-16 13:50:51,870 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 13:50:51,870 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:50:51,872 INFO L256 TraceCheckSpWp]: Trace formula consists of 174 conjuncts, 86 conjuncts are in the unsatisfiable core [2025-03-16 13:50:51,875 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:50:51,920 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-16 13:50:51,927 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-16 13:50:51,952 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 19 treesize of output 18 [2025-03-16 13:50:51,958 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 19 treesize of output 18 [2025-03-16 13:50:51,995 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:50:51,995 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 1 case distinctions, treesize of input 26 treesize of output 28 [2025-03-16 13:50:52,013 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:50:52,013 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 1 case distinctions, treesize of input 26 treesize of output 28 [2025-03-16 13:50:52,060 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:50:52,060 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 6 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 33 treesize of output 38 [2025-03-16 13:50:52,070 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:50:52,070 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 6 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 33 treesize of output 38 [2025-03-16 13:50:52,123 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:50:52,124 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 10 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 40 treesize of output 48 [2025-03-16 13:50:52,138 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:50:52,139 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 10 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 40 treesize of output 48 [2025-03-16 13:50:52,877 INFO L349 Elim1Store]: treesize reduction 325, result has 24.6 percent of original size [2025-03-16 13:50:52,878 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 11 select indices, 11 select index equivalence classes, 10 disjoint index pairs (out of 55 index pairs), introduced 11 new quantified variables, introduced 65 case distinctions, treesize of input 92 treesize of output 147 [2025-03-16 13:50:52,915 INFO L349 Elim1Store]: treesize reduction 12, result has 60.0 percent of original size [2025-03-16 13:50:52,916 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 172 treesize of output 153 [2025-03-16 13:50:52,978 INFO L349 Elim1Store]: treesize reduction 235, result has 0.4 percent of original size [2025-03-16 13:50:52,978 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 2 stores, 7 select indices, 7 select index equivalence classes, 16 disjoint index pairs (out of 21 index pairs), introduced 9 new quantified variables, introduced 10 case distinctions, treesize of input 111 treesize of output 181 [2025-03-16 13:50:52,988 WARN L214 Elim1Store]: Array PQE input equivalent to false [2025-03-16 13:50:56,896 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 1585 treesize of output 1425 [2025-03-16 13:50:57,352 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:50:57,352 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 9 select indices, 9 select index equivalence classes, 10 disjoint index pairs (out of 36 index pairs), introduced 9 new quantified variables, introduced 36 case distinctions, treesize of input 1432 treesize of output 1720 [2025-03-16 13:50:59,324 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:50:59,325 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 15 select indices, 15 select index equivalence classes, 14 disjoint index pairs (out of 105 index pairs), introduced 15 new quantified variables, introduced 91 case distinctions, treesize of input 3898 treesize of output 3774 [2025-03-16 13:51:06,430 WARN L672 sPolynomialRelations]: Constructing 64(two to the power of 6 dual juncts. [2025-03-16 13:51:06,622 WARN L672 sPolynomialRelations]: Constructing 64(two to the power of 6 dual juncts. [2025-03-16 13:51:06,786 WARN L672 sPolynomialRelations]: Constructing 64(two to the power of 6 dual juncts. [2025-03-16 13:51:07,063 WARN L672 sPolynomialRelations]: Constructing 64(two to the power of 6 dual juncts. [2025-03-16 13:51:07,843 WARN L672 sPolynomialRelations]: Constructing 64(two to the power of 6 dual juncts. [2025-03-16 13:51:07,963 WARN L672 sPolynomialRelations]: Constructing 128(two to the power of 7 dual juncts.