./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/array-tiling/mbpr4.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 8fc3dc66 Calling Ultimate with: /root/.sdkman/candidates/java/21.0.5-tem/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/array-tiling/mbpr4.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 d3770c63a87ff983494c9353997301d9eb30588c650f83b67bcf55f325443055 --- Real Ultimate output --- This is Ultimate 0.3.0-?-8fc3dc6-m [2025-03-16 13:34:11,050 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-16 13:34:11,108 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2025-03-16 13:34:11,113 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-16 13:34:11,115 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-16 13:34:11,131 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-16 13:34:11,131 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-16 13:34:11,132 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-16 13:34:11,132 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-16 13:34:11,132 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-16 13:34:11,132 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-03-16 13:34:11,132 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-03-16 13:34:11,133 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-16 13:34:11,133 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-16 13:34:11,133 INFO L153 SettingsManager]: * Use SBE=true [2025-03-16 13:34:11,133 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-16 13:34:11,134 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-03-16 13:34:11,134 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-16 13:34:11,134 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-16 13:34:11,134 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-16 13:34:11,134 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-16 13:34:11,134 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-03-16 13:34:11,134 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-03-16 13:34:11,134 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-03-16 13:34:11,134 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-16 13:34:11,135 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-16 13:34:11,135 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-16 13:34:11,135 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-16 13:34:11,135 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-16 13:34:11,135 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-16 13:34:11,135 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-03-16 13:34:11,135 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-03-16 13:34:11,135 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-16 13:34:11,135 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-16 13:34:11,136 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-03-16 13:34:11,136 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-03-16 13:34:11,136 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-03-16 13:34:11,136 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-16 13:34:11,136 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-03-16 13:34:11,136 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-03-16 13:34:11,136 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-03-16 13:34:11,136 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-03-16 13:34:11,136 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-03-16 13:34:11,136 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 -> d3770c63a87ff983494c9353997301d9eb30588c650f83b67bcf55f325443055 [2025-03-16 13:34:11,348 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-16 13:34:11,355 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-16 13:34:11,356 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-16 13:34:11,357 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-16 13:34:11,357 INFO L274 PluginConnector]: CDTParser initialized [2025-03-16 13:34:11,357 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/array-tiling/mbpr4.c [2025-03-16 13:34:12,469 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/41159f4f5/cf5032d155f843f0bbb98382033db8c3/FLAGe9b40e320 [2025-03-16 13:34:12,687 INFO L384 CDTParser]: Found 1 translation units. [2025-03-16 13:34:12,691 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/array-tiling/mbpr4.c [2025-03-16 13:34:12,697 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/41159f4f5/cf5032d155f843f0bbb98382033db8c3/FLAGe9b40e320 [2025-03-16 13:34:12,711 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/41159f4f5/cf5032d155f843f0bbb98382033db8c3 [2025-03-16 13:34:12,713 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-16 13:34:12,715 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-16 13:34:12,716 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-16 13:34:12,717 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-16 13:34:12,720 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-16 13:34:12,720 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.03 01:34:12" (1/1) ... [2025-03-16 13:34:12,721 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@4479722 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:34:12, skipping insertion in model container [2025-03-16 13:34:12,721 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.03 01:34:12" (1/1) ... [2025-03-16 13:34:12,736 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-16 13:34:12,839 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/array-tiling/mbpr4.c[396,409] [2025-03-16 13:34:12,865 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-16 13:34:12,875 INFO L200 MainTranslator]: Completed pre-run [2025-03-16 13:34:12,884 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/array-tiling/mbpr4.c[396,409] [2025-03-16 13:34:12,904 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-16 13:34:12,918 INFO L204 MainTranslator]: Completed translation [2025-03-16 13:34:12,919 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:34:12 WrapperNode [2025-03-16 13:34:12,920 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-16 13:34:12,921 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-16 13:34:12,921 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-16 13:34:12,921 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-16 13:34:12,925 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:34:12" (1/1) ... [2025-03-16 13:34:12,930 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:34:12" (1/1) ... [2025-03-16 13:34:12,948 INFO L138 Inliner]: procedures = 15, calls = 54, calls flagged for inlining = 4, calls inlined = 4, statements flattened = 131 [2025-03-16 13:34:12,948 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-16 13:34:12,949 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-16 13:34:12,949 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-16 13:34:12,949 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-16 13:34:12,955 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:34:12" (1/1) ... [2025-03-16 13:34:12,956 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:34:12" (1/1) ... [2025-03-16 13:34:12,957 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:34:12" (1/1) ... [2025-03-16 13:34:12,965 INFO L175 MemorySlicer]: Split 44 memory accesses to 3 slices as follows [2, 8, 34]. 77 percent of accesses are in the largest equivalence class. The 10 initializations are split as follows [2, 8, 0]. The 20 writes are split as follows [0, 0, 20]. [2025-03-16 13:34:12,965 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:34:12" (1/1) ... [2025-03-16 13:34:12,965 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:34:12" (1/1) ... [2025-03-16 13:34:12,969 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:34:12" (1/1) ... [2025-03-16 13:34:12,970 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:34:12" (1/1) ... [2025-03-16 13:34:12,971 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:34:12" (1/1) ... [2025-03-16 13:34:12,971 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:34:12" (1/1) ... [2025-03-16 13:34:12,972 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-16 13:34:12,973 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-16 13:34:12,973 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-16 13:34:12,973 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-16 13:34:12,974 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:34:12" (1/1) ... [2025-03-16 13:34:12,980 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-16 13:34:12,989 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:34:12,999 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2025-03-16 13:34:13,000 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2025-03-16 13:34:13,016 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-16 13:34:13,016 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-03-16 13:34:13,016 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2025-03-16 13:34:13,016 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2025-03-16 13:34:13,016 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2025-03-16 13:34:13,016 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2025-03-16 13:34:13,016 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2025-03-16 13:34:13,016 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#2 [2025-03-16 13:34:13,016 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-16 13:34:13,016 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-16 13:34:13,016 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2025-03-16 13:34:13,016 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2025-03-16 13:34:13,016 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#2 [2025-03-16 13:34:13,016 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2025-03-16 13:34:13,071 INFO L256 CfgBuilder]: Building ICFG [2025-03-16 13:34:13,073 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-16 13:34:13,225 INFO L? ?]: Removed 10 outVars from TransFormulas that were not future-live. [2025-03-16 13:34:13,225 INFO L307 CfgBuilder]: Performing block encoding [2025-03-16 13:34:13,232 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-16 13:34:13,233 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-16 13:34:13,233 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 16.03 01:34:13 BoogieIcfgContainer [2025-03-16 13:34:13,233 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-16 13:34:13,234 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-03-16 13:34:13,234 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-03-16 13:34:13,237 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-03-16 13:34:13,238 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 16.03 01:34:12" (1/3) ... [2025-03-16 13:34:13,238 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7c8fc956 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.03 01:34:13, skipping insertion in model container [2025-03-16 13:34:13,238 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 01:34:12" (2/3) ... [2025-03-16 13:34:13,238 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7c8fc956 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.03 01:34:13, skipping insertion in model container [2025-03-16 13:34:13,238 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 16.03 01:34:13" (3/3) ... [2025-03-16 13:34:13,239 INFO L128 eAbstractionObserver]: Analyzing ICFG mbpr4.c [2025-03-16 13:34:13,248 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-03-16 13:34:13,249 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG mbpr4.c that has 1 procedures, 28 locations, 1 initial locations, 5 loop locations, and 1 error locations. [2025-03-16 13:34:13,288 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-03-16 13:34:13,297 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;@5ad873d, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-03-16 13:34:13,298 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-03-16 13:34:13,301 INFO L276 IsEmpty]: Start isEmpty. Operand has 28 states, 26 states have (on average 1.5769230769230769) internal successors, (41), 27 states have internal predecessors, (41), 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 13:34:13,304 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2025-03-16 13:34:13,304 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:34:13,304 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:34:13,305 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:34:13,308 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:34:13,308 INFO L85 PathProgramCache]: Analyzing trace with hash 1349884748, now seen corresponding path program 1 times [2025-03-16 13:34:13,313 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:34:13,314 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1916315262] [2025-03-16 13:34:13,315 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 13:34:13,315 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:34:13,365 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 14 statements into 1 equivalence classes. [2025-03-16 13:34:13,381 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 14 of 14 statements. [2025-03-16 13:34:13,382 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 13:34:13,382 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:34:13,435 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-16 13:34:13,435 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:34:13,436 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1916315262] [2025-03-16 13:34:13,436 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1916315262] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 13:34:13,436 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 13:34:13,436 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2025-03-16 13:34:13,437 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1746739438] [2025-03-16 13:34:13,437 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 13:34:13,439 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2025-03-16 13:34:13,440 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:34:13,451 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2025-03-16 13:34:13,452 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-03-16 13:34:13,453 INFO L87 Difference]: Start difference. First operand has 28 states, 26 states have (on average 1.5769230769230769) internal successors, (41), 27 states have internal predecessors, (41), 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) Second operand has 2 states, 2 states have (on average 7.0) internal successors, (14), 2 states have internal predecessors, (14), 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 13:34:13,461 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:34:13,461 INFO L93 Difference]: Finished difference Result 52 states and 75 transitions. [2025-03-16 13:34:13,462 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2025-03-16 13:34:13,463 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 7.0) internal successors, (14), 2 states have internal predecessors, (14), 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) Word has length 14 [2025-03-16 13:34:13,463 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:34:13,466 INFO L225 Difference]: With dead ends: 52 [2025-03-16 13:34:13,466 INFO L226 Difference]: Without dead ends: 24 [2025-03-16 13:34:13,468 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-03-16 13:34:13,469 INFO L435 NwaCegarLoop]: 39 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 39 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-16 13:34:13,470 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 13:34:13,478 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states. [2025-03-16 13:34:13,485 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2025-03-16 13:34:13,486 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24 states, 23 states have (on average 1.434782608695652) internal successors, (33), 23 states have internal predecessors, (33), 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 13:34:13,490 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 33 transitions. [2025-03-16 13:34:13,491 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 33 transitions. Word has length 14 [2025-03-16 13:34:13,492 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:34:13,492 INFO L471 AbstractCegarLoop]: Abstraction has 24 states and 33 transitions. [2025-03-16 13:34:13,493 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 7.0) internal successors, (14), 2 states have internal predecessors, (14), 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 13:34:13,493 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 33 transitions. [2025-03-16 13:34:13,494 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2025-03-16 13:34:13,494 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:34:13,494 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:34:13,494 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2025-03-16 13:34:13,495 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:34:13,496 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:34:13,496 INFO L85 PathProgramCache]: Analyzing trace with hash -447066611, now seen corresponding path program 1 times [2025-03-16 13:34:13,496 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:34:13,496 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1176091203] [2025-03-16 13:34:13,496 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 13:34:13,497 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:34:13,512 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 14 statements into 1 equivalence classes. [2025-03-16 13:34:13,531 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 14 of 14 statements. [2025-03-16 13:34:13,531 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 13:34:13,531 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:34:13,779 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-16 13:34:13,779 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:34:13,779 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1176091203] [2025-03-16 13:34:13,779 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1176091203] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 13:34:13,779 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 13:34:13,780 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-16 13:34:13,780 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1037226340] [2025-03-16 13:34:13,780 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 13:34:13,780 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-16 13:34:13,781 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:34:13,782 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-16 13:34:13,783 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2025-03-16 13:34:13,783 INFO L87 Difference]: Start difference. First operand 24 states and 33 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 5 states have internal predecessors, (14), 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 13:34:13,871 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:34:13,871 INFO L93 Difference]: Finished difference Result 52 states and 76 transitions. [2025-03-16 13:34:13,871 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-16 13:34:13,871 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 5 states have internal predecessors, (14), 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) Word has length 14 [2025-03-16 13:34:13,871 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:34:13,872 INFO L225 Difference]: With dead ends: 52 [2025-03-16 13:34:13,872 INFO L226 Difference]: Without dead ends: 36 [2025-03-16 13:34:13,872 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2025-03-16 13:34:13,873 INFO L435 NwaCegarLoop]: 11 mSDtfsCounter, 70 mSDsluCounter, 6 mSDsCounter, 0 mSdLazyCounter, 47 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 70 SdHoareTripleChecker+Valid, 17 SdHoareTripleChecker+Invalid, 53 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 47 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 13:34:13,873 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [70 Valid, 17 Invalid, 53 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 47 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 13:34:13,873 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36 states. [2025-03-16 13:34:13,879 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36 to 28. [2025-03-16 13:34:13,879 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 28 states, 27 states have (on average 1.3703703703703705) internal successors, (37), 27 states have internal predecessors, (37), 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 13:34:13,879 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28 states to 28 states and 37 transitions. [2025-03-16 13:34:13,880 INFO L78 Accepts]: Start accepts. Automaton has 28 states and 37 transitions. Word has length 14 [2025-03-16 13:34:13,880 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:34:13,880 INFO L471 AbstractCegarLoop]: Abstraction has 28 states and 37 transitions. [2025-03-16 13:34:13,880 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 5 states have internal predecessors, (14), 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 13:34:13,880 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 37 transitions. [2025-03-16 13:34:13,880 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2025-03-16 13:34:13,880 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:34:13,881 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:34:13,881 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2025-03-16 13:34:13,881 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:34:13,881 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:34:13,881 INFO L85 PathProgramCache]: Analyzing trace with hash -81109714, now seen corresponding path program 1 times [2025-03-16 13:34:13,881 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:34:13,881 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1155843381] [2025-03-16 13:34:13,881 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 13:34:13,881 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:34:13,899 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 26 statements into 1 equivalence classes. [2025-03-16 13:34:13,930 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 26 of 26 statements. [2025-03-16 13:34:13,931 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 13:34:13,931 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:34:15,118 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-16 13:34:15,119 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:34:15,119 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1155843381] [2025-03-16 13:34:15,120 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1155843381] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:34:15,120 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1065389553] [2025-03-16 13:34:15,120 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 13:34:15,120 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:34:15,121 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:34:15,122 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 13:34:15,123 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2025-03-16 13:34:15,171 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 26 statements into 1 equivalence classes. [2025-03-16 13:34:15,194 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 26 of 26 statements. [2025-03-16 13:34:15,195 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 13:34:15,195 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:34:15,197 INFO L256 TraceCheckSpWp]: Trace formula consists of 162 conjuncts, 36 conjuncts are in the unsatisfiable core [2025-03-16 13:34:15,202 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:34:15,308 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-03-16 13:34:15,336 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:34:15,336 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 6 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 37 treesize of output 18 [2025-03-16 13:34:15,375 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 11 [2025-03-16 13:34:15,396 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:34:15,397 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 48 treesize of output 18 [2025-03-16 13:34:15,430 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 11 [2025-03-16 13:34:15,449 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:34:15,449 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 48 treesize of output 18 [2025-03-16 13:34:15,483 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 18 [2025-03-16 13:34:15,524 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:34:15,526 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 6 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 44 treesize of output 35 [2025-03-16 13:34:15,593 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:34:15,594 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 22 treesize of output 10 [2025-03-16 13:34:15,613 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-16 13:34:15,614 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:34:15,772 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 15 [2025-03-16 13:34:15,775 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 20 [2025-03-16 13:34:15,809 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2025-03-16 13:34:15,809 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1065389553] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 13:34:15,809 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 13:34:15,809 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 10, 7] total 20 [2025-03-16 13:34:15,809 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1754397241] [2025-03-16 13:34:15,809 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 13:34:15,810 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2025-03-16 13:34:15,810 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:34:15,810 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2025-03-16 13:34:15,811 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=73, Invalid=307, Unknown=0, NotChecked=0, Total=380 [2025-03-16 13:34:15,811 INFO L87 Difference]: Start difference. First operand 28 states and 37 transitions. Second operand has 20 states, 20 states have (on average 3.45) internal successors, (69), 20 states have internal predecessors, (69), 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 13:34:16,181 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:34:16,181 INFO L93 Difference]: Finished difference Result 102 states and 131 transitions. [2025-03-16 13:34:16,182 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2025-03-16 13:34:16,182 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 20 states have (on average 3.45) internal successors, (69), 20 states have internal predecessors, (69), 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) Word has length 26 [2025-03-16 13:34:16,182 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:34:16,182 INFO L225 Difference]: With dead ends: 102 [2025-03-16 13:34:16,183 INFO L226 Difference]: Without dead ends: 80 [2025-03-16 13:34:16,183 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 80 GetRequests, 45 SyntacticMatches, 4 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 249 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=268, Invalid=788, Unknown=0, NotChecked=0, Total=1056 [2025-03-16 13:34:16,184 INFO L435 NwaCegarLoop]: 19 mSDtfsCounter, 266 mSDsluCounter, 75 mSDsCounter, 0 mSdLazyCounter, 241 mSolverCounterSat, 59 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 266 SdHoareTripleChecker+Valid, 94 SdHoareTripleChecker+Invalid, 300 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 59 IncrementalHoareTripleChecker+Valid, 241 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-16 13:34:16,184 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [266 Valid, 94 Invalid, 300 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [59 Valid, 241 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-16 13:34:16,184 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 80 states. [2025-03-16 13:34:16,188 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 80 to 30. [2025-03-16 13:34:16,188 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 29 states have (on average 1.3103448275862069) internal successors, (38), 29 states have internal predecessors, (38), 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 13:34:16,188 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 38 transitions. [2025-03-16 13:34:16,189 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 38 transitions. Word has length 26 [2025-03-16 13:34:16,189 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:34:16,189 INFO L471 AbstractCegarLoop]: Abstraction has 30 states and 38 transitions. [2025-03-16 13:34:16,189 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 20 states have (on average 3.45) internal successors, (69), 20 states have internal predecessors, (69), 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 13:34:16,189 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 38 transitions. [2025-03-16 13:34:16,189 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2025-03-16 13:34:16,189 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:34:16,189 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:34:16,197 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2025-03-16 13:34:16,395 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:34:16,395 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:34:16,395 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:34:16,396 INFO L85 PathProgramCache]: Analyzing trace with hash -81079923, now seen corresponding path program 1 times [2025-03-16 13:34:16,396 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:34:16,396 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1363269032] [2025-03-16 13:34:16,396 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 13:34:16,396 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:34:16,405 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 26 statements into 1 equivalence classes. [2025-03-16 13:34:16,412 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 26 of 26 statements. [2025-03-16 13:34:16,412 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 13:34:16,412 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:34:16,456 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-16 13:34:16,457 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:34:16,457 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1363269032] [2025-03-16 13:34:16,457 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1363269032] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 13:34:16,457 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 13:34:16,457 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2025-03-16 13:34:16,457 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [815376459] [2025-03-16 13:34:16,457 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 13:34:16,458 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2025-03-16 13:34:16,458 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:34:16,458 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2025-03-16 13:34:16,458 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2025-03-16 13:34:16,458 INFO L87 Difference]: Start difference. First operand 30 states and 38 transitions. Second operand has 4 states, 4 states have (on average 6.5) internal successors, (26), 4 states have internal predecessors, (26), 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 13:34:16,473 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:34:16,473 INFO L93 Difference]: Finished difference Result 34 states and 42 transitions. [2025-03-16 13:34:16,473 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2025-03-16 13:34:16,474 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 6.5) internal successors, (26), 4 states have internal predecessors, (26), 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) Word has length 26 [2025-03-16 13:34:16,474 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:34:16,474 INFO L225 Difference]: With dead ends: 34 [2025-03-16 13:34:16,474 INFO L226 Difference]: Without dead ends: 32 [2025-03-16 13:34:16,474 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2025-03-16 13:34:16,475 INFO L435 NwaCegarLoop]: 30 mSDtfsCounter, 0 mSDsluCounter, 53 mSDsCounter, 0 mSdLazyCounter, 12 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 83 SdHoareTripleChecker+Invalid, 12 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 12 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-16 13:34:16,475 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 83 Invalid, 12 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 12 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 13:34:16,475 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2025-03-16 13:34:16,477 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2025-03-16 13:34:16,478 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 31 states have (on average 1.2903225806451613) internal successors, (40), 31 states have internal predecessors, (40), 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 13:34:16,478 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 40 transitions. [2025-03-16 13:34:16,478 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 40 transitions. Word has length 26 [2025-03-16 13:34:16,478 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:34:16,478 INFO L471 AbstractCegarLoop]: Abstraction has 32 states and 40 transitions. [2025-03-16 13:34:16,478 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 6.5) internal successors, (26), 4 states have internal predecessors, (26), 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 13:34:16,478 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 40 transitions. [2025-03-16 13:34:16,479 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2025-03-16 13:34:16,479 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:34:16,479 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:34:16,479 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2025-03-16 13:34:16,479 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:34:16,480 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:34:16,480 INFO L85 PathProgramCache]: Analyzing trace with hash 917860608, now seen corresponding path program 1 times [2025-03-16 13:34:16,480 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:34:16,480 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2110906822] [2025-03-16 13:34:16,480 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 13:34:16,480 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:34:16,487 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-03-16 13:34:16,497 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-03-16 13:34:16,498 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 13:34:16,498 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:34:17,080 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 2 proven. 5 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2025-03-16 13:34:17,081 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:34:17,081 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2110906822] [2025-03-16 13:34:17,081 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2110906822] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:34:17,081 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [755149971] [2025-03-16 13:34:17,081 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 13:34:17,082 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:34:17,082 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:34:17,085 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 13:34:17,086 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2025-03-16 13:34:17,126 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-03-16 13:34:17,147 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-03-16 13:34:17,147 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 13:34:17,147 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:34:17,155 INFO L256 TraceCheckSpWp]: Trace formula consists of 174 conjuncts, 31 conjuncts are in the unsatisfiable core [2025-03-16 13:34:17,158 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:34:17,224 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-03-16 13:34:17,250 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:34:17,251 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 6 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 37 treesize of output 18 [2025-03-16 13:34:17,285 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 11 [2025-03-16 13:34:17,295 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 37 treesize of output 11 [2025-03-16 13:34:17,315 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 18 [2025-03-16 13:34:17,360 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:34:17,360 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 6 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 44 treesize of output 35 [2025-03-16 13:34:17,443 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:34:17,444 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 22 treesize of output 10 [2025-03-16 13:34:17,459 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 2 proven. 5 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2025-03-16 13:34:17,459 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:34:17,589 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 17 [2025-03-16 13:34:17,590 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 20 [2025-03-16 13:34:17,628 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 2 proven. 3 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2025-03-16 13:34:17,629 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [755149971] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 13:34:17,629 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 13:34:17,629 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 10, 8] total 21 [2025-03-16 13:34:17,629 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1148620224] [2025-03-16 13:34:17,629 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 13:34:17,630 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2025-03-16 13:34:17,630 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:34:17,631 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2025-03-16 13:34:17,631 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=78, Invalid=342, Unknown=0, NotChecked=0, Total=420 [2025-03-16 13:34:17,631 INFO L87 Difference]: Start difference. First operand 32 states and 40 transitions. Second operand has 21 states, 21 states have (on average 4.0) internal successors, (84), 21 states have internal predecessors, (84), 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 13:34:18,020 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:34:18,021 INFO L93 Difference]: Finished difference Result 97 states and 122 transitions. [2025-03-16 13:34:18,021 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2025-03-16 13:34:18,021 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 21 states have (on average 4.0) internal successors, (84), 21 states have internal predecessors, (84), 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) Word has length 31 [2025-03-16 13:34:18,022 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:34:18,023 INFO L225 Difference]: With dead ends: 97 [2025-03-16 13:34:18,023 INFO L226 Difference]: Without dead ends: 75 [2025-03-16 13:34:18,023 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 89 GetRequests, 53 SyntacticMatches, 3 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 265 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=293, Invalid=897, Unknown=0, NotChecked=0, Total=1190 [2025-03-16 13:34:18,025 INFO L435 NwaCegarLoop]: 15 mSDtfsCounter, 164 mSDsluCounter, 94 mSDsCounter, 0 mSdLazyCounter, 341 mSolverCounterSat, 48 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 164 SdHoareTripleChecker+Valid, 109 SdHoareTripleChecker+Invalid, 389 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 48 IncrementalHoareTripleChecker+Valid, 341 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-16 13:34:18,025 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [164 Valid, 109 Invalid, 389 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [48 Valid, 341 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-16 13:34:18,026 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 75 states. [2025-03-16 13:34:18,030 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 75 to 37. [2025-03-16 13:34:18,030 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 36 states have (on average 1.2222222222222223) internal successors, (44), 36 states have internal predecessors, (44), 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 13:34:18,031 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 44 transitions. [2025-03-16 13:34:18,031 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 44 transitions. Word has length 31 [2025-03-16 13:34:18,031 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:34:18,031 INFO L471 AbstractCegarLoop]: Abstraction has 37 states and 44 transitions. [2025-03-16 13:34:18,031 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 21 states have (on average 4.0) internal successors, (84), 21 states have internal predecessors, (84), 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 13:34:18,031 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 44 transitions. [2025-03-16 13:34:18,032 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2025-03-16 13:34:18,032 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:34:18,032 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:34:18,038 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2025-03-16 13:34:18,236 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:34:18,236 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:34:18,236 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:34:18,236 INFO L85 PathProgramCache]: Analyzing trace with hash 1282928750, now seen corresponding path program 2 times [2025-03-16 13:34:18,236 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:34:18,237 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [739040285] [2025-03-16 13:34:18,237 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 13:34:18,237 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:34:18,245 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 36 statements into 2 equivalence classes. [2025-03-16 13:34:18,271 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 36 of 36 statements. [2025-03-16 13:34:18,271 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 13:34:18,271 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:34:18,677 INFO L134 CoverageAnalysis]: Checked inductivity of 17 backedges. 4 proven. 11 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2025-03-16 13:34:18,677 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:34:18,678 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [739040285] [2025-03-16 13:34:18,678 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [739040285] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:34:18,678 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [870391619] [2025-03-16 13:34:18,678 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 13:34:18,678 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:34:18,679 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:34:18,680 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 13:34:18,682 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2025-03-16 13:34:18,728 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 36 statements into 2 equivalence classes. [2025-03-16 13:34:18,749 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 36 of 36 statements. [2025-03-16 13:34:18,750 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 13:34:18,750 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:34:18,751 INFO L256 TraceCheckSpWp]: Trace formula consists of 186 conjuncts, 29 conjuncts are in the unsatisfiable core [2025-03-16 13:34:18,753 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:34:18,845 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-03-16 13:34:18,863 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:34:18,863 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 6 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 37 treesize of output 18 [2025-03-16 13:34:18,896 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 18 [2025-03-16 13:34:18,917 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:34:18,917 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 6 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 44 treesize of output 35 [2025-03-16 13:34:19,047 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:34:19,047 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 22 treesize of output 10 [2025-03-16 13:34:19,056 INFO L134 CoverageAnalysis]: Checked inductivity of 17 backedges. 4 proven. 11 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2025-03-16 13:34:19,057 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:34:19,172 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 17 [2025-03-16 13:34:19,175 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 20 [2025-03-16 13:34:19,217 INFO L134 CoverageAnalysis]: Checked inductivity of 17 backedges. 4 proven. 10 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2025-03-16 13:34:19,217 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [870391619] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 13:34:19,217 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 13:34:19,217 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 11, 9] total 24 [2025-03-16 13:34:19,218 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2056396449] [2025-03-16 13:34:19,218 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 13:34:19,218 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2025-03-16 13:34:19,218 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:34:19,218 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2025-03-16 13:34:19,219 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=90, Invalid=462, Unknown=0, NotChecked=0, Total=552 [2025-03-16 13:34:19,219 INFO L87 Difference]: Start difference. First operand 37 states and 44 transitions. Second operand has 24 states, 24 states have (on average 4.083333333333333) internal successors, (98), 24 states have internal predecessors, (98), 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 13:34:19,746 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:34:19,746 INFO L93 Difference]: Finished difference Result 116 states and 143 transitions. [2025-03-16 13:34:19,746 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2025-03-16 13:34:19,747 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 24 states have (on average 4.083333333333333) internal successors, (98), 24 states have internal predecessors, (98), 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) Word has length 36 [2025-03-16 13:34:19,747 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:34:19,747 INFO L225 Difference]: With dead ends: 116 [2025-03-16 13:34:19,747 INFO L226 Difference]: Without dead ends: 93 [2025-03-16 13:34:19,748 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 103 GetRequests, 59 SyntacticMatches, 2 SemanticMatches, 42 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 416 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=386, Invalid=1506, Unknown=0, NotChecked=0, Total=1892 [2025-03-16 13:34:19,748 INFO L435 NwaCegarLoop]: 14 mSDtfsCounter, 241 mSDsluCounter, 90 mSDsCounter, 0 mSdLazyCounter, 426 mSolverCounterSat, 87 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 241 SdHoareTripleChecker+Valid, 104 SdHoareTripleChecker+Invalid, 513 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 87 IncrementalHoareTripleChecker+Valid, 426 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-03-16 13:34:19,749 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [241 Valid, 104 Invalid, 513 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [87 Valid, 426 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-03-16 13:34:19,749 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 93 states. [2025-03-16 13:34:19,752 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 93 to 42. [2025-03-16 13:34:19,752 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 42 states, 41 states have (on average 1.170731707317073) internal successors, (48), 41 states have internal predecessors, (48), 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 13:34:19,753 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 42 states to 42 states and 48 transitions. [2025-03-16 13:34:19,753 INFO L78 Accepts]: Start accepts. Automaton has 42 states and 48 transitions. Word has length 36 [2025-03-16 13:34:19,753 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:34:19,753 INFO L471 AbstractCegarLoop]: Abstraction has 42 states and 48 transitions. [2025-03-16 13:34:19,753 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 24 states have (on average 4.083333333333333) internal successors, (98), 24 states have internal predecessors, (98), 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 13:34:19,753 INFO L276 IsEmpty]: Start isEmpty. Operand 42 states and 48 transitions. [2025-03-16 13:34:19,754 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2025-03-16 13:34:19,754 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:34:19,754 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:34:19,760 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2025-03-16 13:34:19,958 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:34:19,958 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:34:19,958 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:34:19,958 INFO L85 PathProgramCache]: Analyzing trace with hash -215882304, now seen corresponding path program 3 times [2025-03-16 13:34:19,958 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:34:19,959 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1654766119] [2025-03-16 13:34:19,959 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 13:34:19,959 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:34:19,974 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 41 statements into 4 equivalence classes. [2025-03-16 13:34:20,002 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) and asserted 41 of 41 statements. [2025-03-16 13:34:20,003 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2025-03-16 13:34:20,003 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:34:20,474 INFO L134 CoverageAnalysis]: Checked inductivity of 31 backedges. 5 proven. 24 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2025-03-16 13:34:20,474 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:34:20,474 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1654766119] [2025-03-16 13:34:20,474 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1654766119] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:34:20,474 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1926169473] [2025-03-16 13:34:20,474 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 13:34:20,474 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:34:20,474 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:34:20,476 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 13:34:20,478 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2025-03-16 13:34:20,520 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 41 statements into 4 equivalence classes. [2025-03-16 13:34:20,575 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) and asserted 41 of 41 statements. [2025-03-16 13:34:20,575 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2025-03-16 13:34:20,575 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:34:20,577 INFO L256 TraceCheckSpWp]: Trace formula consists of 198 conjuncts, 24 conjuncts are in the unsatisfiable core [2025-03-16 13:34:20,578 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:34:20,607 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 9 [2025-03-16 13:34:20,626 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:34:20,626 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 47 treesize of output 38 [2025-03-16 13:34:20,726 INFO L134 CoverageAnalysis]: Checked inductivity of 31 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2025-03-16 13:34:20,726 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:34:20,818 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 15 [2025-03-16 13:34:20,820 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 12 [2025-03-16 13:34:20,822 INFO L134 CoverageAnalysis]: Checked inductivity of 31 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2025-03-16 13:34:20,822 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1926169473] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 13:34:20,822 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 13:34:20,822 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 10, 10] total 28 [2025-03-16 13:34:20,822 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1871656892] [2025-03-16 13:34:20,822 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 13:34:20,823 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 28 states [2025-03-16 13:34:20,823 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:34:20,823 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2025-03-16 13:34:20,823 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=107, Invalid=649, Unknown=0, NotChecked=0, Total=756 [2025-03-16 13:34:20,823 INFO L87 Difference]: Start difference. First operand 42 states and 48 transitions. Second operand has 28 states, 28 states have (on average 3.5714285714285716) internal successors, (100), 28 states have internal predecessors, (100), 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 13:34:21,844 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:34:21,845 INFO L93 Difference]: Finished difference Result 194 states and 230 transitions. [2025-03-16 13:34:21,845 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 45 states. [2025-03-16 13:34:21,845 INFO L78 Accepts]: Start accepts. Automaton has has 28 states, 28 states have (on average 3.5714285714285716) internal successors, (100), 28 states have internal predecessors, (100), 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) Word has length 41 [2025-03-16 13:34:21,845 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:34:21,846 INFO L225 Difference]: With dead ends: 194 [2025-03-16 13:34:21,846 INFO L226 Difference]: Without dead ends: 145 [2025-03-16 13:34:21,847 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 145 GetRequests, 76 SyntacticMatches, 1 SemanticMatches, 68 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1362 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=748, Invalid=4082, Unknown=0, NotChecked=0, Total=4830 [2025-03-16 13:34:21,848 INFO L435 NwaCegarLoop]: 12 mSDtfsCounter, 330 mSDsluCounter, 115 mSDsCounter, 0 mSdLazyCounter, 635 mSolverCounterSat, 86 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 330 SdHoareTripleChecker+Valid, 127 SdHoareTripleChecker+Invalid, 721 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 86 IncrementalHoareTripleChecker+Valid, 635 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-03-16 13:34:21,848 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [330 Valid, 127 Invalid, 721 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [86 Valid, 635 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-03-16 13:34:21,848 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 145 states. [2025-03-16 13:34:21,861 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 145 to 88. [2025-03-16 13:34:21,861 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 88 states, 87 states have (on average 1.2183908045977012) internal successors, (106), 87 states have internal predecessors, (106), 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 13:34:21,863 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 88 states to 88 states and 106 transitions. [2025-03-16 13:34:21,864 INFO L78 Accepts]: Start accepts. Automaton has 88 states and 106 transitions. Word has length 41 [2025-03-16 13:34:21,865 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:34:21,865 INFO L471 AbstractCegarLoop]: Abstraction has 88 states and 106 transitions. [2025-03-16 13:34:21,865 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 28 states, 28 states have (on average 3.5714285714285716) internal successors, (100), 28 states have internal predecessors, (100), 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 13:34:21,865 INFO L276 IsEmpty]: Start isEmpty. Operand 88 states and 106 transitions. [2025-03-16 13:34:21,866 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2025-03-16 13:34:21,866 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:34:21,866 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:34:21,874 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2025-03-16 13:34:22,070 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:34:22,070 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:34:22,070 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:34:22,070 INFO L85 PathProgramCache]: Analyzing trace with hash -1460646785, now seen corresponding path program 1 times [2025-03-16 13:34:22,070 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:34:22,070 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2143969907] [2025-03-16 13:34:22,071 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 13:34:22,071 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:34:22,079 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 41 statements into 1 equivalence classes. [2025-03-16 13:34:22,082 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 41 of 41 statements. [2025-03-16 13:34:22,083 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 13:34:22,083 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:34:22,114 INFO L134 CoverageAnalysis]: Checked inductivity of 31 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2025-03-16 13:34:22,114 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:34:22,114 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2143969907] [2025-03-16 13:34:22,114 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2143969907] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 13:34:22,114 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 13:34:22,114 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2025-03-16 13:34:22,115 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [352326819] [2025-03-16 13:34:22,115 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 13:34:22,115 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2025-03-16 13:34:22,115 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:34:22,115 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2025-03-16 13:34:22,115 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2025-03-16 13:34:22,116 INFO L87 Difference]: Start difference. First operand 88 states and 106 transitions. Second operand has 3 states, 3 states have (on average 9.666666666666666) internal successors, (29), 3 states have internal predecessors, (29), 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 13:34:22,125 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:34:22,125 INFO L93 Difference]: Finished difference Result 120 states and 144 transitions. [2025-03-16 13:34:22,126 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2025-03-16 13:34:22,126 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 9.666666666666666) internal successors, (29), 3 states have internal predecessors, (29), 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) Word has length 41 [2025-03-16 13:34:22,126 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:34:22,126 INFO L225 Difference]: With dead ends: 120 [2025-03-16 13:34:22,126 INFO L226 Difference]: Without dead ends: 63 [2025-03-16 13:34:22,127 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2025-03-16 13:34:22,127 INFO L435 NwaCegarLoop]: 24 mSDtfsCounter, 11 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 6 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 24 SdHoareTripleChecker+Invalid, 6 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 6 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-16 13:34:22,127 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 24 Invalid, 6 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 6 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 13:34:22,127 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2025-03-16 13:34:22,132 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 59. [2025-03-16 13:34:22,134 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 59 states, 58 states have (on average 1.1206896551724137) internal successors, (65), 58 states have internal predecessors, (65), 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 13:34:22,134 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 59 states to 59 states and 65 transitions. [2025-03-16 13:34:22,135 INFO L78 Accepts]: Start accepts. Automaton has 59 states and 65 transitions. Word has length 41 [2025-03-16 13:34:22,135 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:34:22,135 INFO L471 AbstractCegarLoop]: Abstraction has 59 states and 65 transitions. [2025-03-16 13:34:22,136 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 9.666666666666666) internal successors, (29), 3 states have internal predecessors, (29), 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 13:34:22,136 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 65 transitions. [2025-03-16 13:34:22,136 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2025-03-16 13:34:22,137 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:34:22,137 INFO L218 NwaCegarLoop]: trace histogram [5, 5, 4, 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:34:22,137 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7 [2025-03-16 13:34:22,137 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:34:22,138 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:34:22,138 INFO L85 PathProgramCache]: Analyzing trace with hash 1381732076, now seen corresponding path program 4 times [2025-03-16 13:34:22,138 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:34:22,138 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [589556261] [2025-03-16 13:34:22,138 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-16 13:34:22,138 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:34:22,153 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 58 statements into 2 equivalence classes. [2025-03-16 13:34:22,180 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 58 of 58 statements. [2025-03-16 13:34:22,183 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-03-16 13:34:22,184 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:34:23,327 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 8 proven. 43 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2025-03-16 13:34:23,328 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:34:23,328 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [589556261] [2025-03-16 13:34:23,328 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [589556261] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:34:23,328 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1513048400] [2025-03-16 13:34:23,328 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-16 13:34:23,328 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:34:23,328 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:34:23,330 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 13:34:23,331 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2025-03-16 13:34:23,379 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 58 statements into 2 equivalence classes. [2025-03-16 13:34:23,411 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 58 of 58 statements. [2025-03-16 13:34:23,411 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-03-16 13:34:23,411 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:34:23,413 INFO L256 TraceCheckSpWp]: Trace formula consists of 277 conjuncts, 64 conjuncts are in the unsatisfiable core [2025-03-16 13:34:23,416 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:34:23,493 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-03-16 13:34:23,514 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:34:23,514 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 6 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 37 treesize of output 18 [2025-03-16 13:34:23,557 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 18 [2025-03-16 13:34:23,594 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:34:23,595 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 10 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 44 treesize of output 28 [2025-03-16 13:34:23,629 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:34:23,629 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 23 treesize of output 25 [2025-03-16 13:34:23,670 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:34:23,670 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 10 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 59 treesize of output 35 [2025-03-16 13:34:23,732 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:34:23,733 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 6 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 30 treesize of output 35 [2025-03-16 13:34:23,779 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:34:23,779 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 15 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 55 treesize of output 38 [2025-03-16 13:34:23,817 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:34:23,818 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 10 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 34 treesize of output 42 [2025-03-16 13:34:23,859 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:34:23,859 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 5 select indices, 5 select index equivalence classes, 15 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 10 case distinctions, treesize of input 70 treesize of output 45 [2025-03-16 13:34:23,934 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:34:23,934 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 5 select indices, 5 select index equivalence classes, 15 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 10 case distinctions, treesize of input 41 treesize of output 52 [2025-03-16 13:34:23,980 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:34:23,980 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 7 select indices, 7 select index equivalence classes, 21 disjoint index pairs (out of 21 index pairs), introduced 7 new quantified variables, introduced 21 case distinctions, treesize of input 66 treesize of output 62 [2025-03-16 13:34:24,038 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:34:24,039 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 6 select indices, 6 select index equivalence classes, 21 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 15 case distinctions, treesize of input 48 treesize of output 62 [2025-03-16 13:34:24,087 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:34:24,088 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 7 select indices, 7 select index equivalence classes, 21 disjoint index pairs (out of 21 index pairs), introduced 7 new quantified variables, introduced 21 case distinctions, treesize of input 73 treesize of output 65 [2025-03-16 13:34:24,467 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:34:24,467 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 7 select indices, 7 select index equivalence classes, 21 disjoint index pairs (out of 21 index pairs), introduced 7 new quantified variables, introduced 21 case distinctions, treesize of input 51 treesize of output 19 [2025-03-16 13:34:24,474 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 8 proven. 58 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-16 13:34:24,474 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:34:24,889 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 17 [2025-03-16 13:34:24,891 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 20 [2025-03-16 13:34:24,970 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 8 proven. 51 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2025-03-16 13:34:24,970 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1513048400] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 13:34:24,970 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 13:34:24,970 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 27, 13] total 47 [2025-03-16 13:34:24,970 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1999198621] [2025-03-16 13:34:24,970 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 13:34:24,971 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 47 states [2025-03-16 13:34:24,971 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:34:24,971 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 47 interpolants. [2025-03-16 13:34:24,971 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=245, Invalid=1917, Unknown=0, NotChecked=0, Total=2162 [2025-03-16 13:34:24,972 INFO L87 Difference]: Start difference. First operand 59 states and 65 transitions. Second operand has 47 states, 47 states have (on average 3.234042553191489) internal successors, (152), 47 states have internal predecessors, (152), 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 13:34:29,406 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2025-03-16 13:34:33,426 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2025-03-16 13:34:37,442 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2025-03-16 13:34:41,449 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [1] [2025-03-16 13:34:43,451 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:34:43,451 INFO L93 Difference]: Finished difference Result 250 states and 288 transitions. [2025-03-16 13:34:43,452 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 69 states. [2025-03-16 13:34:43,452 INFO L78 Accepts]: Start accepts. Automaton has has 47 states, 47 states have (on average 3.234042553191489) internal successors, (152), 47 states have internal predecessors, (152), 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) Word has length 58 [2025-03-16 13:34:43,452 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:34:43,454 INFO L225 Difference]: With dead ends: 250 [2025-03-16 13:34:43,455 INFO L226 Difference]: Without dead ends: 241 [2025-03-16 13:34:43,458 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 209 GetRequests, 87 SyntacticMatches, 10 SemanticMatches, 112 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4095 ImplicationChecksByTransitivity, 2.4s TimeCoverageRelationStatistics Valid=1597, Invalid=11285, Unknown=0, NotChecked=0, Total=12882 [2025-03-16 13:34:43,459 INFO L435 NwaCegarLoop]: 16 mSDtfsCounter, 958 mSDsluCounter, 296 mSDsCounter, 0 mSdLazyCounter, 1672 mSolverCounterSat, 355 mSolverCounterUnsat, 4 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 16.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 958 SdHoareTripleChecker+Valid, 312 SdHoareTripleChecker+Invalid, 2031 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 355 IncrementalHoareTripleChecker+Valid, 1672 IncrementalHoareTripleChecker+Invalid, 4 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 17.0s IncrementalHoareTripleChecker+Time [2025-03-16 13:34:43,460 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [958 Valid, 312 Invalid, 2031 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [355 Valid, 1672 Invalid, 4 Unknown, 0 Unchecked, 17.0s Time] [2025-03-16 13:34:43,460 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 241 states. [2025-03-16 13:34:43,473 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 241 to 64. [2025-03-16 13:34:43,473 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 64 states, 63 states have (on average 1.1111111111111112) internal successors, (70), 63 states have internal predecessors, (70), 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 13:34:43,473 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 70 transitions. [2025-03-16 13:34:43,473 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 70 transitions. Word has length 58 [2025-03-16 13:34:43,473 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:34:43,473 INFO L471 AbstractCegarLoop]: Abstraction has 64 states and 70 transitions. [2025-03-16 13:34:43,473 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 47 states, 47 states have (on average 3.234042553191489) internal successors, (152), 47 states have internal predecessors, (152), 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 13:34:43,473 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 70 transitions. [2025-03-16 13:34:43,474 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 64 [2025-03-16 13:34:43,474 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:34:43,474 INFO L218 NwaCegarLoop]: trace histogram [6, 6, 5, 5, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:34:43,481 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2025-03-16 13:34:43,679 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:34:43,679 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:34:43,679 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:34:43,680 INFO L85 PathProgramCache]: Analyzing trace with hash -1747737086, now seen corresponding path program 5 times [2025-03-16 13:34:43,680 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:34:43,680 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1842121577] [2025-03-16 13:34:43,680 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-03-16 13:34:43,680 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:34:43,690 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 63 statements into 6 equivalence classes. [2025-03-16 13:34:43,714 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) and asserted 63 of 63 statements. [2025-03-16 13:34:43,716 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2025-03-16 13:34:43,716 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:34:44,647 INFO L134 CoverageAnalysis]: Checked inductivity of 90 backedges. 10 proven. 70 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2025-03-16 13:34:44,647 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:34:44,648 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1842121577] [2025-03-16 13:34:44,648 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1842121577] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:34:44,648 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2140746370] [2025-03-16 13:34:44,648 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-03-16 13:34:44,648 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:34:44,648 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:34:44,650 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 13:34:44,652 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2025-03-16 13:34:44,708 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 63 statements into 6 equivalence classes. [2025-03-16 13:34:47,763 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) and asserted 63 of 63 statements. [2025-03-16 13:34:47,763 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2025-03-16 13:34:47,763 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:34:47,768 INFO L256 TraceCheckSpWp]: Trace formula consists of 289 conjuncts, 55 conjuncts are in the unsatisfiable core [2025-03-16 13:34:47,771 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:34:47,861 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-03-16 13:34:47,885 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:34:47,886 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 6 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 37 treesize of output 18 [2025-03-16 13:34:47,937 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 18 [2025-03-16 13:34:47,975 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:34:47,976 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 10 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 44 treesize of output 28 [2025-03-16 13:34:48,009 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:34:48,009 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 23 treesize of output 25 [2025-03-16 13:34:48,033 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:34:48,033 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 10 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 48 treesize of output 28 [2025-03-16 13:34:48,088 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:34:48,088 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 6 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 30 treesize of output 35 [2025-03-16 13:34:48,121 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:34:48,121 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 6 select indices, 6 select index equivalence classes, 15 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 15 case distinctions, treesize of input 55 treesize of output 52 [2025-03-16 13:34:48,160 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:34:48,160 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 10 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 37 treesize of output 45 [2025-03-16 13:34:48,203 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:34:48,204 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 6 select indices, 6 select index equivalence classes, 15 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 15 case distinctions, treesize of input 62 treesize of output 55 [2025-03-16 13:34:48,590 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:34:48,590 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 5 select indices, 5 select index equivalence classes, 10 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 10 case distinctions, treesize of input 40 treesize of output 16 [2025-03-16 13:34:48,595 INFO L134 CoverageAnalysis]: Checked inductivity of 90 backedges. 10 proven. 79 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2025-03-16 13:34:48,595 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:34:48,883 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 17 [2025-03-16 13:34:48,888 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 20 [2025-03-16 13:34:48,966 INFO L134 CoverageAnalysis]: Checked inductivity of 90 backedges. 10 proven. 65 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2025-03-16 13:34:48,966 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2140746370] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 13:34:48,966 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 13:34:48,966 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 23, 13] total 44 [2025-03-16 13:34:48,966 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1843603385] [2025-03-16 13:34:48,966 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 13:34:48,967 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 44 states [2025-03-16 13:34:48,967 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:34:48,967 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 44 interpolants. [2025-03-16 13:34:48,967 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=231, Invalid=1661, Unknown=0, NotChecked=0, Total=1892 [2025-03-16 13:34:48,968 INFO L87 Difference]: Start difference. First operand 64 states and 70 transitions. Second operand has 44 states, 44 states have (on average 3.727272727272727) internal successors, (164), 44 states have internal predecessors, (164), 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 13:34:50,483 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:34:50,483 INFO L93 Difference]: Finished difference Result 176 states and 201 transitions. [2025-03-16 13:34:50,483 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 51 states. [2025-03-16 13:34:50,483 INFO L78 Accepts]: Start accepts. Automaton has has 44 states, 44 states have (on average 3.727272727272727) internal successors, (164), 44 states have internal predecessors, (164), 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) Word has length 63 [2025-03-16 13:34:50,483 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:34:50,484 INFO L225 Difference]: With dead ends: 176 [2025-03-16 13:34:50,484 INFO L226 Difference]: Without dead ends: 167 [2025-03-16 13:34:50,485 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 197 GetRequests, 103 SyntacticMatches, 6 SemanticMatches, 88 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2538 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=968, Invalid=7042, Unknown=0, NotChecked=0, Total=8010 [2025-03-16 13:34:50,486 INFO L435 NwaCegarLoop]: 18 mSDtfsCounter, 367 mSDsluCounter, 251 mSDsCounter, 0 mSdLazyCounter, 1431 mSolverCounterSat, 153 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 367 SdHoareTripleChecker+Valid, 269 SdHoareTripleChecker+Invalid, 1584 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 153 IncrementalHoareTripleChecker+Valid, 1431 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2025-03-16 13:34:50,486 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [367 Valid, 269 Invalid, 1584 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [153 Valid, 1431 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2025-03-16 13:34:50,486 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 167 states. [2025-03-16 13:34:50,494 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 167 to 69. [2025-03-16 13:34:50,494 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 69 states, 68 states have (on average 1.1029411764705883) internal successors, (75), 68 states have internal predecessors, (75), 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 13:34:50,494 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 69 states to 69 states and 75 transitions. [2025-03-16 13:34:50,494 INFO L78 Accepts]: Start accepts. Automaton has 69 states and 75 transitions. Word has length 63 [2025-03-16 13:34:50,495 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:34:50,495 INFO L471 AbstractCegarLoop]: Abstraction has 69 states and 75 transitions. [2025-03-16 13:34:50,495 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 44 states, 44 states have (on average 3.727272727272727) internal successors, (164), 44 states have internal predecessors, (164), 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 13:34:50,495 INFO L276 IsEmpty]: Start isEmpty. Operand 69 states and 75 transitions. [2025-03-16 13:34:50,496 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 69 [2025-03-16 13:34:50,496 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:34:50,496 INFO L218 NwaCegarLoop]: trace histogram [7, 7, 6, 6, 5, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:34:50,507 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2025-03-16 13:34:50,696 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:34:50,697 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:34:50,697 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:34:50,697 INFO L85 PathProgramCache]: Analyzing trace with hash 1650232492, now seen corresponding path program 6 times [2025-03-16 13:34:50,697 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:34:50,697 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [524467985] [2025-03-16 13:34:50,697 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-03-16 13:34:50,697 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:34:50,708 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 68 statements into 7 equivalence classes. [2025-03-16 13:34:50,746 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) and asserted 68 of 68 statements. [2025-03-16 13:34:50,747 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2025-03-16 13:34:50,747 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:34:51,519 INFO L134 CoverageAnalysis]: Checked inductivity of 119 backedges. 12 proven. 102 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2025-03-16 13:34:51,519 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:34:51,519 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [524467985] [2025-03-16 13:34:51,520 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [524467985] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:34:51,520 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1724340588] [2025-03-16 13:34:51,520 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-03-16 13:34:51,520 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:34:51,520 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:34:51,522 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 13:34:51,523 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2025-03-16 13:34:51,587 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 68 statements into 7 equivalence classes. [2025-03-16 13:34:52,150 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) and asserted 68 of 68 statements. [2025-03-16 13:34:52,151 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2025-03-16 13:34:52,151 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:34:52,153 INFO L256 TraceCheckSpWp]: Trace formula consists of 301 conjuncts, 52 conjuncts are in the unsatisfiable core [2025-03-16 13:34:52,156 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:34:52,252 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-16 13:34:52,280 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:34:52,280 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 6 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 37 treesize of output 18 [2025-03-16 13:34:52,316 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 18 [2025-03-16 13:34:52,338 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:34:52,338 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 10 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 48 treesize of output 28 [2025-03-16 13:34:52,398 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:34:52,398 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 30 treesize of output 28 [2025-03-16 13:34:52,430 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:34:52,431 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 5 select indices, 5 select index equivalence classes, 10 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 10 case distinctions, treesize of input 55 treesize of output 45 [2025-03-16 13:34:52,466 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-16 13:34:52,468 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:34:52,468 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 6 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 41 treesize of output 42 [2025-03-16 13:34:52,508 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-16 13:34:52,510 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-16 13:34:52,519 INFO L349 Elim1Store]: treesize reduction 25, result has 21.9 percent of original size [2025-03-16 13:34:52,519 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 7 select indices, 7 select index equivalence classes, 20 disjoint index pairs (out of 21 index pairs), introduced 7 new quantified variables, introduced 22 case distinctions, treesize of input 90 treesize of output 78 [2025-03-16 13:34:53,236 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-16 13:34:53,238 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:34:53,238 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 6 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 44 treesize of output 16 [2025-03-16 13:34:53,244 INFO L134 CoverageAnalysis]: Checked inductivity of 119 backedges. 12 proven. 105 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2025-03-16 13:34:53,244 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:34:53,588 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 60 treesize of output 56 [2025-03-16 13:34:53,589 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 54 treesize of output 50 [2025-03-16 13:34:53,666 INFO L134 CoverageAnalysis]: Checked inductivity of 119 backedges. 12 proven. 92 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2025-03-16 13:34:53,666 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1724340588] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 13:34:53,666 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 13:34:53,666 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 21, 15] total 46 [2025-03-16 13:34:53,666 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1058562414] [2025-03-16 13:34:53,666 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 13:34:53,666 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 46 states [2025-03-16 13:34:53,667 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:34:53,667 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 46 interpolants. [2025-03-16 13:34:53,667 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=215, Invalid=1855, Unknown=0, NotChecked=0, Total=2070 [2025-03-16 13:34:53,668 INFO L87 Difference]: Start difference. First operand 69 states and 75 transitions. Second operand has 46 states, 46 states have (on average 3.9565217391304346) internal successors, (182), 46 states have internal predecessors, (182), 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 13:34:55,643 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:34:55,643 INFO L93 Difference]: Finished difference Result 133 states and 154 transitions. [2025-03-16 13:34:55,644 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 44 states. [2025-03-16 13:34:55,644 INFO L78 Accepts]: Start accepts. Automaton has has 46 states, 46 states have (on average 3.9565217391304346) internal successors, (182), 46 states have internal predecessors, (182), 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) Word has length 68 [2025-03-16 13:34:55,644 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:34:55,644 INFO L225 Difference]: With dead ends: 133 [2025-03-16 13:34:55,644 INFO L226 Difference]: Without dead ends: 124 [2025-03-16 13:34:55,646 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 199 GetRequests, 110 SyntacticMatches, 3 SemanticMatches, 86 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1843 ImplicationChecksByTransitivity, 2.0s TimeCoverageRelationStatistics Valid=1013, Invalid=6643, Unknown=0, NotChecked=0, Total=7656 [2025-03-16 13:34:55,646 INFO L435 NwaCegarLoop]: 19 mSDtfsCounter, 369 mSDsluCounter, 255 mSDsCounter, 0 mSdLazyCounter, 1824 mSolverCounterSat, 162 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 369 SdHoareTripleChecker+Valid, 274 SdHoareTripleChecker+Invalid, 1986 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 162 IncrementalHoareTripleChecker+Valid, 1824 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2025-03-16 13:34:55,646 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [369 Valid, 274 Invalid, 1986 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [162 Valid, 1824 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2025-03-16 13:34:55,646 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 124 states. [2025-03-16 13:34:55,659 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 124 to 74. [2025-03-16 13:34:55,659 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 74 states, 73 states have (on average 1.095890410958904) internal successors, (80), 73 states have internal predecessors, (80), 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 13:34:55,659 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 74 states to 74 states and 80 transitions. [2025-03-16 13:34:55,659 INFO L78 Accepts]: Start accepts. Automaton has 74 states and 80 transitions. Word has length 68 [2025-03-16 13:34:55,659 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:34:55,660 INFO L471 AbstractCegarLoop]: Abstraction has 74 states and 80 transitions. [2025-03-16 13:34:55,660 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 46 states, 46 states have (on average 3.9565217391304346) internal successors, (182), 46 states have internal predecessors, (182), 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 13:34:55,660 INFO L276 IsEmpty]: Start isEmpty. Operand 74 states and 80 transitions. [2025-03-16 13:34:55,661 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2025-03-16 13:34:55,661 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:34:55,661 INFO L218 NwaCegarLoop]: trace histogram [8, 8, 7, 7, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:34:55,668 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2025-03-16 13:34:55,861 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:34:55,861 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:34:55,862 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:34:55,862 INFO L85 PathProgramCache]: Analyzing trace with hash -1987362750, now seen corresponding path program 7 times [2025-03-16 13:34:55,862 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:34:55,862 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1402438666] [2025-03-16 13:34:55,862 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-03-16 13:34:55,862 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:34:55,873 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 73 statements into 1 equivalence classes. [2025-03-16 13:34:55,889 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 73 of 73 statements. [2025-03-16 13:34:55,889 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 13:34:55,889 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:34:56,346 INFO L134 CoverageAnalysis]: Checked inductivity of 153 backedges. 0 proven. 143 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2025-03-16 13:34:56,346 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:34:56,346 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1402438666] [2025-03-16 13:34:56,346 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1402438666] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:34:56,346 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [998531686] [2025-03-16 13:34:56,346 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-03-16 13:34:56,346 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:34:56,346 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:34:56,349 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 13:34:56,350 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2025-03-16 13:34:56,421 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 73 statements into 1 equivalence classes. [2025-03-16 13:34:56,452 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 73 of 73 statements. [2025-03-16 13:34:56,452 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 13:34:56,452 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:34:56,454 INFO L256 TraceCheckSpWp]: Trace formula consists of 313 conjuncts, 36 conjuncts are in the unsatisfiable core [2025-03-16 13:34:56,455 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:34:56,535 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-16 13:34:56,557 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:34:56,558 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 6 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 37 treesize of output 32 [2025-03-16 13:34:56,808 INFO L134 CoverageAnalysis]: Checked inductivity of 153 backedges. 0 proven. 142 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2025-03-16 13:34:56,808 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:34:56,891 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 15 [2025-03-16 13:34:56,892 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 12 [2025-03-16 13:34:56,897 INFO L134 CoverageAnalysis]: Checked inductivity of 153 backedges. 0 proven. 138 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2025-03-16 13:34:56,897 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [998531686] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 13:34:56,897 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 13:34:56,897 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16, 15] total 30 [2025-03-16 13:34:56,897 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [313546508] [2025-03-16 13:34:56,897 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 13:34:56,897 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 30 states [2025-03-16 13:34:56,897 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:34:56,898 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2025-03-16 13:34:56,898 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=107, Invalid=763, Unknown=0, NotChecked=0, Total=870 [2025-03-16 13:34:56,898 INFO L87 Difference]: Start difference. First operand 74 states and 80 transitions. Second operand has 30 states, 30 states have (on average 4.8) internal successors, (144), 30 states have internal predecessors, (144), 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 13:34:57,752 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:34:57,752 INFO L93 Difference]: Finished difference Result 131 states and 144 transitions. [2025-03-16 13:34:57,752 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 46 states. [2025-03-16 13:34:57,753 INFO L78 Accepts]: Start accepts. Automaton has has 30 states, 30 states have (on average 4.8) internal successors, (144), 30 states have internal predecessors, (144), 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) Word has length 73 [2025-03-16 13:34:57,753 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:34:57,753 INFO L225 Difference]: With dead ends: 131 [2025-03-16 13:34:57,753 INFO L226 Difference]: Without dead ends: 129 [2025-03-16 13:34:57,754 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 195 GetRequests, 133 SyntacticMatches, 2 SemanticMatches, 60 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 992 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=452, Invalid=3330, Unknown=0, NotChecked=0, Total=3782 [2025-03-16 13:34:57,754 INFO L435 NwaCegarLoop]: 18 mSDtfsCounter, 42 mSDsluCounter, 262 mSDsCounter, 0 mSdLazyCounter, 1724 mSolverCounterSat, 41 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 42 SdHoareTripleChecker+Valid, 280 SdHoareTripleChecker+Invalid, 1765 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 41 IncrementalHoareTripleChecker+Valid, 1724 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2025-03-16 13:34:57,754 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [42 Valid, 280 Invalid, 1765 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [41 Valid, 1724 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2025-03-16 13:34:57,755 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 129 states. [2025-03-16 13:34:57,762 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 129 to 79. [2025-03-16 13:34:57,762 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 79 states, 78 states have (on average 1.1025641025641026) internal successors, (86), 78 states have internal predecessors, (86), 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 13:34:57,763 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 79 states to 79 states and 86 transitions. [2025-03-16 13:34:57,763 INFO L78 Accepts]: Start accepts. Automaton has 79 states and 86 transitions. Word has length 73 [2025-03-16 13:34:57,763 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:34:57,763 INFO L471 AbstractCegarLoop]: Abstraction has 79 states and 86 transitions. [2025-03-16 13:34:57,763 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 30 states, 30 states have (on average 4.8) internal successors, (144), 30 states have internal predecessors, (144), 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 13:34:57,763 INFO L276 IsEmpty]: Start isEmpty. Operand 79 states and 86 transitions. [2025-03-16 13:34:57,763 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 79 [2025-03-16 13:34:57,763 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:34:57,763 INFO L218 NwaCegarLoop]: trace histogram [9, 9, 8, 8, 6, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:34:57,770 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 13:34:57,968 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,SelfDestructingSolverStorable11 [2025-03-16 13:34:57,968 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:34:57,968 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:34:57,968 INFO L85 PathProgramCache]: Analyzing trace with hash -1907954837, now seen corresponding path program 8 times [2025-03-16 13:34:57,968 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:34:57,968 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1322825122] [2025-03-16 13:34:57,968 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 13:34:57,968 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:34:57,979 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 78 statements into 2 equivalence classes. [2025-03-16 13:34:57,986 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 78 of 78 statements. [2025-03-16 13:34:57,986 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 13:34:57,986 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:34:58,292 INFO L134 CoverageAnalysis]: Checked inductivity of 192 backedges. 136 proven. 41 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2025-03-16 13:34:58,293 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:34:58,293 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1322825122] [2025-03-16 13:34:58,293 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1322825122] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:34:58,293 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [313846329] [2025-03-16 13:34:58,293 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 13:34:58,293 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:34:58,293 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:34:58,295 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 13:34:58,296 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2025-03-16 13:34:58,367 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 78 statements into 2 equivalence classes. [2025-03-16 13:34:58,398 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 78 of 78 statements. [2025-03-16 13:34:58,398 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 13:34:58,398 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:34:58,399 INFO L256 TraceCheckSpWp]: Trace formula consists of 328 conjuncts, 16 conjuncts are in the unsatisfiable core [2025-03-16 13:34:58,401 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:34:58,926 INFO L134 CoverageAnalysis]: Checked inductivity of 192 backedges. 172 proven. 5 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2025-03-16 13:34:58,926 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:34:59,146 INFO L134 CoverageAnalysis]: Checked inductivity of 192 backedges. 172 proven. 5 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2025-03-16 13:34:59,146 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [313846329] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 13:34:59,146 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 13:34:59,147 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 17, 16] total 45 [2025-03-16 13:34:59,147 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [317705253] [2025-03-16 13:34:59,147 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 13:34:59,147 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 45 states [2025-03-16 13:34:59,147 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:34:59,148 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 45 interpolants. [2025-03-16 13:34:59,148 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=495, Invalid=1485, Unknown=0, NotChecked=0, Total=1980 [2025-03-16 13:34:59,148 INFO L87 Difference]: Start difference. First operand 79 states and 86 transitions. Second operand has 45 states, 45 states have (on average 4.355555555555555) internal successors, (196), 45 states have internal predecessors, (196), 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 13:34:59,446 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:34:59,446 INFO L93 Difference]: Finished difference Result 224 states and 246 transitions. [2025-03-16 13:34:59,447 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2025-03-16 13:34:59,447 INFO L78 Accepts]: Start accepts. Automaton has has 45 states, 45 states have (on average 4.355555555555555) internal successors, (196), 45 states have internal predecessors, (196), 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) Word has length 78 [2025-03-16 13:34:59,447 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:34:59,447 INFO L225 Difference]: With dead ends: 224 [2025-03-16 13:34:59,447 INFO L226 Difference]: Without dead ends: 99 [2025-03-16 13:34:59,448 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 177 GetRequests, 128 SyntacticMatches, 0 SemanticMatches, 49 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 940 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=628, Invalid=1922, Unknown=0, NotChecked=0, Total=2550 [2025-03-16 13:34:59,448 INFO L435 NwaCegarLoop]: 30 mSDtfsCounter, 335 mSDsluCounter, 217 mSDsCounter, 0 mSdLazyCounter, 504 mSolverCounterSat, 104 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 335 SdHoareTripleChecker+Valid, 247 SdHoareTripleChecker+Invalid, 608 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 104 IncrementalHoareTripleChecker+Valid, 504 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-16 13:34:59,449 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [335 Valid, 247 Invalid, 608 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [104 Valid, 504 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-16 13:34:59,449 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 99 states. [2025-03-16 13:34:59,458 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 99 to 91. [2025-03-16 13:34:59,458 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 91 states, 90 states have (on average 1.0888888888888888) internal successors, (98), 90 states have internal predecessors, (98), 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 13:34:59,459 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 91 states to 91 states and 98 transitions. [2025-03-16 13:34:59,459 INFO L78 Accepts]: Start accepts. Automaton has 91 states and 98 transitions. Word has length 78 [2025-03-16 13:34:59,459 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:34:59,459 INFO L471 AbstractCegarLoop]: Abstraction has 91 states and 98 transitions. [2025-03-16 13:34:59,459 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 45 states, 45 states have (on average 4.355555555555555) internal successors, (196), 45 states have internal predecessors, (196), 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 13:34:59,459 INFO L276 IsEmpty]: Start isEmpty. Operand 91 states and 98 transitions. [2025-03-16 13:34:59,459 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 91 [2025-03-16 13:34:59,459 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:34:59,459 INFO L218 NwaCegarLoop]: trace histogram [9, 9, 8, 8, 6, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:34:59,466 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2025-03-16 13:34:59,660 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,SelfDestructingSolverStorable12 [2025-03-16 13:34:59,660 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:34:59,660 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:34:59,660 INFO L85 PathProgramCache]: Analyzing trace with hash -2098481332, now seen corresponding path program 9 times [2025-03-16 13:34:59,660 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:34:59,660 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [147568624] [2025-03-16 13:34:59,660 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 13:34:59,660 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:34:59,674 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 90 statements into 9 equivalence classes. [2025-03-16 13:34:59,723 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 9 check-sat command(s) and asserted 90 of 90 statements. [2025-03-16 13:34:59,724 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 9 check-sat command(s) [2025-03-16 13:34:59,724 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:35:02,840 INFO L134 CoverageAnalysis]: Checked inductivity of 220 backedges. 16 proven. 204 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-16 13:35:02,840 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:35:02,840 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [147568624] [2025-03-16 13:35:02,840 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [147568624] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:35:02,840 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2056102574] [2025-03-16 13:35:02,840 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 13:35:02,840 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:35:02,840 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:35:02,842 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 13:35:02,843 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2025-03-16 13:35:02,920 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 90 statements into 9 equivalence classes. [2025-03-16 13:35:04,061 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 9 check-sat command(s) and asserted 90 of 90 statements. [2025-03-16 13:35:04,061 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 9 check-sat command(s) [2025-03-16 13:35:04,061 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:35:04,067 INFO L256 TraceCheckSpWp]: Trace formula consists of 392 conjuncts, 95 conjuncts are in the unsatisfiable core [2025-03-16 13:35:04,071 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:35:04,202 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-03-16 13:35:04,236 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:35:04,237 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 6 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 37 treesize of output 18 [2025-03-16 13:35:04,302 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 18 [2025-03-16 13:35:04,345 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:35:04,345 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 10 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 44 treesize of output 28 [2025-03-16 13:35:04,392 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:35:04,392 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 26 treesize of output 28 [2025-03-16 13:35:04,440 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:35:04,440 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 15 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 51 treesize of output 38 [2025-03-16 13:35:04,493 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:35:04,493 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 6 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 34 treesize of output 35 [2025-03-16 13:35:04,537 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:35:04,537 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 6 select indices, 6 select index equivalence classes, 15 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 15 case distinctions, treesize of input 59 treesize of output 52 [2025-03-16 13:35:04,618 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:35:04,618 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 10 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 41 treesize of output 45 [2025-03-16 13:35:04,665 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:35:04,666 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 5 select indices, 5 select index equivalence classes, 21 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 10 case distinctions, treesize of input 66 treesize of output 48 [2025-03-16 13:35:04,727 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:35:04,727 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 5 select indices, 5 select index equivalence classes, 15 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 10 case distinctions, treesize of input 48 treesize of output 55 [2025-03-16 13:35:04,783 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:35:04,783 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 6 select indices, 6 select index equivalence classes, 28 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 15 case distinctions, treesize of input 73 treesize of output 58 [2025-03-16 13:35:04,865 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:35:04,865 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 6 select indices, 6 select index equivalence classes, 21 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 15 case distinctions, treesize of input 56 treesize of output 62 [2025-03-16 13:35:04,932 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:35:04,932 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 7 select indices, 7 select index equivalence classes, 28 disjoint index pairs (out of 21 index pairs), introduced 7 new quantified variables, introduced 21 case distinctions, treesize of input 92 treesize of output 65 [2025-03-16 13:35:05,044 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:35:05,044 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 7 select indices, 7 select index equivalence classes, 28 disjoint index pairs (out of 21 index pairs), introduced 7 new quantified variables, introduced 21 case distinctions, treesize of input 63 treesize of output 72 [2025-03-16 13:35:05,108 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:35:05,108 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 9 select indices, 9 select index equivalence classes, 36 disjoint index pairs (out of 36 index pairs), introduced 9 new quantified variables, introduced 36 case distinctions, treesize of input 88 treesize of output 82 [2025-03-16 13:35:05,178 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:35:05,179 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 8 select indices, 8 select index equivalence classes, 36 disjoint index pairs (out of 28 index pairs), introduced 8 new quantified variables, introduced 28 case distinctions, treesize of input 70 treesize of output 82 [2025-03-16 13:35:05,251 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:35:05,251 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 10 select indices, 10 select index equivalence classes, 45 disjoint index pairs (out of 45 index pairs), introduced 10 new quantified variables, introduced 45 case distinctions, treesize of input 95 treesize of output 92 [2025-03-16 13:35:05,332 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:35:05,332 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 9 select indices, 9 select index equivalence classes, 45 disjoint index pairs (out of 36 index pairs), introduced 9 new quantified variables, introduced 36 case distinctions, treesize of input 77 treesize of output 92 [2025-03-16 13:35:05,412 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:35:05,412 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 10 select indices, 10 select index equivalence classes, 45 disjoint index pairs (out of 45 index pairs), introduced 10 new quantified variables, introduced 45 case distinctions, treesize of input 102 treesize of output 95 [2025-03-16 13:35:06,545 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:35:06,545 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 10 select indices, 10 select index equivalence classes, 45 disjoint index pairs (out of 45 index pairs), introduced 10 new quantified variables, introduced 45 case distinctions, treesize of input 80 treesize of output 28 [2025-03-16 13:35:06,577 INFO L134 CoverageAnalysis]: Checked inductivity of 220 backedges. 16 proven. 204 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-16 13:35:06,577 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:35:23,899 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 17 [2025-03-16 13:35:23,901 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 20 [2025-03-16 13:35:24,065 INFO L134 CoverageAnalysis]: Checked inductivity of 220 backedges. 16 proven. 190 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2025-03-16 13:35:24,065 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2056102574] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 13:35:24,065 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 13:35:24,065 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [32, 38, 19] total 84 [2025-03-16 13:35:24,065 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [206870316] [2025-03-16 13:35:24,065 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 13:35:24,066 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 84 states [2025-03-16 13:35:24,066 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:35:24,067 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 84 interpolants. [2025-03-16 13:35:24,068 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=455, Invalid=6517, Unknown=0, NotChecked=0, Total=6972 [2025-03-16 13:35:24,068 INFO L87 Difference]: Start difference. First operand 91 states and 98 transitions. Second operand has 84 states, 84 states have (on average 3.0357142857142856) internal successors, (255), 84 states have internal predecessors, (255), 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 13:35:36,003 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 13:35:36,004 INFO L93 Difference]: Finished difference Result 200 states and 232 transitions. [2025-03-16 13:35:36,004 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 120 states. [2025-03-16 13:35:36,004 INFO L78 Accepts]: Start accepts. Automaton has has 84 states, 84 states have (on average 3.0357142857142856) internal successors, (255), 84 states have internal predecessors, (255), 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) Word has length 90 [2025-03-16 13:35:36,004 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 13:35:36,005 INFO L225 Difference]: With dead ends: 200 [2025-03-16 13:35:36,005 INFO L226 Difference]: Without dead ends: 191 [2025-03-16 13:35:36,007 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 340 GetRequests, 127 SyntacticMatches, 15 SemanticMatches, 198 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13184 ImplicationChecksByTransitivity, 27.4s TimeCoverageRelationStatistics Valid=3454, Invalid=36346, Unknown=0, NotChecked=0, Total=39800 [2025-03-16 13:35:36,007 INFO L435 NwaCegarLoop]: 22 mSDtfsCounter, 770 mSDsluCounter, 563 mSDsCounter, 0 mSdLazyCounter, 4503 mSolverCounterSat, 791 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 770 SdHoareTripleChecker+Valid, 585 SdHoareTripleChecker+Invalid, 5294 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 791 IncrementalHoareTripleChecker+Valid, 4503 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.6s IncrementalHoareTripleChecker+Time [2025-03-16 13:35:36,007 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [770 Valid, 585 Invalid, 5294 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [791 Valid, 4503 Invalid, 0 Unknown, 0 Unchecked, 3.6s Time] [2025-03-16 13:35:36,008 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 191 states. [2025-03-16 13:35:36,020 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 191 to 96. [2025-03-16 13:35:36,021 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 96 states, 95 states have (on average 1.0842105263157895) internal successors, (103), 95 states have internal predecessors, (103), 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 13:35:36,021 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 103 transitions. [2025-03-16 13:35:36,021 INFO L78 Accepts]: Start accepts. Automaton has 96 states and 103 transitions. Word has length 90 [2025-03-16 13:35:36,021 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 13:35:36,021 INFO L471 AbstractCegarLoop]: Abstraction has 96 states and 103 transitions. [2025-03-16 13:35:36,021 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 84 states, 84 states have (on average 3.0357142857142856) internal successors, (255), 84 states have internal predecessors, (255), 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 13:35:36,021 INFO L276 IsEmpty]: Start isEmpty. Operand 96 states and 103 transitions. [2025-03-16 13:35:36,022 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 96 [2025-03-16 13:35:36,022 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 13:35:36,022 INFO L218 NwaCegarLoop]: trace histogram [10, 10, 9, 9, 7, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 13:35:36,031 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2025-03-16 13:35:36,222 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,SelfDestructingSolverStorable13 [2025-03-16 13:35:36,222 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 13:35:36,222 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 13:35:36,222 INFO L85 PathProgramCache]: Analyzing trace with hash 653113762, now seen corresponding path program 10 times [2025-03-16 13:35:36,223 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 13:35:36,223 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [449970043] [2025-03-16 13:35:36,223 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-16 13:35:36,223 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 13:35:36,234 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 95 statements into 2 equivalence classes. [2025-03-16 13:35:36,265 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 95 of 95 statements. [2025-03-16 13:35:36,265 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-03-16 13:35:36,265 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:35:37,739 INFO L134 CoverageAnalysis]: Checked inductivity of 264 backedges. 21 proven. 219 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-03-16 13:35:37,739 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 13:35:37,739 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [449970043] [2025-03-16 13:35:37,739 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [449970043] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 13:35:37,739 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1070720740] [2025-03-16 13:35:37,739 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-16 13:35:37,740 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 13:35:37,740 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 13:35:37,741 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 13:35:37,742 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2025-03-16 13:35:37,821 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 95 statements into 2 equivalence classes. [2025-03-16 13:35:37,861 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 95 of 95 statements. [2025-03-16 13:35:37,861 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-03-16 13:35:37,861 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 13:35:37,864 INFO L256 TraceCheckSpWp]: Trace formula consists of 404 conjuncts, 79 conjuncts are in the unsatisfiable core [2025-03-16 13:35:37,867 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 13:35:38,012 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-03-16 13:35:38,040 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:35:38,040 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 6 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 37 treesize of output 18 [2025-03-16 13:35:38,090 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 18 [2025-03-16 13:35:38,131 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:35:38,131 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 10 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 44 treesize of output 28 [2025-03-16 13:35:38,172 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:35:38,173 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 26 treesize of output 28 [2025-03-16 13:35:38,213 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:35:38,213 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 15 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 51 treesize of output 38 [2025-03-16 13:35:38,258 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:35:38,259 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 6 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 34 treesize of output 35 [2025-03-16 13:35:38,302 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:35:38,303 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 15 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 59 treesize of output 38 [2025-03-16 13:35:38,381 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:35:38,381 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 10 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 41 treesize of output 45 [2025-03-16 13:35:38,432 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:35:38,432 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 7 select indices, 7 select index equivalence classes, 21 disjoint index pairs (out of 21 index pairs), introduced 7 new quantified variables, introduced 21 case distinctions, treesize of input 66 treesize of output 62 [2025-03-16 13:35:38,510 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:35:38,510 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 5 select indices, 5 select index equivalence classes, 15 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 10 case distinctions, treesize of input 48 treesize of output 55 [2025-03-16 13:35:38,560 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:35:38,560 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 8 select indices, 8 select index equivalence classes, 28 disjoint index pairs (out of 28 index pairs), introduced 8 new quantified variables, introduced 28 case distinctions, treesize of input 73 treesize of output 72 [2025-03-16 13:35:38,621 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:35:38,621 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 6 select indices, 6 select index equivalence classes, 21 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 15 case distinctions, treesize of input 55 treesize of output 65 [2025-03-16 13:35:38,678 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:35:38,678 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 8 select indices, 8 select index equivalence classes, 28 disjoint index pairs (out of 28 index pairs), introduced 8 new quantified variables, introduced 28 case distinctions, treesize of input 80 treesize of output 75 [2025-03-16 13:35:39,673 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-16 13:35:39,674 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 7 select indices, 7 select index equivalence classes, 21 disjoint index pairs (out of 21 index pairs), introduced 7 new quantified variables, introduced 21 case distinctions, treesize of input 58 treesize of output 22 [2025-03-16 13:35:39,678 INFO L134 CoverageAnalysis]: Checked inductivity of 264 backedges. 18 proven. 245 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2025-03-16 13:35:39,678 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 13:35:40,354 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 17 [2025-03-16 13:35:40,356 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 20 [2025-03-16 13:35:40,509 INFO L134 CoverageAnalysis]: Checked inductivity of 264 backedges. 18 proven. 210 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2025-03-16 13:35:40,509 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1070720740] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 13:35:40,510 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 13:35:40,510 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [26, 32, 18] total 70 [2025-03-16 13:35:40,510 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1006188574] [2025-03-16 13:35:40,510 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 13:35:40,510 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 70 states [2025-03-16 13:35:40,510 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 13:35:40,511 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 70 interpolants. [2025-03-16 13:35:40,511 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=295, Invalid=4535, Unknown=0, NotChecked=0, Total=4830 [2025-03-16 13:35:40,511 INFO L87 Difference]: Start difference. First operand 96 states and 103 transitions. Second operand has 70 states, 70 states have (on average 3.5) internal successors, (245), 70 states have internal predecessors, (245), 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)