./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/recursive/Ackermann03.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/recursive/Ackermann03.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 c244f72db2906c596b7f122d769fc1464836d7d05d9227ee4269773d59ed10bd --- Real Ultimate output --- This is Ultimate 0.3.0-?-8fc3dc6-m [2025-03-16 18:50:45,351 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-16 18:50:45,408 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2025-03-16 18:50:45,416 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-16 18:50:45,417 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-16 18:50:45,437 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-16 18:50:45,437 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-16 18:50:45,438 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-16 18:50:45,438 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-16 18:50:45,439 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-16 18:50:45,439 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-03-16 18:50:45,439 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-03-16 18:50:45,440 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-16 18:50:45,440 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-16 18:50:45,440 INFO L153 SettingsManager]: * Use SBE=true [2025-03-16 18:50:45,440 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-16 18:50:45,441 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-03-16 18:50:45,441 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-16 18:50:45,441 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-16 18:50:45,441 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-16 18:50:45,441 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-16 18:50:45,441 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-03-16 18:50:45,441 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-03-16 18:50:45,441 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-03-16 18:50:45,441 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-16 18:50:45,441 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-16 18:50:45,441 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-16 18:50:45,441 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-16 18:50:45,441 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-16 18:50:45,442 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-16 18:50:45,442 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-03-16 18:50:45,442 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-03-16 18:50:45,442 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-16 18:50:45,442 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-16 18:50:45,442 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-03-16 18:50:45,442 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-03-16 18:50:45,442 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-03-16 18:50:45,442 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-16 18:50:45,443 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-03-16 18:50:45,443 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-03-16 18:50:45,443 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-03-16 18:50:45,443 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-03-16 18:50:45,443 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-03-16 18:50:45,443 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 -> c244f72db2906c596b7f122d769fc1464836d7d05d9227ee4269773d59ed10bd [2025-03-16 18:50:45,636 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-16 18:50:45,642 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-16 18:50:45,645 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-16 18:50:45,646 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-16 18:50:45,646 INFO L274 PluginConnector]: CDTParser initialized [2025-03-16 18:50:45,647 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursive/Ackermann03.c [2025-03-16 18:50:46,761 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/97f42efd4/cb387c1e88e549799efb70529515e77f/FLAG6d8640f5b [2025-03-16 18:50:46,973 INFO L384 CDTParser]: Found 1 translation units. [2025-03-16 18:50:46,973 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive/Ackermann03.c [2025-03-16 18:50:46,986 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/97f42efd4/cb387c1e88e549799efb70529515e77f/FLAG6d8640f5b [2025-03-16 18:50:47,025 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/97f42efd4/cb387c1e88e549799efb70529515e77f [2025-03-16 18:50:47,027 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-16 18:50:47,028 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-16 18:50:47,033 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-16 18:50:47,034 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-16 18:50:47,039 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-16 18:50:47,039 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.03 06:50:47" (1/1) ... [2025-03-16 18:50:47,040 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@154be36a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:50:47, skipping insertion in model container [2025-03-16 18:50:47,040 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.03 06:50:47" (1/1) ... [2025-03-16 18:50:47,051 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-16 18:50:47,154 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/recursive/Ackermann03.c[1168,1181] [2025-03-16 18:50:47,157 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-16 18:50:47,164 INFO L200 MainTranslator]: Completed pre-run [2025-03-16 18:50:47,172 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/recursive/Ackermann03.c[1168,1181] [2025-03-16 18:50:47,173 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-16 18:50:47,180 INFO L204 MainTranslator]: Completed translation [2025-03-16 18:50:47,181 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:50:47 WrapperNode [2025-03-16 18:50:47,182 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-16 18:50:47,183 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-16 18:50:47,183 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-16 18:50:47,183 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-16 18:50:47,187 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:50:47" (1/1) ... [2025-03-16 18:50:47,191 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:50:47" (1/1) ... [2025-03-16 18:50:47,201 INFO L138 Inliner]: procedures = 13, calls = 11, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 33 [2025-03-16 18:50:47,201 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-16 18:50:47,201 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-16 18:50:47,201 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-16 18:50:47,202 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-16 18:50:47,206 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:50:47" (1/1) ... [2025-03-16 18:50:47,206 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:50:47" (1/1) ... [2025-03-16 18:50:47,206 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:50:47" (1/1) ... [2025-03-16 18:50:47,212 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2025-03-16 18:50:47,212 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:50:47" (1/1) ... [2025-03-16 18:50:47,212 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:50:47" (1/1) ... [2025-03-16 18:50:47,213 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:50:47" (1/1) ... [2025-03-16 18:50:47,214 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:50:47" (1/1) ... [2025-03-16 18:50:47,214 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:50:47" (1/1) ... [2025-03-16 18:50:47,214 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:50:47" (1/1) ... [2025-03-16 18:50:47,215 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-16 18:50:47,216 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-16 18:50:47,216 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-16 18:50:47,216 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-16 18:50:47,216 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:50:47" (1/1) ... [2025-03-16 18:50:47,220 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-16 18:50:47,227 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:50:47,237 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 18:50:47,239 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 18:50:47,254 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-16 18:50:47,254 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-16 18:50:47,254 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-16 18:50:47,254 INFO L130 BoogieDeclarations]: Found specification of procedure ackermann [2025-03-16 18:50:47,254 INFO L138 BoogieDeclarations]: Found implementation of procedure ackermann [2025-03-16 18:50:47,254 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-03-16 18:50:47,290 INFO L256 CfgBuilder]: Building ICFG [2025-03-16 18:50:47,292 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-16 18:50:47,374 INFO L1322 $ProcedureCfgBuilder]: dead code at ProgramPoint L23: havoc #t~ret5;havoc #t~ret6; [2025-03-16 18:50:47,375 INFO L1322 $ProcedureCfgBuilder]: dead code at ProgramPoint L21: havoc #t~ret4; [2025-03-16 18:50:47,380 INFO L? ?]: Removed 13 outVars from TransFormulas that were not future-live. [2025-03-16 18:50:47,381 INFO L307 CfgBuilder]: Performing block encoding [2025-03-16 18:50:47,387 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-16 18:50:47,390 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-16 18:50:47,390 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 16.03 06:50:47 BoogieIcfgContainer [2025-03-16 18:50:47,390 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-16 18:50:47,392 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-03-16 18:50:47,392 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-03-16 18:50:47,395 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-03-16 18:50:47,395 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 16.03 06:50:47" (1/3) ... [2025-03-16 18:50:47,396 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@74c81307 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.03 06:50:47, skipping insertion in model container [2025-03-16 18:50:47,396 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:50:47" (2/3) ... [2025-03-16 18:50:47,396 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@74c81307 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.03 06:50:47, skipping insertion in model container [2025-03-16 18:50:47,396 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 16.03 06:50:47" (3/3) ... [2025-03-16 18:50:47,397 INFO L128 eAbstractionObserver]: Analyzing ICFG Ackermann03.c [2025-03-16 18:50:47,406 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-03-16 18:50:47,406 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG Ackermann03.c that has 2 procedures, 22 locations, 1 initial locations, 0 loop locations, and 1 error locations. [2025-03-16 18:50:47,439 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-03-16 18:50:47,448 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;@7472d24c, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-03-16 18:50:47,449 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-03-16 18:50:47,452 INFO L276 IsEmpty]: Start isEmpty. Operand has 22 states, 15 states have (on average 1.4) internal successors, (21), 16 states have internal predecessors, (21), 4 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2025-03-16 18:50:47,457 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2025-03-16 18:50:47,457 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:50:47,457 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:50:47,458 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:50:47,462 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:50:47,462 INFO L85 PathProgramCache]: Analyzing trace with hash -777849041, now seen corresponding path program 1 times [2025-03-16 18:50:47,467 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:50:47,467 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [512289921] [2025-03-16 18:50:47,467 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:50:47,468 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:50:47,509 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 11 statements into 1 equivalence classes. [2025-03-16 18:50:47,521 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 11 of 11 statements. [2025-03-16 18:50:47,521 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:50:47,521 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:50:47,623 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 18:50:47,624 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:50:47,624 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [512289921] [2025-03-16 18:50:47,624 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [512289921] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 18:50:47,624 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 18:50:47,624 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-16 18:50:47,625 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [933778560] [2025-03-16 18:50:47,626 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:50:47,628 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-16 18:50:47,628 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:50:47,639 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-16 18:50:47,639 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-16 18:50:47,640 INFO L87 Difference]: Start difference. First operand has 22 states, 15 states have (on average 1.4) internal successors, (21), 16 states have internal predecessors, (21), 4 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Second operand has 5 states, 5 states have (on average 1.8) internal successors, (9), 5 states have internal predecessors, (9), 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 18:50:47,731 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:50:47,731 INFO L93 Difference]: Finished difference Result 36 states and 52 transitions. [2025-03-16 18:50:47,732 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-16 18:50:47,733 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 5 states have internal predecessors, (9), 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 11 [2025-03-16 18:50:47,733 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:50:47,737 INFO L225 Difference]: With dead ends: 36 [2025-03-16 18:50:47,737 INFO L226 Difference]: Without dead ends: 26 [2025-03-16 18:50:47,739 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2025-03-16 18:50:47,741 INFO L435 NwaCegarLoop]: 23 mSDtfsCounter, 11 mSDsluCounter, 42 mSDsCounter, 0 mSdLazyCounter, 62 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 65 SdHoareTripleChecker+Invalid, 67 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 62 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:50:47,741 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 65 Invalid, 67 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 62 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 18:50:47,749 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26 states. [2025-03-16 18:50:47,759 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26 to 24. [2025-03-16 18:50:47,760 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24 states, 16 states have (on average 1.125) internal successors, (18), 16 states have internal predecessors, (18), 5 states have call successors, (5), 1 states have call predecessors, (5), 2 states have return successors, (9), 6 states have call predecessors, (9), 5 states have call successors, (9) [2025-03-16 18:50:47,762 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 32 transitions. [2025-03-16 18:50:47,763 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 32 transitions. Word has length 11 [2025-03-16 18:50:47,763 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:50:47,763 INFO L471 AbstractCegarLoop]: Abstraction has 24 states and 32 transitions. [2025-03-16 18:50:47,764 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 5 states have internal predecessors, (9), 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 18:50:47,764 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 32 transitions. [2025-03-16 18:50:47,765 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2025-03-16 18:50:47,765 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:50:47,765 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:50:47,765 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2025-03-16 18:50:47,765 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:50:47,766 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:50:47,766 INFO L85 PathProgramCache]: Analyzing trace with hash -522828622, now seen corresponding path program 1 times [2025-03-16 18:50:47,766 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:50:47,766 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [683177116] [2025-03-16 18:50:47,766 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:50:47,766 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:50:47,771 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 18 statements into 1 equivalence classes. [2025-03-16 18:50:47,781 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 18 of 18 statements. [2025-03-16 18:50:47,781 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:50:47,781 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:50:47,841 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 1 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2025-03-16 18:50:47,841 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:50:47,841 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [683177116] [2025-03-16 18:50:47,841 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [683177116] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:50:47,841 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1515973198] [2025-03-16 18:50:47,841 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:50:47,841 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:50:47,841 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:50:47,844 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 18:50:47,845 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 18:50:47,869 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 18 statements into 1 equivalence classes. [2025-03-16 18:50:47,881 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 18 of 18 statements. [2025-03-16 18:50:47,881 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:50:47,881 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:50:47,882 INFO L256 TraceCheckSpWp]: Trace formula consists of 76 conjuncts, 4 conjuncts are in the unsatisfiable core [2025-03-16 18:50:47,885 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:50:47,912 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 1 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2025-03-16 18:50:47,912 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:50:47,999 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 1 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2025-03-16 18:50:47,999 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1515973198] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:50:47,999 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 18:50:48,000 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5, 5] total 8 [2025-03-16 18:50:48,002 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1075721289] [2025-03-16 18:50:48,002 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 18:50:48,002 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2025-03-16 18:50:48,003 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:50:48,003 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-03-16 18:50:48,004 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2025-03-16 18:50:48,004 INFO L87 Difference]: Start difference. First operand 24 states and 32 transitions. Second operand has 8 states, 8 states have (on average 2.625) internal successors, (21), 8 states have internal predecessors, (21), 3 states have call successors, (3), 1 states have call predecessors, (3), 3 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) [2025-03-16 18:50:48,120 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:50:48,120 INFO L93 Difference]: Finished difference Result 68 states and 123 transitions. [2025-03-16 18:50:48,121 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2025-03-16 18:50:48,121 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 2.625) internal successors, (21), 8 states have internal predecessors, (21), 3 states have call successors, (3), 1 states have call predecessors, (3), 3 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) Word has length 18 [2025-03-16 18:50:48,121 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:50:48,123 INFO L225 Difference]: With dead ends: 68 [2025-03-16 18:50:48,123 INFO L226 Difference]: Without dead ends: 44 [2025-03-16 18:50:48,123 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 41 GetRequests, 34 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=23, Invalid=49, Unknown=0, NotChecked=0, Total=72 [2025-03-16 18:50:48,124 INFO L435 NwaCegarLoop]: 26 mSDtfsCounter, 11 mSDsluCounter, 62 mSDsCounter, 0 mSdLazyCounter, 104 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 88 SdHoareTripleChecker+Invalid, 112 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 104 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:50:48,124 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 88 Invalid, 112 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 104 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 18:50:48,124 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2025-03-16 18:50:48,133 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 40. [2025-03-16 18:50:48,133 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 40 states, 26 states have (on average 1.1538461538461537) internal successors, (30), 27 states have internal predecessors, (30), 8 states have call successors, (8), 2 states have call predecessors, (8), 5 states have return successors, (27), 10 states have call predecessors, (27), 8 states have call successors, (27) [2025-03-16 18:50:48,134 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 40 states to 40 states and 65 transitions. [2025-03-16 18:50:48,134 INFO L78 Accepts]: Start accepts. Automaton has 40 states and 65 transitions. Word has length 18 [2025-03-16 18:50:48,134 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:50:48,135 INFO L471 AbstractCegarLoop]: Abstraction has 40 states and 65 transitions. [2025-03-16 18:50:48,135 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 2.625) internal successors, (21), 8 states have internal predecessors, (21), 3 states have call successors, (3), 1 states have call predecessors, (3), 3 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) [2025-03-16 18:50:48,135 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 65 transitions. [2025-03-16 18:50:48,138 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2025-03-16 18:50:48,139 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:50:48,139 INFO L218 NwaCegarLoop]: trace histogram [6, 6, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:50:48,145 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2025-03-16 18:50:48,339 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:50:48,340 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:50:48,340 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:50:48,341 INFO L85 PathProgramCache]: Analyzing trace with hash -1555976702, now seen corresponding path program 1 times [2025-03-16 18:50:48,341 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:50:48,341 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [129244972] [2025-03-16 18:50:48,341 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:50:48,341 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:50:48,346 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 44 statements into 1 equivalence classes. [2025-03-16 18:50:48,370 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 44 of 44 statements. [2025-03-16 18:50:48,371 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:50:48,371 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:50:48,521 INFO L134 CoverageAnalysis]: Checked inductivity of 67 backedges. 6 proven. 24 refuted. 0 times theorem prover too weak. 37 trivial. 0 not checked. [2025-03-16 18:50:48,522 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:50:48,522 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [129244972] [2025-03-16 18:50:48,522 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [129244972] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:50:48,522 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [951991835] [2025-03-16 18:50:48,522 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:50:48,522 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:50:48,522 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:50:48,524 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 18:50:48,526 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 18:50:48,552 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 44 statements into 1 equivalence classes. [2025-03-16 18:50:48,573 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 44 of 44 statements. [2025-03-16 18:50:48,573 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:50:48,573 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:50:48,574 INFO L256 TraceCheckSpWp]: Trace formula consists of 152 conjuncts, 10 conjuncts are in the unsatisfiable core [2025-03-16 18:50:48,576 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:50:48,626 INFO L134 CoverageAnalysis]: Checked inductivity of 67 backedges. 6 proven. 24 refuted. 0 times theorem prover too weak. 37 trivial. 0 not checked. [2025-03-16 18:50:48,627 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:50:49,059 INFO L134 CoverageAnalysis]: Checked inductivity of 67 backedges. 6 proven. 27 refuted. 0 times theorem prover too weak. 34 trivial. 0 not checked. [2025-03-16 18:50:49,059 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [951991835] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:50:49,059 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 18:50:49,060 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 7] total 8 [2025-03-16 18:50:49,060 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1385401915] [2025-03-16 18:50:49,060 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 18:50:49,060 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2025-03-16 18:50:49,061 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:50:49,061 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-03-16 18:50:49,061 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=37, Unknown=0, NotChecked=0, Total=56 [2025-03-16 18:50:49,061 INFO L87 Difference]: Start difference. First operand 40 states and 65 transitions. Second operand has 8 states, 8 states have (on average 3.125) internal successors, (25), 8 states have internal predecessors, (25), 4 states have call successors, (6), 1 states have call predecessors, (6), 3 states have return successors, (6), 2 states have call predecessors, (6), 4 states have call successors, (6) [2025-03-16 18:50:49,142 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:50:49,142 INFO L93 Difference]: Finished difference Result 61 states and 123 transitions. [2025-03-16 18:50:49,142 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2025-03-16 18:50:49,142 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 3.125) internal successors, (25), 8 states have internal predecessors, (25), 4 states have call successors, (6), 1 states have call predecessors, (6), 3 states have return successors, (6), 2 states have call predecessors, (6), 4 states have call successors, (6) Word has length 44 [2025-03-16 18:50:49,143 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:50:49,144 INFO L225 Difference]: With dead ends: 61 [2025-03-16 18:50:49,144 INFO L226 Difference]: Without dead ends: 57 [2025-03-16 18:50:49,144 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 101 GetRequests, 88 SyntacticMatches, 5 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2025-03-16 18:50:49,145 INFO L435 NwaCegarLoop]: 19 mSDtfsCounter, 12 mSDsluCounter, 44 mSDsCounter, 0 mSdLazyCounter, 58 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 21 SdHoareTripleChecker+Valid, 63 SdHoareTripleChecker+Invalid, 67 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 58 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:50:49,145 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [21 Valid, 63 Invalid, 67 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 58 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 18:50:49,148 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 57 states. [2025-03-16 18:50:49,161 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 57 to 53. [2025-03-16 18:50:49,162 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 53 states, 34 states have (on average 1.1176470588235294) internal successors, (38), 35 states have internal predecessors, (38), 10 states have call successors, (10), 2 states have call predecessors, (10), 8 states have return successors, (60), 15 states have call predecessors, (60), 10 states have call successors, (60) [2025-03-16 18:50:49,165 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 108 transitions. [2025-03-16 18:50:49,165 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 108 transitions. Word has length 44 [2025-03-16 18:50:49,165 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:50:49,166 INFO L471 AbstractCegarLoop]: Abstraction has 53 states and 108 transitions. [2025-03-16 18:50:49,166 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 3.125) internal successors, (25), 8 states have internal predecessors, (25), 4 states have call successors, (6), 1 states have call predecessors, (6), 3 states have return successors, (6), 2 states have call predecessors, (6), 4 states have call successors, (6) [2025-03-16 18:50:49,166 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 108 transitions. [2025-03-16 18:50:49,171 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 119 [2025-03-16 18:50:49,171 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:50:49,171 INFO L218 NwaCegarLoop]: trace histogram [17, 17, 11, 6, 6, 6, 6, 6, 5, 5, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:50:49,177 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 18:50:49,371 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2025-03-16 18:50:49,371 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:50:49,372 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:50:49,372 INFO L85 PathProgramCache]: Analyzing trace with hash -526777589, now seen corresponding path program 2 times [2025-03-16 18:50:49,372 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:50:49,372 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1100754145] [2025-03-16 18:50:49,372 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:50:49,372 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:50:49,383 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 118 statements into 2 equivalence classes. [2025-03-16 18:50:49,413 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 118 of 118 statements. [2025-03-16 18:50:49,414 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:50:49,414 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:50:49,637 INFO L134 CoverageAnalysis]: Checked inductivity of 669 backedges. 157 proven. 146 refuted. 0 times theorem prover too weak. 366 trivial. 0 not checked. [2025-03-16 18:50:49,638 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:50:49,638 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1100754145] [2025-03-16 18:50:49,638 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1100754145] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:50:49,638 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1357397192] [2025-03-16 18:50:49,638 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:50:49,638 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:50:49,639 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:50:49,640 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 18:50:49,642 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 18:50:49,678 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 118 statements into 2 equivalence classes. [2025-03-16 18:50:49,710 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 118 of 118 statements. [2025-03-16 18:50:49,710 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:50:49,710 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:50:49,711 INFO L256 TraceCheckSpWp]: Trace formula consists of 366 conjuncts, 17 conjuncts are in the unsatisfiable core [2025-03-16 18:50:49,714 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:50:49,830 INFO L134 CoverageAnalysis]: Checked inductivity of 669 backedges. 360 proven. 86 refuted. 0 times theorem prover too weak. 223 trivial. 0 not checked. [2025-03-16 18:50:49,831 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:50:51,166 INFO L134 CoverageAnalysis]: Checked inductivity of 669 backedges. 115 proven. 179 refuted. 0 times theorem prover too weak. 375 trivial. 0 not checked. [2025-03-16 18:50:51,166 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1357397192] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:50:51,166 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 18:50:51,166 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 12, 15] total 30 [2025-03-16 18:50:51,166 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [363471639] [2025-03-16 18:50:51,166 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 18:50:51,167 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 30 states [2025-03-16 18:50:51,167 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:50:51,167 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2025-03-16 18:50:51,168 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=100, Invalid=770, Unknown=0, NotChecked=0, Total=870 [2025-03-16 18:50:51,168 INFO L87 Difference]: Start difference. First operand 53 states and 108 transitions. Second operand has 30 states, 30 states have (on average 2.4) internal successors, (72), 24 states have internal predecessors, (72), 10 states have call successors, (18), 2 states have call predecessors, (18), 14 states have return successors, (31), 18 states have call predecessors, (31), 10 states have call successors, (31) [2025-03-16 18:50:52,358 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:50:52,359 INFO L93 Difference]: Finished difference Result 347 states and 2270 transitions. [2025-03-16 18:50:52,360 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 49 states. [2025-03-16 18:50:52,360 INFO L78 Accepts]: Start accepts. Automaton has has 30 states, 30 states have (on average 2.4) internal successors, (72), 24 states have internal predecessors, (72), 10 states have call successors, (18), 2 states have call predecessors, (18), 14 states have return successors, (31), 18 states have call predecessors, (31), 10 states have call successors, (31) Word has length 118 [2025-03-16 18:50:52,360 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:50:52,362 INFO L225 Difference]: With dead ends: 347 [2025-03-16 18:50:52,362 INFO L226 Difference]: Without dead ends: 50 [2025-03-16 18:50:52,376 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 295 GetRequests, 220 SyntacticMatches, 1 SemanticMatches, 74 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1123 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=1009, Invalid=4691, Unknown=0, NotChecked=0, Total=5700 [2025-03-16 18:50:52,377 INFO L435 NwaCegarLoop]: 41 mSDtfsCounter, 15 mSDsluCounter, 281 mSDsCounter, 0 mSdLazyCounter, 924 mSolverCounterSat, 90 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 322 SdHoareTripleChecker+Invalid, 1014 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 90 IncrementalHoareTripleChecker+Valid, 924 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2025-03-16 18:50:52,377 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 322 Invalid, 1014 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [90 Valid, 924 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2025-03-16 18:50:52,378 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2025-03-16 18:50:52,385 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 47. [2025-03-16 18:50:52,385 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 47 states, 30 states have (on average 1.1333333333333333) internal successors, (34), 33 states have internal predecessors, (34), 8 states have call successors, (8), 2 states have call predecessors, (8), 8 states have return successors, (18), 11 states have call predecessors, (18), 8 states have call successors, (18) [2025-03-16 18:50:52,386 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 60 transitions. [2025-03-16 18:50:52,386 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 60 transitions. Word has length 118 [2025-03-16 18:50:52,386 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:50:52,387 INFO L471 AbstractCegarLoop]: Abstraction has 47 states and 60 transitions. [2025-03-16 18:50:52,387 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 30 states, 30 states have (on average 2.4) internal successors, (72), 24 states have internal predecessors, (72), 10 states have call successors, (18), 2 states have call predecessors, (18), 14 states have return successors, (31), 18 states have call predecessors, (31), 10 states have call successors, (31) [2025-03-16 18:50:52,387 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 60 transitions. [2025-03-16 18:50:52,388 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 144 [2025-03-16 18:50:52,388 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:50:52,388 INFO L218 NwaCegarLoop]: trace histogram [21, 21, 12, 9, 8, 8, 8, 8, 8, 8, 8, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:50:52,395 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 18:50:52,593 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:50:52,593 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:50:52,593 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:50:52,594 INFO L85 PathProgramCache]: Analyzing trace with hash 2008985291, now seen corresponding path program 3 times [2025-03-16 18:50:52,594 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:50:52,594 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1692933028] [2025-03-16 18:50:52,594 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 18:50:52,594 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:50:52,602 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 143 statements into 15 equivalence classes. [2025-03-16 18:50:52,636 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 14 check-sat command(s) and asserted 137 of 143 statements. [2025-03-16 18:50:52,636 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 14 check-sat command(s) [2025-03-16 18:50:52,636 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:50:53,551 INFO L134 CoverageAnalysis]: Checked inductivity of 1030 backedges. 396 proven. 240 refuted. 0 times theorem prover too weak. 394 trivial. 0 not checked. [2025-03-16 18:50:53,551 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:50:53,551 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1692933028] [2025-03-16 18:50:53,552 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1692933028] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:50:53,552 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [48197261] [2025-03-16 18:50:53,552 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 18:50:53,552 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:50:53,552 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:50:53,554 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 18:50:53,555 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 18:50:53,602 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 143 statements into 15 equivalence classes. [2025-03-16 18:50:53,640 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 14 check-sat command(s) and asserted 137 of 143 statements. [2025-03-16 18:50:53,641 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 14 check-sat command(s) [2025-03-16 18:50:53,641 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:50:53,642 INFO L256 TraceCheckSpWp]: Trace formula consists of 426 conjuncts, 33 conjuncts are in the unsatisfiable core [2025-03-16 18:50:53,645 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:50:53,903 INFO L134 CoverageAnalysis]: Checked inductivity of 1030 backedges. 367 proven. 209 refuted. 0 times theorem prover too weak. 454 trivial. 0 not checked. [2025-03-16 18:50:53,903 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:50:57,002 INFO L134 CoverageAnalysis]: Checked inductivity of 1030 backedges. 410 proven. 201 refuted. 0 times theorem prover too weak. 419 trivial. 0 not checked. [2025-03-16 18:50:57,002 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [48197261] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:50:57,002 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 18:50:57,002 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [31, 19, 26] total 59 [2025-03-16 18:50:57,002 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1658616618] [2025-03-16 18:50:57,003 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 18:50:57,004 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 59 states [2025-03-16 18:50:57,004 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:50:57,005 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 59 interpolants. [2025-03-16 18:50:57,006 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=354, Invalid=3068, Unknown=0, NotChecked=0, Total=3422 [2025-03-16 18:50:57,006 INFO L87 Difference]: Start difference. First operand 47 states and 60 transitions. Second operand has 59 states, 58 states have (on average 1.7758620689655173) internal successors, (103), 48 states have internal predecessors, (103), 20 states have call successors, (23), 1 states have call predecessors, (23), 26 states have return successors, (43), 28 states have call predecessors, (43), 20 states have call successors, (43) [2025-03-16 18:50:57,966 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:50:57,967 INFO L93 Difference]: Finished difference Result 143 states and 224 transitions. [2025-03-16 18:50:57,967 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 47 states. [2025-03-16 18:50:57,967 INFO L78 Accepts]: Start accepts. Automaton has has 59 states, 58 states have (on average 1.7758620689655173) internal successors, (103), 48 states have internal predecessors, (103), 20 states have call successors, (23), 1 states have call predecessors, (23), 26 states have return successors, (43), 28 states have call predecessors, (43), 20 states have call successors, (43) Word has length 143 [2025-03-16 18:50:57,968 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:50:57,969 INFO L225 Difference]: With dead ends: 143 [2025-03-16 18:50:57,969 INFO L226 Difference]: Without dead ends: 83 [2025-03-16 18:50:57,973 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 357 GetRequests, 252 SyntacticMatches, 10 SemanticMatches, 95 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2753 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=1538, Invalid=7774, Unknown=0, NotChecked=0, Total=9312 [2025-03-16 18:50:57,974 INFO L435 NwaCegarLoop]: 35 mSDtfsCounter, 108 mSDsluCounter, 443 mSDsCounter, 0 mSdLazyCounter, 1331 mSolverCounterSat, 216 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 113 SdHoareTripleChecker+Valid, 478 SdHoareTripleChecker+Invalid, 1547 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 216 IncrementalHoareTripleChecker+Valid, 1331 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2025-03-16 18:50:57,974 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [113 Valid, 478 Invalid, 1547 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [216 Valid, 1331 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2025-03-16 18:50:57,974 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 83 states. [2025-03-16 18:50:57,981 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 83 to 63. [2025-03-16 18:50:57,982 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 63 states, 42 states have (on average 1.119047619047619) internal successors, (47), 44 states have internal predecessors, (47), 10 states have call successors, (10), 5 states have call predecessors, (10), 10 states have return successors, (20), 13 states have call predecessors, (20), 10 states have call successors, (20) [2025-03-16 18:50:57,982 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 77 transitions. [2025-03-16 18:50:57,983 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 77 transitions. Word has length 143 [2025-03-16 18:50:57,983 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:50:57,983 INFO L471 AbstractCegarLoop]: Abstraction has 63 states and 77 transitions. [2025-03-16 18:50:57,983 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 59 states, 58 states have (on average 1.7758620689655173) internal successors, (103), 48 states have internal predecessors, (103), 20 states have call successors, (23), 1 states have call predecessors, (23), 26 states have return successors, (43), 28 states have call predecessors, (43), 20 states have call successors, (43) [2025-03-16 18:50:57,983 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 77 transitions. [2025-03-16 18:50:57,985 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 144 [2025-03-16 18:50:57,985 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:50:57,985 INFO L218 NwaCegarLoop]: trace histogram [21, 21, 12, 9, 8, 8, 8, 8, 8, 8, 8, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:50:57,993 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 18:50:58,188 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:50:58,188 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:50:58,189 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:50:58,189 INFO L85 PathProgramCache]: Analyzing trace with hash -430047615, now seen corresponding path program 4 times [2025-03-16 18:50:58,189 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:50:58,189 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1326601544] [2025-03-16 18:50:58,189 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-16 18:50:58,189 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:50:58,201 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 143 statements into 2 equivalence classes. [2025-03-16 18:50:58,229 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 143 of 143 statements. [2025-03-16 18:50:58,229 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-03-16 18:50:58,229 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:50:58,568 INFO L134 CoverageAnalysis]: Checked inductivity of 1030 backedges. 146 proven. 369 refuted. 0 times theorem prover too weak. 515 trivial. 0 not checked. [2025-03-16 18:50:58,569 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:50:58,569 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1326601544] [2025-03-16 18:50:58,569 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1326601544] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:50:58,569 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1605466329] [2025-03-16 18:50:58,569 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-16 18:50:58,569 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:50:58,569 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:50:58,571 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 18:50:58,573 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 18:50:58,654 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 143 statements into 2 equivalence classes. [2025-03-16 18:50:58,688 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 143 of 143 statements. [2025-03-16 18:50:58,688 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-03-16 18:50:58,688 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:50:58,690 INFO L256 TraceCheckSpWp]: Trace formula consists of 440 conjuncts, 21 conjuncts are in the unsatisfiable core [2025-03-16 18:50:58,692 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:50:58,739 INFO L134 CoverageAnalysis]: Checked inductivity of 1030 backedges. 595 proven. 114 refuted. 0 times theorem prover too weak. 321 trivial. 0 not checked. [2025-03-16 18:50:58,739 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:50:59,878 INFO L134 CoverageAnalysis]: Checked inductivity of 1030 backedges. 160 proven. 360 refuted. 0 times theorem prover too weak. 510 trivial. 0 not checked. [2025-03-16 18:50:59,879 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1605466329] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:50:59,879 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 18:50:59,879 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 14, 17] total 20 [2025-03-16 18:50:59,879 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [379145794] [2025-03-16 18:50:59,879 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 18:50:59,879 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2025-03-16 18:50:59,879 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:50:59,880 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2025-03-16 18:50:59,880 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=64, Invalid=316, Unknown=0, NotChecked=0, Total=380 [2025-03-16 18:50:59,880 INFO L87 Difference]: Start difference. First operand 63 states and 77 transitions. Second operand has 20 states, 20 states have (on average 3.1) internal successors, (62), 17 states have internal predecessors, (62), 11 states have call successors, (17), 2 states have call predecessors, (17), 10 states have return successors, (25), 10 states have call predecessors, (25), 11 states have call successors, (25) [2025-03-16 18:51:00,067 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:51:00,068 INFO L93 Difference]: Finished difference Result 127 states and 159 transitions. [2025-03-16 18:51:00,072 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2025-03-16 18:51:00,072 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 20 states have (on average 3.1) internal successors, (62), 17 states have internal predecessors, (62), 11 states have call successors, (17), 2 states have call predecessors, (17), 10 states have return successors, (25), 10 states have call predecessors, (25), 11 states have call successors, (25) Word has length 143 [2025-03-16 18:51:00,072 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:51:00,073 INFO L225 Difference]: With dead ends: 127 [2025-03-16 18:51:00,073 INFO L226 Difference]: Without dead ends: 68 [2025-03-16 18:51:00,074 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 322 GetRequests, 275 SyntacticMatches, 11 SemanticMatches, 36 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 303 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=299, Invalid=1107, Unknown=0, NotChecked=0, Total=1406 [2025-03-16 18:51:00,074 INFO L435 NwaCegarLoop]: 21 mSDtfsCounter, 20 mSDsluCounter, 119 mSDsCounter, 0 mSdLazyCounter, 217 mSolverCounterSat, 29 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 140 SdHoareTripleChecker+Invalid, 246 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 29 IncrementalHoareTripleChecker+Valid, 217 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:51:00,074 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [25 Valid, 140 Invalid, 246 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [29 Valid, 217 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 18:51:00,074 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 68 states. [2025-03-16 18:51:00,079 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 68 to 63. [2025-03-16 18:51:00,082 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 63 states, 42 states have (on average 1.119047619047619) internal successors, (47), 44 states have internal predecessors, (47), 10 states have call successors, (10), 5 states have call predecessors, (10), 10 states have return successors, (18), 13 states have call predecessors, (18), 10 states have call successors, (18) [2025-03-16 18:51:00,083 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 75 transitions. [2025-03-16 18:51:00,083 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 75 transitions. Word has length 143 [2025-03-16 18:51:00,083 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:51:00,083 INFO L471 AbstractCegarLoop]: Abstraction has 63 states and 75 transitions. [2025-03-16 18:51:00,083 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 20 states have (on average 3.1) internal successors, (62), 17 states have internal predecessors, (62), 11 states have call successors, (17), 2 states have call predecessors, (17), 10 states have return successors, (25), 10 states have call predecessors, (25), 11 states have call successors, (25) [2025-03-16 18:51:00,083 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 75 transitions. [2025-03-16 18:51:00,084 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 157 [2025-03-16 18:51:00,084 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:51:00,084 INFO L218 NwaCegarLoop]: trace histogram [23, 23, 13, 10, 9, 9, 9, 9, 9, 9, 9, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:51:00,091 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2025-03-16 18:51:00,285 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:51:00,285 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:51:00,285 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:51:00,286 INFO L85 PathProgramCache]: Analyzing trace with hash 1360656611, now seen corresponding path program 5 times [2025-03-16 18:51:00,286 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:51:00,286 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [863699442] [2025-03-16 18:51:00,286 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-03-16 18:51:00,286 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:51:00,294 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 156 statements into 15 equivalence classes. [2025-03-16 18:51:00,311 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 13 check-sat command(s) and asserted 136 of 156 statements. [2025-03-16 18:51:00,311 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 13 check-sat command(s) [2025-03-16 18:51:00,312 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:51:00,829 INFO L134 CoverageAnalysis]: Checked inductivity of 1246 backedges. 399 proven. 321 refuted. 0 times theorem prover too weak. 526 trivial. 0 not checked. [2025-03-16 18:51:00,830 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:51:00,830 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [863699442] [2025-03-16 18:51:00,830 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [863699442] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:51:00,830 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [613231742] [2025-03-16 18:51:00,830 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-03-16 18:51:00,830 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:51:00,830 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:51:00,832 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 18:51:00,833 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 18:51:00,924 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 156 statements into 15 equivalence classes. [2025-03-16 18:51:00,960 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 13 check-sat command(s) and asserted 136 of 156 statements. [2025-03-16 18:51:00,960 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 13 check-sat command(s) [2025-03-16 18:51:00,960 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:51:00,962 INFO L256 TraceCheckSpWp]: Trace formula consists of 398 conjuncts, 35 conjuncts are in the unsatisfiable core [2025-03-16 18:51:00,964 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:51:01,246 INFO L134 CoverageAnalysis]: Checked inductivity of 1246 backedges. 421 proven. 286 refuted. 0 times theorem prover too weak. 539 trivial. 0 not checked. [2025-03-16 18:51:01,247 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:51:04,233 INFO L134 CoverageAnalysis]: Checked inductivity of 1246 backedges. 467 proven. 286 refuted. 0 times theorem prover too weak. 493 trivial. 0 not checked. [2025-03-16 18:51:04,234 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [613231742] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:51:04,234 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 18:51:04,234 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 20, 27] total 49 [2025-03-16 18:51:04,234 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1327199220] [2025-03-16 18:51:04,234 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 18:51:04,235 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 49 states [2025-03-16 18:51:04,235 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:51:04,235 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 49 interpolants. [2025-03-16 18:51:04,236 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=242, Invalid=2110, Unknown=0, NotChecked=0, Total=2352 [2025-03-16 18:51:04,236 INFO L87 Difference]: Start difference. First operand 63 states and 75 transitions. Second operand has 49 states, 49 states have (on average 2.0) internal successors, (98), 40 states have internal predecessors, (98), 23 states have call successors, (26), 1 states have call predecessors, (26), 24 states have return successors, (47), 28 states have call predecessors, (47), 23 states have call successors, (47) [2025-03-16 18:51:04,801 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:51:04,801 INFO L93 Difference]: Finished difference Result 138 states and 173 transitions. [2025-03-16 18:51:04,802 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 31 states. [2025-03-16 18:51:04,802 INFO L78 Accepts]: Start accepts. Automaton has has 49 states, 49 states have (on average 2.0) internal successors, (98), 40 states have internal predecessors, (98), 23 states have call successors, (26), 1 states have call predecessors, (26), 24 states have return successors, (47), 28 states have call predecessors, (47), 23 states have call successors, (47) Word has length 156 [2025-03-16 18:51:04,802 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:51:04,803 INFO L225 Difference]: With dead ends: 138 [2025-03-16 18:51:04,803 INFO L226 Difference]: Without dead ends: 79 [2025-03-16 18:51:04,805 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 367 GetRequests, 281 SyntacticMatches, 14 SemanticMatches, 72 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1229 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=835, Invalid=4567, Unknown=0, NotChecked=0, Total=5402 [2025-03-16 18:51:04,805 INFO L435 NwaCegarLoop]: 28 mSDtfsCounter, 57 mSDsluCounter, 352 mSDsCounter, 0 mSdLazyCounter, 879 mSolverCounterSat, 100 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 62 SdHoareTripleChecker+Valid, 380 SdHoareTripleChecker+Invalid, 979 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 100 IncrementalHoareTripleChecker+Valid, 879 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-03-16 18:51:04,805 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [62 Valid, 380 Invalid, 979 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [100 Valid, 879 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-03-16 18:51:04,805 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 79 states. [2025-03-16 18:51:04,810 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 79 to 68. [2025-03-16 18:51:04,811 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 68 states, 45 states have (on average 1.1111111111111112) internal successors, (50), 47 states have internal predecessors, (50), 11 states have call successors, (11), 5 states have call predecessors, (11), 11 states have return successors, (22), 15 states have call predecessors, (22), 11 states have call successors, (22) [2025-03-16 18:51:04,811 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 68 states to 68 states and 83 transitions. [2025-03-16 18:51:04,811 INFO L78 Accepts]: Start accepts. Automaton has 68 states and 83 transitions. Word has length 156 [2025-03-16 18:51:04,812 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:51:04,812 INFO L471 AbstractCegarLoop]: Abstraction has 68 states and 83 transitions. [2025-03-16 18:51:04,812 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 49 states, 49 states have (on average 2.0) internal successors, (98), 40 states have internal predecessors, (98), 23 states have call successors, (26), 1 states have call predecessors, (26), 24 states have return successors, (47), 28 states have call predecessors, (47), 23 states have call successors, (47) [2025-03-16 18:51:04,812 INFO L276 IsEmpty]: Start isEmpty. Operand 68 states and 83 transitions. [2025-03-16 18:51:04,813 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 170 [2025-03-16 18:51:04,813 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:51:04,813 INFO L218 NwaCegarLoop]: trace histogram [25, 25, 14, 11, 10, 10, 10, 10, 10, 10, 10, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:51:04,819 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 18:51:05,016 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:51:05,017 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:51:05,017 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:51:05,017 INFO L85 PathProgramCache]: Analyzing trace with hash -555363333, now seen corresponding path program 6 times [2025-03-16 18:51:05,017 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:51:05,017 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [888227146] [2025-03-16 18:51:05,017 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-03-16 18:51:05,017 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:51:05,025 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 169 statements into 18 equivalence classes. [2025-03-16 18:51:05,049 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 18 check-sat command(s) and asserted 169 of 169 statements. [2025-03-16 18:51:05,050 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 18 check-sat command(s) [2025-03-16 18:51:05,050 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:51:05,575 INFO L134 CoverageAnalysis]: Checked inductivity of 1483 backedges. 485 proven. 410 refuted. 0 times theorem prover too weak. 588 trivial. 0 not checked. [2025-03-16 18:51:05,575 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:51:05,575 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [888227146] [2025-03-16 18:51:05,575 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [888227146] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:51:05,575 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1619608081] [2025-03-16 18:51:05,575 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-03-16 18:51:05,575 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:51:05,575 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:51:05,577 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 18:51:05,578 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 18:51:05,706 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 169 statements into 18 equivalence classes. [2025-03-16 18:51:05,752 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 18 check-sat command(s) and asserted 169 of 169 statements. [2025-03-16 18:51:05,752 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 18 check-sat command(s) [2025-03-16 18:51:05,752 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:51:05,754 INFO L256 TraceCheckSpWp]: Trace formula consists of 516 conjuncts, 37 conjuncts are in the unsatisfiable core [2025-03-16 18:51:05,756 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:51:05,856 INFO L134 CoverageAnalysis]: Checked inductivity of 1483 backedges. 477 proven. 372 refuted. 0 times theorem prover too weak. 634 trivial. 0 not checked. [2025-03-16 18:51:05,857 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:51:08,817 INFO L134 CoverageAnalysis]: Checked inductivity of 1483 backedges. 525 proven. 384 refuted. 0 times theorem prover too weak. 574 trivial. 0 not checked. [2025-03-16 18:51:08,817 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1619608081] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:51:08,817 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 18:51:08,817 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [25, 21, 28] total 37 [2025-03-16 18:51:08,817 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1532935847] [2025-03-16 18:51:08,817 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 18:51:08,818 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 37 states [2025-03-16 18:51:08,818 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:51:08,818 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 37 interpolants. [2025-03-16 18:51:08,818 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=197, Invalid=1135, Unknown=0, NotChecked=0, Total=1332 [2025-03-16 18:51:08,819 INFO L87 Difference]: Start difference. First operand 68 states and 83 transitions. Second operand has 37 states, 37 states have (on average 2.5135135135135136) internal successors, (93), 33 states have internal predecessors, (93), 21 states have call successors, (24), 1 states have call predecessors, (24), 19 states have return successors, (37), 18 states have call predecessors, (37), 21 states have call successors, (37) [2025-03-16 18:51:09,186 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:51:09,186 INFO L93 Difference]: Finished difference Result 152 states and 196 transitions. [2025-03-16 18:51:09,186 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2025-03-16 18:51:09,186 INFO L78 Accepts]: Start accepts. Automaton has has 37 states, 37 states have (on average 2.5135135135135136) internal successors, (93), 33 states have internal predecessors, (93), 21 states have call successors, (24), 1 states have call predecessors, (24), 19 states have return successors, (37), 18 states have call predecessors, (37), 21 states have call successors, (37) Word has length 169 [2025-03-16 18:51:09,187 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:51:09,188 INFO L225 Difference]: With dead ends: 152 [2025-03-16 18:51:09,188 INFO L226 Difference]: Without dead ends: 88 [2025-03-16 18:51:09,189 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 397 GetRequests, 316 SyntacticMatches, 19 SemanticMatches, 62 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1223 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=822, Invalid=3210, Unknown=0, NotChecked=0, Total=4032 [2025-03-16 18:51:09,189 INFO L435 NwaCegarLoop]: 27 mSDtfsCounter, 102 mSDsluCounter, 192 mSDsCounter, 0 mSdLazyCounter, 478 mSolverCounterSat, 127 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 108 SdHoareTripleChecker+Valid, 219 SdHoareTripleChecker+Invalid, 605 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 127 IncrementalHoareTripleChecker+Valid, 478 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-16 18:51:09,189 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [108 Valid, 219 Invalid, 605 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [127 Valid, 478 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-16 18:51:09,190 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 88 states. [2025-03-16 18:51:09,198 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 88 to 73. [2025-03-16 18:51:09,199 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 73 states, 48 states have (on average 1.1041666666666667) internal successors, (53), 50 states have internal predecessors, (53), 12 states have call successors, (12), 5 states have call predecessors, (12), 12 states have return successors, (26), 17 states have call predecessors, (26), 12 states have call successors, (26) [2025-03-16 18:51:09,199 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 73 states to 73 states and 91 transitions. [2025-03-16 18:51:09,199 INFO L78 Accepts]: Start accepts. Automaton has 73 states and 91 transitions. Word has length 169 [2025-03-16 18:51:09,200 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:51:09,200 INFO L471 AbstractCegarLoop]: Abstraction has 73 states and 91 transitions. [2025-03-16 18:51:09,200 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 37 states, 37 states have (on average 2.5135135135135136) internal successors, (93), 33 states have internal predecessors, (93), 21 states have call successors, (24), 1 states have call predecessors, (24), 19 states have return successors, (37), 18 states have call predecessors, (37), 21 states have call successors, (37) [2025-03-16 18:51:09,200 INFO L276 IsEmpty]: Start isEmpty. Operand 73 states and 91 transitions. [2025-03-16 18:51:09,201 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 183 [2025-03-16 18:51:09,201 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:51:09,201 INFO L218 NwaCegarLoop]: trace histogram [27, 27, 15, 12, 11, 11, 11, 11, 11, 11, 11, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:51:09,208 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 18:51:09,402 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:51:09,402 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:51:09,402 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:51:09,402 INFO L85 PathProgramCache]: Analyzing trace with hash -563103821, now seen corresponding path program 7 times [2025-03-16 18:51:09,402 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:51:09,402 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [137511598] [2025-03-16 18:51:09,403 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-03-16 18:51:09,403 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:51:09,411 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 182 statements into 1 equivalence classes. [2025-03-16 18:51:09,436 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 182 of 182 statements. [2025-03-16 18:51:09,436 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:51:09,436 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:51:09,898 INFO L134 CoverageAnalysis]: Checked inductivity of 1741 backedges. 600 proven. 156 refuted. 0 times theorem prover too weak. 985 trivial. 0 not checked. [2025-03-16 18:51:09,898 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:51:09,899 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [137511598] [2025-03-16 18:51:09,899 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [137511598] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:51:09,899 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1344675631] [2025-03-16 18:51:09,899 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-03-16 18:51:09,899 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:51:09,899 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:51:09,900 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 18:51:09,901 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 18:51:10,053 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 182 statements into 1 equivalence classes. [2025-03-16 18:51:10,093 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 182 of 182 statements. [2025-03-16 18:51:10,093 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:51:10,093 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:51:10,096 INFO L256 TraceCheckSpWp]: Trace formula consists of 554 conjuncts, 79 conjuncts are in the unsatisfiable core [2025-03-16 18:51:10,098 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:51:10,148 INFO L134 CoverageAnalysis]: Checked inductivity of 1741 backedges. 583 proven. 158 refuted. 0 times theorem prover too weak. 1000 trivial. 0 not checked. [2025-03-16 18:51:10,149 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:51:10,924 INFO L134 CoverageAnalysis]: Checked inductivity of 1741 backedges. 597 proven. 189 refuted. 0 times theorem prover too weak. 955 trivial. 0 not checked. [2025-03-16 18:51:10,924 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1344675631] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:51:10,924 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 18:51:10,924 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [25, 23, 33] total 36 [2025-03-16 18:51:10,924 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [268110628] [2025-03-16 18:51:10,924 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 18:51:10,925 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 36 states [2025-03-16 18:51:10,925 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:51:10,925 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 36 interpolants. [2025-03-16 18:51:10,925 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=89, Invalid=1171, Unknown=0, NotChecked=0, Total=1260 [2025-03-16 18:51:10,925 INFO L87 Difference]: Start difference. First operand 73 states and 91 transitions. Second operand has 36 states, 36 states have (on average 1.5277777777777777) internal successors, (55), 29 states have internal predecessors, (55), 6 states have call successors, (9), 1 states have call predecessors, (9), 14 states have return successors, (22), 13 states have call predecessors, (22), 6 states have call successors, (22) [2025-03-16 18:51:13,308 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:51:13,309 INFO L93 Difference]: Finished difference Result 169 states and 240 transitions. [2025-03-16 18:51:13,309 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 67 states. [2025-03-16 18:51:13,309 INFO L78 Accepts]: Start accepts. Automaton has has 36 states, 36 states have (on average 1.5277777777777777) internal successors, (55), 29 states have internal predecessors, (55), 6 states have call successors, (9), 1 states have call predecessors, (9), 14 states have return successors, (22), 13 states have call predecessors, (22), 6 states have call successors, (22) Word has length 182 [2025-03-16 18:51:13,310 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:51:13,312 INFO L225 Difference]: With dead ends: 169 [2025-03-16 18:51:13,312 INFO L226 Difference]: Without dead ends: 125 [2025-03-16 18:51:13,316 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 458 GetRequests, 363 SyntacticMatches, 0 SemanticMatches, 95 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1865 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=1147, Invalid=8165, Unknown=0, NotChecked=0, Total=9312 [2025-03-16 18:51:13,316 INFO L435 NwaCegarLoop]: 54 mSDtfsCounter, 155 mSDsluCounter, 520 mSDsCounter, 0 mSdLazyCounter, 3192 mSolverCounterSat, 220 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 161 SdHoareTripleChecker+Valid, 574 SdHoareTripleChecker+Invalid, 3412 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 220 IncrementalHoareTripleChecker+Valid, 3192 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.0s IncrementalHoareTripleChecker+Time [2025-03-16 18:51:13,317 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [161 Valid, 574 Invalid, 3412 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [220 Valid, 3192 Invalid, 0 Unknown, 0 Unchecked, 1.0s Time] [2025-03-16 18:51:13,317 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 125 states. [2025-03-16 18:51:13,331 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 125 to 89. [2025-03-16 18:51:13,331 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 89 states, 59 states have (on average 1.11864406779661) internal successors, (66), 60 states have internal predecessors, (66), 15 states have call successors, (15), 7 states have call predecessors, (15), 14 states have return successors, (37), 21 states have call predecessors, (37), 15 states have call successors, (37) [2025-03-16 18:51:13,333 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 89 states to 89 states and 118 transitions. [2025-03-16 18:51:13,333 INFO L78 Accepts]: Start accepts. Automaton has 89 states and 118 transitions. Word has length 182 [2025-03-16 18:51:13,334 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:51:13,334 INFO L471 AbstractCegarLoop]: Abstraction has 89 states and 118 transitions. [2025-03-16 18:51:13,334 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 36 states, 36 states have (on average 1.5277777777777777) internal successors, (55), 29 states have internal predecessors, (55), 6 states have call successors, (9), 1 states have call predecessors, (9), 14 states have return successors, (22), 13 states have call predecessors, (22), 6 states have call successors, (22) [2025-03-16 18:51:13,334 INFO L276 IsEmpty]: Start isEmpty. Operand 89 states and 118 transitions. [2025-03-16 18:51:13,335 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 196 [2025-03-16 18:51:13,335 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:51:13,336 INFO L218 NwaCegarLoop]: trace histogram [29, 29, 16, 13, 12, 12, 12, 12, 12, 12, 12, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:51:13,343 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2025-03-16 18:51:13,536 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,SelfDestructingSolverStorable8 [2025-03-16 18:51:13,536 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:51:13,536 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:51:13,536 INFO L85 PathProgramCache]: Analyzing trace with hash -1894092501, now seen corresponding path program 8 times [2025-03-16 18:51:13,537 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:51:13,537 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1348132756] [2025-03-16 18:51:13,537 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:51:13,537 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:51:13,559 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 195 statements into 2 equivalence classes. [2025-03-16 18:51:13,593 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 195 of 195 statements. [2025-03-16 18:51:13,595 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:51:13,595 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:51:14,048 INFO L134 CoverageAnalysis]: Checked inductivity of 2020 backedges. 665 proven. 517 refuted. 0 times theorem prover too weak. 838 trivial. 0 not checked. [2025-03-16 18:51:14,049 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:51:14,049 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1348132756] [2025-03-16 18:51:14,049 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1348132756] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:51:14,049 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1917169477] [2025-03-16 18:51:14,049 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:51:14,049 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:51:14,049 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:51:14,051 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 18:51:14,052 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 18:51:14,211 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 195 statements into 2 equivalence classes. [2025-03-16 18:51:14,247 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 195 of 195 statements. [2025-03-16 18:51:14,247 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:51:14,247 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:51:14,250 INFO L256 TraceCheckSpWp]: Trace formula consists of 592 conjuncts, 41 conjuncts are in the unsatisfiable core [2025-03-16 18:51:14,252 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:51:14,347 INFO L134 CoverageAnalysis]: Checked inductivity of 2020 backedges. 647 proven. 519 refuted. 0 times theorem prover too weak. 854 trivial. 0 not checked. [2025-03-16 18:51:14,347 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:51:18,041 INFO L134 CoverageAnalysis]: Checked inductivity of 2020 backedges. 685 proven. 580 refuted. 0 times theorem prover too weak. 755 trivial. 0 not checked. [2025-03-16 18:51:18,042 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1917169477] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:51:18,042 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 18:51:18,042 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [25, 23, 32] total 36 [2025-03-16 18:51:18,042 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [225953660] [2025-03-16 18:51:18,042 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 18:51:18,042 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 36 states [2025-03-16 18:51:18,042 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:51:18,043 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 36 interpolants. [2025-03-16 18:51:18,043 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=181, Invalid=1079, Unknown=0, NotChecked=0, Total=1260 [2025-03-16 18:51:18,043 INFO L87 Difference]: Start difference. First operand 89 states and 118 transitions. Second operand has 36 states, 36 states have (on average 2.4166666666666665) internal successors, (87), 32 states have internal predecessors, (87), 19 states have call successors, (22), 1 states have call predecessors, (22), 19 states have return successors, (38), 17 states have call predecessors, (38), 19 states have call successors, (38) [2025-03-16 18:51:18,645 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:51:18,645 INFO L93 Difference]: Finished difference Result 215 states and 289 transitions. [2025-03-16 18:51:18,646 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2025-03-16 18:51:18,646 INFO L78 Accepts]: Start accepts. Automaton has has 36 states, 36 states have (on average 2.4166666666666665) internal successors, (87), 32 states have internal predecessors, (87), 19 states have call successors, (22), 1 states have call predecessors, (22), 19 states have return successors, (38), 17 states have call predecessors, (38), 19 states have call successors, (38) Word has length 195 [2025-03-16 18:51:18,646 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:51:18,648 INFO L225 Difference]: With dead ends: 215 [2025-03-16 18:51:18,648 INFO L226 Difference]: Without dead ends: 130 [2025-03-16 18:51:18,649 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 451 GetRequests, 371 SyntacticMatches, 21 SemanticMatches, 59 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1081 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=711, Invalid=2949, Unknown=0, NotChecked=0, Total=3660 [2025-03-16 18:51:18,649 INFO L435 NwaCegarLoop]: 33 mSDtfsCounter, 58 mSDsluCounter, 328 mSDsCounter, 0 mSdLazyCounter, 971 mSolverCounterSat, 42 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 58 SdHoareTripleChecker+Valid, 361 SdHoareTripleChecker+Invalid, 1013 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 42 IncrementalHoareTripleChecker+Valid, 971 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-03-16 18:51:18,650 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [58 Valid, 361 Invalid, 1013 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [42 Valid, 971 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-03-16 18:51:18,650 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 130 states. [2025-03-16 18:51:18,658 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 130 to 94. [2025-03-16 18:51:18,659 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 94 states, 62 states have (on average 1.1129032258064515) internal successors, (69), 63 states have internal predecessors, (69), 16 states have call successors, (16), 7 states have call predecessors, (16), 15 states have return successors, (39), 23 states have call predecessors, (39), 16 states have call successors, (39) [2025-03-16 18:51:18,659 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 94 states to 94 states and 124 transitions. [2025-03-16 18:51:18,660 INFO L78 Accepts]: Start accepts. Automaton has 94 states and 124 transitions. Word has length 195 [2025-03-16 18:51:18,660 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:51:18,660 INFO L471 AbstractCegarLoop]: Abstraction has 94 states and 124 transitions. [2025-03-16 18:51:18,660 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 36 states, 36 states have (on average 2.4166666666666665) internal successors, (87), 32 states have internal predecessors, (87), 19 states have call successors, (22), 1 states have call predecessors, (22), 19 states have return successors, (38), 17 states have call predecessors, (38), 19 states have call successors, (38) [2025-03-16 18:51:18,660 INFO L276 IsEmpty]: Start isEmpty. Operand 94 states and 124 transitions. [2025-03-16 18:51:18,662 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 209 [2025-03-16 18:51:18,662 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:51:18,662 INFO L218 NwaCegarLoop]: trace histogram [31, 31, 17, 14, 13, 13, 13, 13, 13, 13, 13, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:51:18,670 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2025-03-16 18:51:18,862 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2025-03-16 18:51:18,863 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:51:18,863 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:51:18,863 INFO L85 PathProgramCache]: Analyzing trace with hash 1678043325, now seen corresponding path program 9 times [2025-03-16 18:51:18,863 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:51:18,863 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2008325343] [2025-03-16 18:51:18,864 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 18:51:18,864 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:51:18,875 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 208 statements into 22 equivalence classes. [2025-03-16 18:51:18,906 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 22 check-sat command(s) and asserted 208 of 208 statements. [2025-03-16 18:51:18,907 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 22 check-sat command(s) [2025-03-16 18:51:18,907 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:51:19,651 INFO L134 CoverageAnalysis]: Checked inductivity of 2320 backedges. 462 proven. 936 refuted. 0 times theorem prover too weak. 922 trivial. 0 not checked. [2025-03-16 18:51:19,651 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:51:19,651 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2008325343] [2025-03-16 18:51:19,651 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2008325343] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:51:19,651 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [949879270] [2025-03-16 18:51:19,651 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 18:51:19,651 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:51:19,652 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:51:19,653 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 18:51:19,655 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 18:51:19,859 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 208 statements into 22 equivalence classes. [2025-03-16 18:51:19,910 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 22 check-sat command(s) and asserted 208 of 208 statements. [2025-03-16 18:51:19,910 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 22 check-sat command(s) [2025-03-16 18:51:19,910 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:51:19,912 INFO L256 TraceCheckSpWp]: Trace formula consists of 630 conjuncts, 25 conjuncts are in the unsatisfiable core [2025-03-16 18:51:19,915 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:51:20,023 INFO L134 CoverageAnalysis]: Checked inductivity of 2320 backedges. 1340 proven. 196 refuted. 0 times theorem prover too weak. 784 trivial. 0 not checked. [2025-03-16 18:51:20,023 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:51:21,833 INFO L134 CoverageAnalysis]: Checked inductivity of 2320 backedges. 274 proven. 806 refuted. 0 times theorem prover too weak. 1240 trivial. 0 not checked. [2025-03-16 18:51:21,834 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [949879270] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:51:21,834 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 18:51:21,834 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [31, 16, 21] total 44 [2025-03-16 18:51:21,834 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [258787432] [2025-03-16 18:51:21,834 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 18:51:21,835 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 44 states [2025-03-16 18:51:21,835 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:51:21,835 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 44 interpolants. [2025-03-16 18:51:21,836 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=245, Invalid=1647, Unknown=0, NotChecked=0, Total=1892 [2025-03-16 18:51:21,836 INFO L87 Difference]: Start difference. First operand 94 states and 124 transitions. Second operand has 44 states, 44 states have (on average 2.5) internal successors, (110), 38 states have internal predecessors, (110), 24 states have call successors, (30), 2 states have call predecessors, (30), 23 states have return successors, (48), 23 states have call predecessors, (48), 24 states have call successors, (48) [2025-03-16 18:51:22,282 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:51:22,282 INFO L93 Difference]: Finished difference Result 204 states and 269 transitions. [2025-03-16 18:51:22,282 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 32 states. [2025-03-16 18:51:22,283 INFO L78 Accepts]: Start accepts. Automaton has has 44 states, 44 states have (on average 2.5) internal successors, (110), 38 states have internal predecessors, (110), 24 states have call successors, (30), 2 states have call predecessors, (30), 23 states have return successors, (48), 23 states have call predecessors, (48), 24 states have call successors, (48) Word has length 208 [2025-03-16 18:51:22,283 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:51:22,284 INFO L225 Difference]: With dead ends: 204 [2025-03-16 18:51:22,284 INFO L226 Difference]: Without dead ends: 114 [2025-03-16 18:51:22,285 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 479 GetRequests, 403 SyntacticMatches, 13 SemanticMatches, 63 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1366 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=638, Invalid=3522, Unknown=0, NotChecked=0, Total=4160 [2025-03-16 18:51:22,286 INFO L435 NwaCegarLoop]: 32 mSDtfsCounter, 147 mSDsluCounter, 392 mSDsCounter, 0 mSdLazyCounter, 886 mSolverCounterSat, 135 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 155 SdHoareTripleChecker+Valid, 424 SdHoareTripleChecker+Invalid, 1021 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 135 IncrementalHoareTripleChecker+Valid, 886 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-03-16 18:51:22,286 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [155 Valid, 424 Invalid, 1021 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [135 Valid, 886 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-03-16 18:51:22,286 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 114 states. [2025-03-16 18:51:22,294 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 114 to 95. [2025-03-16 18:51:22,294 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 95 states, 63 states have (on average 1.1111111111111112) internal successors, (70), 65 states have internal predecessors, (70), 15 states have call successors, (15), 8 states have call predecessors, (15), 16 states have return successors, (30), 21 states have call predecessors, (30), 15 states have call successors, (30) [2025-03-16 18:51:22,295 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 95 states to 95 states and 115 transitions. [2025-03-16 18:51:22,295 INFO L78 Accepts]: Start accepts. Automaton has 95 states and 115 transitions. Word has length 208 [2025-03-16 18:51:22,295 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:51:22,295 INFO L471 AbstractCegarLoop]: Abstraction has 95 states and 115 transitions. [2025-03-16 18:51:22,296 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 44 states, 44 states have (on average 2.5) internal successors, (110), 38 states have internal predecessors, (110), 24 states have call successors, (30), 2 states have call predecessors, (30), 23 states have return successors, (48), 23 states have call predecessors, (48), 24 states have call successors, (48) [2025-03-16 18:51:22,296 INFO L276 IsEmpty]: Start isEmpty. Operand 95 states and 115 transitions. [2025-03-16 18:51:22,297 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 281 [2025-03-16 18:51:22,297 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:51:22,297 INFO L218 NwaCegarLoop]: trace histogram [42, 42, 23, 19, 18, 18, 18, 18, 18, 18, 18, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:51:22,305 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 18:51:22,497 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,SelfDestructingSolverStorable10 [2025-03-16 18:51:22,498 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:51:22,498 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:51:22,498 INFO L85 PathProgramCache]: Analyzing trace with hash 422502960, now seen corresponding path program 10 times [2025-03-16 18:51:22,498 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:51:22,498 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [117272451] [2025-03-16 18:51:22,498 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-16 18:51:22,499 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:51:22,509 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 280 statements into 2 equivalence classes. [2025-03-16 18:51:22,516 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 235 of 280 statements. [2025-03-16 18:51:22,517 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-03-16 18:51:22,517 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:51:22,721 INFO L134 CoverageAnalysis]: Checked inductivity of 4329 backedges. 215 proven. 534 refuted. 0 times theorem prover too weak. 3580 trivial. 0 not checked. [2025-03-16 18:51:22,721 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:51:22,721 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [117272451] [2025-03-16 18:51:22,721 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [117272451] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:51:22,721 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [378626861] [2025-03-16 18:51:22,721 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-16 18:51:22,722 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:51:22,722 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:51:22,724 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 18:51:22,725 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 18:51:22,969 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 280 statements into 2 equivalence classes. [2025-03-16 18:51:23,014 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 235 of 280 statements. [2025-03-16 18:51:23,014 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-03-16 18:51:23,014 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:51:23,016 INFO L256 TraceCheckSpWp]: Trace formula consists of 681 conjuncts, 10 conjuncts are in the unsatisfiable core [2025-03-16 18:51:23,018 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:51:23,085 INFO L134 CoverageAnalysis]: Checked inductivity of 4329 backedges. 234 proven. 507 refuted. 0 times theorem prover too weak. 3588 trivial. 0 not checked. [2025-03-16 18:51:23,085 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:51:23,696 INFO L134 CoverageAnalysis]: Checked inductivity of 4329 backedges. 234 proven. 522 refuted. 0 times theorem prover too weak. 3573 trivial. 0 not checked. [2025-03-16 18:51:23,696 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [378626861] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:51:23,696 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 18:51:23,696 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 8, 11] total 20 [2025-03-16 18:51:23,696 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1043878590] [2025-03-16 18:51:23,696 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 18:51:23,697 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2025-03-16 18:51:23,697 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:51:23,697 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2025-03-16 18:51:23,697 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=83, Invalid=297, Unknown=0, NotChecked=0, Total=380 [2025-03-16 18:51:23,697 INFO L87 Difference]: Start difference. First operand 95 states and 115 transitions. Second operand has 20 states, 19 states have (on average 3.263157894736842) internal successors, (62), 20 states have internal predecessors, (62), 15 states have call successors, (18), 1 states have call predecessors, (18), 9 states have return successors, (22), 11 states have call predecessors, (22), 15 states have call successors, (22) [2025-03-16 18:51:23,848 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:51:23,848 INFO L93 Difference]: Finished difference Result 98 states and 118 transitions. [2025-03-16 18:51:23,848 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2025-03-16 18:51:23,848 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 19 states have (on average 3.263157894736842) internal successors, (62), 20 states have internal predecessors, (62), 15 states have call successors, (18), 1 states have call predecessors, (18), 9 states have return successors, (22), 11 states have call predecessors, (22), 15 states have call successors, (22) Word has length 280 [2025-03-16 18:51:23,849 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:51:23,849 INFO L225 Difference]: With dead ends: 98 [2025-03-16 18:51:23,849 INFO L226 Difference]: Without dead ends: 0 [2025-03-16 18:51:23,850 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 580 GetRequests, 548 SyntacticMatches, 5 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 169 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=205, Invalid=607, Unknown=0, NotChecked=0, Total=812 [2025-03-16 18:51:23,850 INFO L435 NwaCegarLoop]: 25 mSDtfsCounter, 31 mSDsluCounter, 83 mSDsCounter, 0 mSdLazyCounter, 190 mSolverCounterSat, 31 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 108 SdHoareTripleChecker+Invalid, 221 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 31 IncrementalHoareTripleChecker+Valid, 190 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:51:23,850 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [34 Valid, 108 Invalid, 221 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [31 Valid, 190 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 18:51:23,850 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2025-03-16 18:51:23,850 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2025-03-16 18:51:23,851 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-16 18:51:23,851 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2025-03-16 18:51:23,851 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 280 [2025-03-16 18:51:23,851 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:51:23,851 INFO L471 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-03-16 18:51:23,851 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 19 states have (on average 3.263157894736842) internal successors, (62), 20 states have internal predecessors, (62), 15 states have call successors, (18), 1 states have call predecessors, (18), 9 states have return successors, (22), 11 states have call predecessors, (22), 15 states have call successors, (22) [2025-03-16 18:51:23,851 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2025-03-16 18:51:23,851 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2025-03-16 18:51:23,853 INFO L782 garLoopResultBuilder]: Registering result SAFE for location ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2025-03-16 18:51:23,861 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2025-03-16 18:51:24,054 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,SelfDestructingSolverStorable11 [2025-03-16 18:51:24,056 INFO L422 BasicCegarLoop]: Path program histogram: [10, 1, 1] [2025-03-16 18:51:24,058 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2025-03-16 18:51:48,527 INFO L170 ceAbstractionStarter]: Computing trace abstraction results [2025-03-16 18:51:48,530 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 16.03 06:51:48 BoogieIcfgContainer [2025-03-16 18:51:48,530 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2025-03-16 18:51:48,531 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2025-03-16 18:51:48,531 INFO L270 PluginConnector]: Initializing Witness Printer... [2025-03-16 18:51:48,531 INFO L274 PluginConnector]: Witness Printer initialized [2025-03-16 18:51:48,531 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 16.03 06:50:47" (3/4) ... [2025-03-16 18:51:48,533 INFO L146 WitnessPrinter]: Generating witness for correct program [2025-03-16 18:51:48,537 INFO L385 IcfgBacktranslator]: Ignoring RootEdge to procedure ackermann [2025-03-16 18:51:48,539 INFO L919 BoogieBacktranslator]: Reduced CFG by removing 11 nodes and edges [2025-03-16 18:51:48,539 INFO L919 BoogieBacktranslator]: Reduced CFG by removing 5 nodes and edges [2025-03-16 18:51:48,539 INFO L919 BoogieBacktranslator]: Reduced CFG by removing 3 nodes and edges [2025-03-16 18:51:48,539 INFO L919 BoogieBacktranslator]: Reduced CFG by removing 1 nodes and edges [2025-03-16 18:51:48,585 INFO L149 WitnessManager]: Wrote witness to /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/witness.graphml [2025-03-16 18:51:48,585 INFO L149 WitnessManager]: Wrote witness to /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/witness.yml [2025-03-16 18:51:48,585 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2025-03-16 18:51:48,586 INFO L158 Benchmark]: Toolchain (without parser) took 61557.75ms. Allocated memory was 142.6MB in the beginning and 1.1GB in the end (delta: 964.7MB). Free memory was 106.4MB in the beginning and 1.0GB in the end (delta: -943.5MB). Peak memory consumption was 15.7MB. Max. memory is 16.1GB. [2025-03-16 18:51:48,586 INFO L158 Benchmark]: CDTParser took 0.21ms. Allocated memory is still 201.3MB. Free memory is still 115.7MB. There was no memory consumed. Max. memory is 16.1GB. [2025-03-16 18:51:48,586 INFO L158 Benchmark]: CACSL2BoogieTranslator took 149.17ms. Allocated memory is still 142.6MB. Free memory was 105.3MB in the beginning and 95.6MB in the end (delta: 9.8MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-03-16 18:51:48,586 INFO L158 Benchmark]: Boogie Procedure Inliner took 18.16ms. Allocated memory is still 142.6MB. Free memory was 95.6MB in the beginning and 94.5MB in the end (delta: 1.1MB). There was no memory consumed. Max. memory is 16.1GB. [2025-03-16 18:51:48,587 INFO L158 Benchmark]: Boogie Preprocessor took 13.61ms. Allocated memory is still 142.6MB. Free memory was 94.5MB in the beginning and 93.4MB in the end (delta: 1.1MB). There was no memory consumed. Max. memory is 16.1GB. [2025-03-16 18:51:48,587 INFO L158 Benchmark]: IcfgBuilder took 174.94ms. Allocated memory is still 142.6MB. Free memory was 93.4MB in the beginning and 81.0MB in the end (delta: 12.4MB). Peak memory consumption was 16.8MB. Max. memory is 16.1GB. [2025-03-16 18:51:48,587 INFO L158 Benchmark]: TraceAbstraction took 61138.42ms. Allocated memory was 142.6MB in the beginning and 1.1GB in the end (delta: 964.7MB). Free memory was 81.0MB in the beginning and 1.1GB in the end (delta: -973.0MB). Peak memory consumption was 644.4MB. Max. memory is 16.1GB. [2025-03-16 18:51:48,588 INFO L158 Benchmark]: Witness Printer took 54.87ms. Allocated memory is still 1.1GB. Free memory was 1.1GB in the beginning and 1.0GB in the end (delta: 4.0MB). There was no memory consumed. Max. memory is 16.1GB. [2025-03-16 18:51:48,590 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.21ms. Allocated memory is still 201.3MB. Free memory is still 115.7MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 149.17ms. Allocated memory is still 142.6MB. Free memory was 105.3MB in the beginning and 95.6MB in the end (delta: 9.8MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 18.16ms. Allocated memory is still 142.6MB. Free memory was 95.6MB in the beginning and 94.5MB in the end (delta: 1.1MB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 13.61ms. Allocated memory is still 142.6MB. Free memory was 94.5MB in the beginning and 93.4MB in the end (delta: 1.1MB). There was no memory consumed. Max. memory is 16.1GB. * IcfgBuilder took 174.94ms. Allocated memory is still 142.6MB. Free memory was 93.4MB in the beginning and 81.0MB in the end (delta: 12.4MB). Peak memory consumption was 16.8MB. Max. memory is 16.1GB. * TraceAbstraction took 61138.42ms. Allocated memory was 142.6MB in the beginning and 1.1GB in the end (delta: 964.7MB). Free memory was 81.0MB in the beginning and 1.1GB in the end (delta: -973.0MB). Peak memory consumption was 644.4MB. Max. memory is 16.1GB. * Witness Printer took 54.87ms. Allocated memory is still 1.1GB. Free memory was 1.1GB in the beginning and 1.0GB in the end (delta: 4.0MB). There was no memory consumed. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - PositiveResult [Line: 45]: a call to reach_error is unreachable For all program executions holds that a call to reach_error is unreachable at this location - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 22 locations, 33 edges, 1 error locations. Started 1 CEGAR loops. OverallTime: 36.6s, OverallIterations: 12, TraceHistogramMax: 42, PathProgramHistogramMax: 10, EmptinessCheckTime: 0.0s, AutomataDifference: 7.2s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 782 SdHoareTripleChecker+Valid, 3.4s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 727 mSDsluCounter, 3222 SdHoareTripleChecker+Invalid, 2.8s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 2858 mSDsCounter, 1012 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 9292 IncrementalHoareTripleChecker+Invalid, 10304 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 1012 mSolverCounterUnsat, 364 mSDtfsCounter, 9292 mSolverCounterSat, 0.1s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 3854 GetRequests, 3153 SyntacticMatches, 99 SemanticMatches, 602 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11124 ImplicationChecksByTransitivity, 7.2s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=95occurred in iteration=11, InterpolantAutomatonStates: 347, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.1s AutomataMinimizationTime, 12 MinimizatonAttempts, 155 StatesRemovedByMinimization, 11 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.2s SsaConstructionTime, 0.7s SatisfiabilityAnalysisTime, 24.9s InterpolantComputationTime, 3323 NumberOfCodeBlocks, 3181 NumberOfCodeBlocksAsserted, 155 NumberOfCheckSat, 4945 ConstructedInterpolants, 0 QuantifiedInterpolants, 9681 SizeOfPredicates, 47 NumberOfNonLiveVariables, 4831 ConjunctsInSsa, 312 ConjunctsInUnsatCore, 34 InterpolantComputations, 1 PerfectInterpolantSequences, 38156/47817 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available, ConComCheckerStatistics: No data available - AllSpecificationsHoldResult: All specifications hold 1 specifications checked. All of them hold RESULT: Ultimate proved your program to be correct! [2025-03-16 18:51:48,605 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Ended with exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE