./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound10.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/nla-digbench-scaling/egcd3-ll_valuebound10.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 776d32abf1ae3b62e7ad4a02cd7c02c0cc6433852a1fe73b7d30c6e216da832a --- Real Ultimate output --- This is Ultimate 0.3.0-?-8fc3dc6-m [2025-03-16 18:11:04,371 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-16 18:11:04,414 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2025-03-16 18:11:04,417 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-16 18:11:04,418 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-16 18:11:04,436 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-16 18:11:04,436 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-16 18:11:04,437 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-16 18:11:04,437 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-16 18:11:04,437 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-16 18:11:04,437 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-03-16 18:11:04,437 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-03-16 18:11:04,437 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-16 18:11:04,437 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-16 18:11:04,437 INFO L153 SettingsManager]: * Use SBE=true [2025-03-16 18:11:04,438 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-16 18:11:04,438 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-03-16 18:11:04,438 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-16 18:11:04,438 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-16 18:11:04,438 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-16 18:11:04,438 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-16 18:11:04,438 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-03-16 18:11:04,438 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-03-16 18:11:04,438 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-03-16 18:11:04,438 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-16 18:11:04,438 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-16 18:11:04,438 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-16 18:11:04,438 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-16 18:11:04,438 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-16 18:11:04,439 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-16 18:11:04,439 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-03-16 18:11:04,439 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-03-16 18:11:04,439 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-16 18:11:04,439 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-16 18:11:04,439 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-03-16 18:11:04,439 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-03-16 18:11:04,439 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-03-16 18:11:04,439 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-16 18:11:04,439 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-03-16 18:11:04,439 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-03-16 18:11:04,439 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-03-16 18:11:04,439 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-03-16 18:11:04,439 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-03-16 18:11:04,439 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 -> 776d32abf1ae3b62e7ad4a02cd7c02c0cc6433852a1fe73b7d30c6e216da832a [2025-03-16 18:11:04,678 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-16 18:11:04,686 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-16 18:11:04,688 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-16 18:11:04,689 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-16 18:11:04,689 INFO L274 PluginConnector]: CDTParser initialized [2025-03-16 18:11:04,690 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound10.c [2025-03-16 18:11:05,838 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/109a69a8b/37facef5caa04a18aeb27a5ccb742211/FLAGc31cd0955 [2025-03-16 18:11:06,048 INFO L384 CDTParser]: Found 1 translation units. [2025-03-16 18:11:06,050 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound10.c [2025-03-16 18:11:06,057 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/109a69a8b/37facef5caa04a18aeb27a5ccb742211/FLAGc31cd0955 [2025-03-16 18:11:06,070 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/109a69a8b/37facef5caa04a18aeb27a5ccb742211 [2025-03-16 18:11:06,072 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-16 18:11:06,074 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-16 18:11:06,075 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-16 18:11:06,075 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-16 18:11:06,078 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-16 18:11:06,079 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.03 06:11:06" (1/1) ... [2025-03-16 18:11:06,080 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@727f97fc and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:06, skipping insertion in model container [2025-03-16 18:11:06,081 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.03 06:11:06" (1/1) ... [2025-03-16 18:11:06,091 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-16 18:11:06,205 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/nla-digbench-scaling/egcd3-ll_valuebound10.c[490,503] [2025-03-16 18:11:06,227 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-16 18:11:06,236 INFO L200 MainTranslator]: Completed pre-run [2025-03-16 18:11:06,243 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/nla-digbench-scaling/egcd3-ll_valuebound10.c[490,503] [2025-03-16 18:11:06,250 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-16 18:11:06,263 INFO L204 MainTranslator]: Completed translation [2025-03-16 18:11:06,263 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:06 WrapperNode [2025-03-16 18:11:06,264 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-16 18:11:06,265 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-16 18:11:06,265 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-16 18:11:06,265 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-16 18:11:06,270 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:06" (1/1) ... [2025-03-16 18:11:06,273 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:06" (1/1) ... [2025-03-16 18:11:06,286 INFO L138 Inliner]: procedures = 14, calls = 16, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 74 [2025-03-16 18:11:06,286 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-16 18:11:06,287 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-16 18:11:06,288 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-16 18:11:06,288 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-16 18:11:06,294 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:06" (1/1) ... [2025-03-16 18:11:06,294 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:06" (1/1) ... [2025-03-16 18:11:06,295 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:06" (1/1) ... [2025-03-16 18:11:06,307 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2025-03-16 18:11:06,307 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:06" (1/1) ... [2025-03-16 18:11:06,307 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:06" (1/1) ... [2025-03-16 18:11:06,311 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:06" (1/1) ... [2025-03-16 18:11:06,313 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:06" (1/1) ... [2025-03-16 18:11:06,314 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:06" (1/1) ... [2025-03-16 18:11:06,315 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:06" (1/1) ... [2025-03-16 18:11:06,317 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-16 18:11:06,319 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-16 18:11:06,319 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-16 18:11:06,319 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-16 18:11:06,320 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:06" (1/1) ... [2025-03-16 18:11:06,324 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-16 18:11:06,332 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:06,341 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2025-03-16 18:11:06,343 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2025-03-16 18:11:06,357 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-16 18:11:06,357 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2025-03-16 18:11:06,357 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2025-03-16 18:11:06,357 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-03-16 18:11:06,357 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-16 18:11:06,358 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-16 18:11:06,358 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2025-03-16 18:11:06,358 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2025-03-16 18:11:06,394 INFO L256 CfgBuilder]: Building ICFG [2025-03-16 18:11:06,395 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-16 18:11:06,520 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2025-03-16 18:11:06,520 INFO L307 CfgBuilder]: Performing block encoding [2025-03-16 18:11:06,526 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-16 18:11:06,526 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-16 18:11:06,527 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 16.03 06:11:06 BoogieIcfgContainer [2025-03-16 18:11:06,527 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-16 18:11:06,528 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-03-16 18:11:06,529 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-03-16 18:11:06,532 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-03-16 18:11:06,532 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 16.03 06:11:06" (1/3) ... [2025-03-16 18:11:06,532 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7894b9c8 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.03 06:11:06, skipping insertion in model container [2025-03-16 18:11:06,533 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:06" (2/3) ... [2025-03-16 18:11:06,533 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7894b9c8 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.03 06:11:06, skipping insertion in model container [2025-03-16 18:11:06,533 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 16.03 06:11:06" (3/3) ... [2025-03-16 18:11:06,534 INFO L128 eAbstractionObserver]: Analyzing ICFG egcd3-ll_valuebound10.c [2025-03-16 18:11:06,544 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-03-16 18:11:06,545 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG egcd3-ll_valuebound10.c that has 3 procedures, 30 locations, 1 initial locations, 3 loop locations, and 1 error locations. [2025-03-16 18:11:06,583 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-03-16 18:11:06,593 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;@424a3758, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-03-16 18:11:06,593 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-03-16 18:11:06,596 INFO L276 IsEmpty]: Start isEmpty. Operand has 30 states, 18 states have (on average 1.4444444444444444) internal successors, (26), 18 states have internal predecessors, (26), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2025-03-16 18:11:06,600 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2025-03-16 18:11:06,601 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:06,601 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:11:06,602 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:06,605 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:06,606 INFO L85 PathProgramCache]: Analyzing trace with hash -1461292294, now seen corresponding path program 1 times [2025-03-16 18:11:06,612 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:06,612 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1609422871] [2025-03-16 18:11:06,613 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:06,614 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:06,670 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 28 statements into 1 equivalence classes. [2025-03-16 18:11:06,703 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 28 of 28 statements. [2025-03-16 18:11:06,704 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:06,705 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:06,914 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 9 proven. 0 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2025-03-16 18:11:06,915 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:06,916 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1609422871] [2025-03-16 18:11:06,917 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1609422871] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 18:11:06,917 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 18:11:06,917 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2025-03-16 18:11:06,918 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1425847194] [2025-03-16 18:11:06,919 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:11:06,921 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2025-03-16 18:11:06,921 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:06,933 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-03-16 18:11:06,933 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2025-03-16 18:11:06,934 INFO L87 Difference]: Start difference. First operand has 30 states, 18 states have (on average 1.4444444444444444) internal successors, (26), 18 states have internal predecessors, (26), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Second operand has 6 states, 6 states have (on average 2.1666666666666665) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 1 states have call successors, (4) [2025-03-16 18:11:07,045 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:07,046 INFO L93 Difference]: Finished difference Result 67 states and 117 transitions. [2025-03-16 18:11:07,047 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-16 18:11:07,048 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.1666666666666665) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 1 states have call successors, (4) Word has length 28 [2025-03-16 18:11:07,048 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:07,052 INFO L225 Difference]: With dead ends: 67 [2025-03-16 18:11:07,052 INFO L226 Difference]: Without dead ends: 36 [2025-03-16 18:11:07,055 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2025-03-16 18:11:07,059 INFO L435 NwaCegarLoop]: 29 mSDtfsCounter, 22 mSDsluCounter, 90 mSDsCounter, 0 mSdLazyCounter, 57 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 119 SdHoareTripleChecker+Invalid, 65 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 57 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:07,060 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [27 Valid, 119 Invalid, 65 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 57 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 18:11:07,072 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36 states. [2025-03-16 18:11:07,084 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36 to 28. [2025-03-16 18:11:07,085 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 28 states, 16 states have (on average 1.25) internal successors, (20), 17 states have internal predecessors, (20), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2025-03-16 18:11:07,090 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28 states to 28 states and 37 transitions. [2025-03-16 18:11:07,091 INFO L78 Accepts]: Start accepts. Automaton has 28 states and 37 transitions. Word has length 28 [2025-03-16 18:11:07,092 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:07,092 INFO L471 AbstractCegarLoop]: Abstraction has 28 states and 37 transitions. [2025-03-16 18:11:07,092 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.1666666666666665) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 1 states have call successors, (4) [2025-03-16 18:11:07,092 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 37 transitions. [2025-03-16 18:11:07,093 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2025-03-16 18:11:07,093 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:07,093 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:11:07,093 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2025-03-16 18:11:07,095 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:07,095 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:07,095 INFO L85 PathProgramCache]: Analyzing trace with hash 1979049318, now seen corresponding path program 1 times [2025-03-16 18:11:07,095 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:07,095 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [338409720] [2025-03-16 18:11:07,096 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:07,096 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:07,104 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 29 statements into 1 equivalence classes. [2025-03-16 18:11:07,112 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 29 of 29 statements. [2025-03-16 18:11:07,113 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:07,113 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:07,114 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1813941083] [2025-03-16 18:11:07,115 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:07,116 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:07,116 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:07,119 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:11:07,121 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2025-03-16 18:11:07,153 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 29 statements into 1 equivalence classes. [2025-03-16 18:11:07,167 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 29 of 29 statements. [2025-03-16 18:11:07,168 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:07,168 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:07,171 INFO L256 TraceCheckSpWp]: Trace formula consists of 92 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-03-16 18:11:07,174 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:07,269 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-03-16 18:11:07,269 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-16 18:11:07,269 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:07,269 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [338409720] [2025-03-16 18:11:07,270 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:07,270 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1813941083] [2025-03-16 18:11:07,270 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1813941083] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 18:11:07,270 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 18:11:07,270 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-16 18:11:07,270 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2115297059] [2025-03-16 18:11:07,270 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:11:07,271 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-16 18:11:07,271 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:07,271 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-16 18:11:07,271 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-16 18:11:07,271 INFO L87 Difference]: Start difference. First operand 28 states and 37 transitions. Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2025-03-16 18:11:07,332 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:07,332 INFO L93 Difference]: Finished difference Result 42 states and 56 transitions. [2025-03-16 18:11:07,333 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-16 18:11:07,333 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 29 [2025-03-16 18:11:07,333 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:07,334 INFO L225 Difference]: With dead ends: 42 [2025-03-16 18:11:07,334 INFO L226 Difference]: Without dead ends: 40 [2025-03-16 18:11:07,334 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 25 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2025-03-16 18:11:07,335 INFO L435 NwaCegarLoop]: 31 mSDtfsCounter, 7 mSDsluCounter, 87 mSDsCounter, 0 mSdLazyCounter, 25 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 118 SdHoareTripleChecker+Invalid, 25 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 25 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:07,335 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 118 Invalid, 25 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 25 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 18:11:07,335 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40 states. [2025-03-16 18:11:07,342 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40 to 39. [2025-03-16 18:11:07,343 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 39 states, 22 states have (on average 1.2727272727272727) internal successors, (28), 23 states have internal predecessors, (28), 13 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2025-03-16 18:11:07,343 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 53 transitions. [2025-03-16 18:11:07,344 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 53 transitions. Word has length 29 [2025-03-16 18:11:07,344 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:07,344 INFO L471 AbstractCegarLoop]: Abstraction has 39 states and 53 transitions. [2025-03-16 18:11:07,344 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2025-03-16 18:11:07,344 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 53 transitions. [2025-03-16 18:11:07,344 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2025-03-16 18:11:07,344 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:07,344 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:11:07,350 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2025-03-16 18:11:07,545 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:07,546 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:07,546 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:07,546 INFO L85 PathProgramCache]: Analyzing trace with hash 351925117, now seen corresponding path program 1 times [2025-03-16 18:11:07,546 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:07,546 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1091617357] [2025-03-16 18:11:07,546 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:07,547 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:07,553 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-03-16 18:11:07,565 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-03-16 18:11:07,565 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:07,566 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:07,695 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 6 proven. 4 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2025-03-16 18:11:07,696 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:07,696 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1091617357] [2025-03-16 18:11:07,696 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1091617357] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:11:07,696 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1066395098] [2025-03-16 18:11:07,696 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:07,696 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:07,697 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:07,698 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:11:07,700 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2025-03-16 18:11:07,727 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-03-16 18:11:07,741 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-03-16 18:11:07,742 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:07,742 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:07,742 INFO L256 TraceCheckSpWp]: Trace formula consists of 102 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-03-16 18:11:07,745 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:07,778 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 6 proven. 4 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2025-03-16 18:11:07,779 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:07,856 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 6 proven. 4 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2025-03-16 18:11:07,856 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1066395098] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:11:07,856 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 18:11:07,857 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 9 [2025-03-16 18:11:07,857 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1395500079] [2025-03-16 18:11:07,857 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:07,857 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2025-03-16 18:11:07,857 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:07,857 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2025-03-16 18:11:07,858 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2025-03-16 18:11:07,858 INFO L87 Difference]: Start difference. First operand 39 states and 53 transitions. Second operand has 9 states, 9 states have (on average 2.0) internal successors, (18), 8 states have internal predecessors, (18), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2025-03-16 18:11:07,997 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:07,997 INFO L93 Difference]: Finished difference Result 81 states and 121 transitions. [2025-03-16 18:11:07,997 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-03-16 18:11:07,997 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.0) internal successors, (18), 8 states have internal predecessors, (18), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 31 [2025-03-16 18:11:07,998 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:07,998 INFO L225 Difference]: With dead ends: 81 [2025-03-16 18:11:07,998 INFO L226 Difference]: Without dead ends: 74 [2025-03-16 18:11:07,999 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 72 GetRequests, 57 SyntacticMatches, 4 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=42, Invalid=114, Unknown=0, NotChecked=0, Total=156 [2025-03-16 18:11:07,999 INFO L435 NwaCegarLoop]: 33 mSDtfsCounter, 44 mSDsluCounter, 136 mSDsCounter, 0 mSdLazyCounter, 88 mSolverCounterSat, 28 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 48 SdHoareTripleChecker+Valid, 169 SdHoareTripleChecker+Invalid, 116 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 28 IncrementalHoareTripleChecker+Valid, 88 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:07,999 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [48 Valid, 169 Invalid, 116 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [28 Valid, 88 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 18:11:08,000 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 74 states. [2025-03-16 18:11:08,009 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 74 to 53. [2025-03-16 18:11:08,009 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 53 states, 32 states have (on average 1.375) internal successors, (44), 33 states have internal predecessors, (44), 17 states have call successors, (17), 3 states have call predecessors, (17), 3 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2025-03-16 18:11:08,010 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 77 transitions. [2025-03-16 18:11:08,010 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 77 transitions. Word has length 31 [2025-03-16 18:11:08,011 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:08,011 INFO L471 AbstractCegarLoop]: Abstraction has 53 states and 77 transitions. [2025-03-16 18:11:08,011 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.0) internal successors, (18), 8 states have internal predecessors, (18), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2025-03-16 18:11:08,011 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 77 transitions. [2025-03-16 18:11:08,011 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2025-03-16 18:11:08,011 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:08,011 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:11:08,017 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2025-03-16 18:11:08,212 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2025-03-16 18:11:08,212 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:08,212 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:08,212 INFO L85 PathProgramCache]: Analyzing trace with hash -1940753085, now seen corresponding path program 1 times [2025-03-16 18:11:08,212 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:08,212 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [102718848] [2025-03-16 18:11:08,213 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:08,213 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:08,217 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 32 statements into 1 equivalence classes. [2025-03-16 18:11:08,225 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 32 of 32 statements. [2025-03-16 18:11:08,225 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:08,225 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:08,226 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1624121357] [2025-03-16 18:11:08,226 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:08,226 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:08,226 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:08,228 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:11:08,229 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2025-03-16 18:11:08,252 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 32 statements into 1 equivalence classes. [2025-03-16 18:11:08,264 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 32 of 32 statements. [2025-03-16 18:11:08,264 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:08,264 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:08,265 INFO L256 TraceCheckSpWp]: Trace formula consists of 110 conjuncts, 15 conjuncts are in the unsatisfiable core [2025-03-16 18:11:08,266 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:08,332 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-03-16 18:11:08,332 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:08,443 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-03-16 18:11:08,443 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:08,444 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [102718848] [2025-03-16 18:11:08,444 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:08,444 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1624121357] [2025-03-16 18:11:08,444 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1624121357] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:11:08,444 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:11:08,444 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 8 [2025-03-16 18:11:08,444 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [412393823] [2025-03-16 18:11:08,444 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:08,444 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2025-03-16 18:11:08,445 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:08,445 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-03-16 18:11:08,445 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2025-03-16 18:11:08,445 INFO L87 Difference]: Start difference. First operand 53 states and 77 transitions. Second operand has 8 states, 8 states have (on average 2.5) internal successors, (20), 7 states have internal predecessors, (20), 3 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2025-03-16 18:11:08,538 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:08,539 INFO L93 Difference]: Finished difference Result 82 states and 119 transitions. [2025-03-16 18:11:08,539 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-16 18:11:08,539 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 2.5) internal successors, (20), 7 states have internal predecessors, (20), 3 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 32 [2025-03-16 18:11:08,539 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:08,540 INFO L225 Difference]: With dead ends: 82 [2025-03-16 18:11:08,540 INFO L226 Difference]: Without dead ends: 80 [2025-03-16 18:11:08,540 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 63 GetRequests, 54 SyntacticMatches, 2 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2025-03-16 18:11:08,541 INFO L435 NwaCegarLoop]: 50 mSDtfsCounter, 17 mSDsluCounter, 190 mSDsCounter, 0 mSdLazyCounter, 82 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 240 SdHoareTripleChecker+Invalid, 87 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 82 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:08,541 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [25 Valid, 240 Invalid, 87 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 82 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 18:11:08,541 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 80 states. [2025-03-16 18:11:08,555 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 80 to 76. [2025-03-16 18:11:08,556 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 76 states, 46 states have (on average 1.391304347826087) internal successors, (64), 47 states have internal predecessors, (64), 25 states have call successors, (25), 4 states have call predecessors, (25), 4 states have return successors, (24), 24 states have call predecessors, (24), 24 states have call successors, (24) [2025-03-16 18:11:08,558 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 76 states to 76 states and 113 transitions. [2025-03-16 18:11:08,559 INFO L78 Accepts]: Start accepts. Automaton has 76 states and 113 transitions. Word has length 32 [2025-03-16 18:11:08,559 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:08,559 INFO L471 AbstractCegarLoop]: Abstraction has 76 states and 113 transitions. [2025-03-16 18:11:08,559 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 2.5) internal successors, (20), 7 states have internal predecessors, (20), 3 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2025-03-16 18:11:08,559 INFO L276 IsEmpty]: Start isEmpty. Operand 76 states and 113 transitions. [2025-03-16 18:11:08,560 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2025-03-16 18:11:08,560 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:08,560 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:11:08,568 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2025-03-16 18:11:08,765 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:08,766 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:08,766 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:08,766 INFO L85 PathProgramCache]: Analyzing trace with hash -908329914, now seen corresponding path program 2 times [2025-03-16 18:11:08,766 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:08,766 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1399992853] [2025-03-16 18:11:08,766 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:11:08,766 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:08,771 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 35 statements into 2 equivalence classes. [2025-03-16 18:11:08,781 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 35 of 35 statements. [2025-03-16 18:11:08,781 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:11:08,781 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:08,862 INFO L134 CoverageAnalysis]: Checked inductivity of 31 backedges. 7 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-03-16 18:11:08,864 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:08,865 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1399992853] [2025-03-16 18:11:08,865 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1399992853] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 18:11:08,865 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 18:11:08,865 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-16 18:11:08,865 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1762422803] [2025-03-16 18:11:08,865 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:11:08,865 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-16 18:11:08,865 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:08,866 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-16 18:11:08,866 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-16 18:11:08,866 INFO L87 Difference]: Start difference. First operand 76 states and 113 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2025-03-16 18:11:08,946 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:08,947 INFO L93 Difference]: Finished difference Result 115 states and 177 transitions. [2025-03-16 18:11:08,947 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-16 18:11:08,948 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 35 [2025-03-16 18:11:08,949 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:08,949 INFO L225 Difference]: With dead ends: 115 [2025-03-16 18:11:08,949 INFO L226 Difference]: Without dead ends: 86 [2025-03-16 18:11:08,950 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2025-03-16 18:11:08,950 INFO L435 NwaCegarLoop]: 34 mSDtfsCounter, 13 mSDsluCounter, 84 mSDsCounter, 0 mSdLazyCounter, 50 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 118 SdHoareTripleChecker+Invalid, 58 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 50 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:08,950 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 118 Invalid, 58 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 50 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 18:11:08,951 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 86 states. [2025-03-16 18:11:08,965 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 86 to 57. [2025-03-16 18:11:08,965 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 57 states, 35 states have (on average 1.2857142857142858) internal successors, (45), 36 states have internal predecessors, (45), 17 states have call successors, (17), 4 states have call predecessors, (17), 4 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2025-03-16 18:11:08,966 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 78 transitions. [2025-03-16 18:11:08,966 INFO L78 Accepts]: Start accepts. Automaton has 57 states and 78 transitions. Word has length 35 [2025-03-16 18:11:08,966 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:08,966 INFO L471 AbstractCegarLoop]: Abstraction has 57 states and 78 transitions. [2025-03-16 18:11:08,966 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2025-03-16 18:11:08,966 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 78 transitions. [2025-03-16 18:11:08,967 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2025-03-16 18:11:08,967 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:08,967 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:11:08,967 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4 [2025-03-16 18:11:08,967 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:08,967 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:08,968 INFO L85 PathProgramCache]: Analyzing trace with hash -1361869309, now seen corresponding path program 1 times [2025-03-16 18:11:08,968 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:08,968 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1743420267] [2025-03-16 18:11:08,968 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:08,968 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:08,974 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 37 statements into 1 equivalence classes. [2025-03-16 18:11:08,988 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 37 of 37 statements. [2025-03-16 18:11:08,988 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:08,988 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:08,992 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [451840267] [2025-03-16 18:11:08,992 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:08,992 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:08,992 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:08,994 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:11:08,996 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2025-03-16 18:11:09,020 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 37 statements into 1 equivalence classes. [2025-03-16 18:11:09,033 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 37 of 37 statements. [2025-03-16 18:11:09,033 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:09,033 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:09,034 INFO L256 TraceCheckSpWp]: Trace formula consists of 119 conjuncts, 21 conjuncts are in the unsatisfiable core [2025-03-16 18:11:09,035 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:09,145 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-03-16 18:11:09,146 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:09,185 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:09,185 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1743420267] [2025-03-16 18:11:09,185 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:09,185 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [451840267] [2025-03-16 18:11:09,185 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [451840267] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:11:09,185 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-16 18:11:09,185 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2025-03-16 18:11:09,185 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [106842912] [2025-03-16 18:11:09,185 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:09,185 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2025-03-16 18:11:09,186 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:09,186 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2025-03-16 18:11:09,186 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2025-03-16 18:11:09,186 INFO L87 Difference]: Start difference. First operand 57 states and 78 transitions. Second operand has 7 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 6 states have internal predecessors, (17), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2025-03-16 18:11:09,313 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:09,313 INFO L93 Difference]: Finished difference Result 78 states and 109 transitions. [2025-03-16 18:11:09,314 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2025-03-16 18:11:09,314 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 6 states have internal predecessors, (17), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 37 [2025-03-16 18:11:09,314 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:09,315 INFO L225 Difference]: With dead ends: 78 [2025-03-16 18:11:09,315 INFO L226 Difference]: Without dead ends: 76 [2025-03-16 18:11:09,315 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 43 GetRequests, 33 SyntacticMatches, 2 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=22, Invalid=68, Unknown=0, NotChecked=0, Total=90 [2025-03-16 18:11:09,316 INFO L435 NwaCegarLoop]: 35 mSDtfsCounter, 21 mSDsluCounter, 138 mSDsCounter, 0 mSdLazyCounter, 109 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 28 SdHoareTripleChecker+Valid, 173 SdHoareTripleChecker+Invalid, 120 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 109 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:09,316 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [28 Valid, 173 Invalid, 120 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 109 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 18:11:09,317 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 76 states. [2025-03-16 18:11:09,333 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 76 to 74. [2025-03-16 18:11:09,335 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 74 states, 43 states have (on average 1.302325581395349) internal successors, (56), 44 states have internal predecessors, (56), 25 states have call successors, (25), 5 states have call predecessors, (25), 5 states have return successors, (24), 24 states have call predecessors, (24), 24 states have call successors, (24) [2025-03-16 18:11:09,335 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 74 states to 74 states and 105 transitions. [2025-03-16 18:11:09,336 INFO L78 Accepts]: Start accepts. Automaton has 74 states and 105 transitions. Word has length 37 [2025-03-16 18:11:09,336 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:09,336 INFO L471 AbstractCegarLoop]: Abstraction has 74 states and 105 transitions. [2025-03-16 18:11:09,336 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 6 states have internal predecessors, (17), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2025-03-16 18:11:09,336 INFO L276 IsEmpty]: Start isEmpty. Operand 74 states and 105 transitions. [2025-03-16 18:11:09,337 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2025-03-16 18:11:09,337 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:09,337 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 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] [2025-03-16 18:11:09,343 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2025-03-16 18:11:09,541 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:09,541 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:09,541 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:09,541 INFO L85 PathProgramCache]: Analyzing trace with hash -1979591293, now seen corresponding path program 1 times [2025-03-16 18:11:09,541 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:09,541 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [859357188] [2025-03-16 18:11:09,542 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:09,542 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:09,545 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 42 statements into 1 equivalence classes. [2025-03-16 18:11:09,551 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 42 of 42 statements. [2025-03-16 18:11:09,551 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:09,551 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:09,552 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [581446092] [2025-03-16 18:11:09,552 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:09,552 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:09,552 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:09,554 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:11:09,556 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2025-03-16 18:11:09,577 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 42 statements into 1 equivalence classes. [2025-03-16 18:11:09,590 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 42 of 42 statements. [2025-03-16 18:11:09,590 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:09,590 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:09,591 INFO L256 TraceCheckSpWp]: Trace formula consists of 128 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-16 18:11:09,594 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:09,628 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 5 proven. 0 refuted. 0 times theorem prover too weak. 29 trivial. 0 not checked. [2025-03-16 18:11:09,628 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-16 18:11:09,628 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:09,628 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [859357188] [2025-03-16 18:11:09,628 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:09,628 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [581446092] [2025-03-16 18:11:09,629 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [581446092] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 18:11:09,629 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 18:11:09,629 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-16 18:11:09,629 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1320838464] [2025-03-16 18:11:09,629 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:11:09,629 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-16 18:11:09,629 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:09,629 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-16 18:11:09,629 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-16 18:11:09,630 INFO L87 Difference]: Start difference. First operand 74 states and 105 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2025-03-16 18:11:09,684 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:09,684 INFO L93 Difference]: Finished difference Result 103 states and 147 transitions. [2025-03-16 18:11:09,684 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-16 18:11:09,684 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 42 [2025-03-16 18:11:09,684 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:09,685 INFO L225 Difference]: With dead ends: 103 [2025-03-16 18:11:09,685 INFO L226 Difference]: Without dead ends: 101 [2025-03-16 18:11:09,685 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 42 GetRequests, 38 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2025-03-16 18:11:09,686 INFO L435 NwaCegarLoop]: 30 mSDtfsCounter, 6 mSDsluCounter, 78 mSDsCounter, 0 mSdLazyCounter, 43 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 108 SdHoareTripleChecker+Invalid, 43 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 43 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:09,686 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 108 Invalid, 43 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 43 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 18:11:09,686 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 101 states. [2025-03-16 18:11:09,709 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 101 to 97. [2025-03-16 18:11:09,711 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 97 states, 52 states have (on average 1.3076923076923077) internal successors, (68), 53 states have internal predecessors, (68), 37 states have call successors, (37), 7 states have call predecessors, (37), 7 states have return successors, (36), 36 states have call predecessors, (36), 36 states have call successors, (36) [2025-03-16 18:11:09,712 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 97 states to 97 states and 141 transitions. [2025-03-16 18:11:09,712 INFO L78 Accepts]: Start accepts. Automaton has 97 states and 141 transitions. Word has length 42 [2025-03-16 18:11:09,713 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:09,713 INFO L471 AbstractCegarLoop]: Abstraction has 97 states and 141 transitions. [2025-03-16 18:11:09,713 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2025-03-16 18:11:09,713 INFO L276 IsEmpty]: Start isEmpty. Operand 97 states and 141 transitions. [2025-03-16 18:11:09,714 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2025-03-16 18:11:09,714 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:09,714 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:11:09,722 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 18:11:09,915 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:09,915 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:09,915 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:09,916 INFO L85 PathProgramCache]: Analyzing trace with hash 146539456, now seen corresponding path program 1 times [2025-03-16 18:11:09,916 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:09,916 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [984248377] [2025-03-16 18:11:09,916 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:09,916 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:09,920 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 44 statements into 1 equivalence classes. [2025-03-16 18:11:09,929 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 44 of 44 statements. [2025-03-16 18:11:09,930 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:09,930 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:09,930 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [799649047] [2025-03-16 18:11:09,932 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:09,932 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:09,932 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:09,934 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:11:09,935 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2025-03-16 18:11:09,958 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 44 statements into 1 equivalence classes. [2025-03-16 18:11:09,970 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 44 of 44 statements. [2025-03-16 18:11:09,970 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:09,971 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:09,971 INFO L256 TraceCheckSpWp]: Trace formula consists of 119 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-16 18:11:09,972 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:10,005 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2025-03-16 18:11:10,006 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-16 18:11:10,007 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:10,007 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [984248377] [2025-03-16 18:11:10,007 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:10,007 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [799649047] [2025-03-16 18:11:10,007 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [799649047] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 18:11:10,007 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 18:11:10,007 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-16 18:11:10,007 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1487575418] [2025-03-16 18:11:10,007 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:11:10,007 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-16 18:11:10,007 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:10,008 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-16 18:11:10,008 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-16 18:11:10,008 INFO L87 Difference]: Start difference. First operand 97 states and 141 transitions. Second operand has 5 states, 4 states have (on average 3.5) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2025-03-16 18:11:10,072 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:10,072 INFO L93 Difference]: Finished difference Result 147 states and 230 transitions. [2025-03-16 18:11:10,073 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-16 18:11:10,073 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 3.5) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 44 [2025-03-16 18:11:10,074 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:10,077 INFO L225 Difference]: With dead ends: 147 [2025-03-16 18:11:10,077 INFO L226 Difference]: Without dead ends: 145 [2025-03-16 18:11:10,077 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 44 GetRequests, 40 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2025-03-16 18:11:10,078 INFO L435 NwaCegarLoop]: 33 mSDtfsCounter, 4 mSDsluCounter, 83 mSDsCounter, 0 mSdLazyCounter, 35 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 116 SdHoareTripleChecker+Invalid, 35 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 35 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:10,078 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 116 Invalid, 35 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 35 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 18:11:10,079 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 145 states. [2025-03-16 18:11:10,120 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 145 to 133. [2025-03-16 18:11:10,121 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 133 states, 55 states have (on average 1.290909090909091) internal successors, (71), 64 states have internal predecessors, (71), 69 states have call successors, (69), 8 states have call predecessors, (69), 8 states have return successors, (68), 60 states have call predecessors, (68), 68 states have call successors, (68) [2025-03-16 18:11:10,123 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 133 states to 133 states and 208 transitions. [2025-03-16 18:11:10,123 INFO L78 Accepts]: Start accepts. Automaton has 133 states and 208 transitions. Word has length 44 [2025-03-16 18:11:10,123 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:10,123 INFO L471 AbstractCegarLoop]: Abstraction has 133 states and 208 transitions. [2025-03-16 18:11:10,123 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 3.5) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2025-03-16 18:11:10,123 INFO L276 IsEmpty]: Start isEmpty. Operand 133 states and 208 transitions. [2025-03-16 18:11:10,124 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2025-03-16 18:11:10,124 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:10,124 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 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, 1, 1] [2025-03-16 18:11:10,133 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2025-03-16 18:11:10,331 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:10,331 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:10,332 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:10,332 INFO L85 PathProgramCache]: Analyzing trace with hash 89640629, now seen corresponding path program 1 times [2025-03-16 18:11:10,332 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:10,332 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [749356991] [2025-03-16 18:11:10,332 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:10,332 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:10,338 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 54 statements into 1 equivalence classes. [2025-03-16 18:11:10,356 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 54 of 54 statements. [2025-03-16 18:11:10,357 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:10,357 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:10,359 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [809852634] [2025-03-16 18:11:10,359 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:10,359 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:10,359 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:10,361 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:11:10,363 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2025-03-16 18:11:10,386 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 54 statements into 1 equivalence classes. [2025-03-16 18:11:10,402 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 54 of 54 statements. [2025-03-16 18:11:10,402 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:10,403 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:10,404 INFO L256 TraceCheckSpWp]: Trace formula consists of 148 conjuncts, 51 conjuncts are in the unsatisfiable core [2025-03-16 18:11:10,406 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:10,948 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 14 proven. 5 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2025-03-16 18:11:10,949 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:11,300 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2025-03-16 18:11:11,301 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:11,301 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [749356991] [2025-03-16 18:11:11,301 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:11,301 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [809852634] [2025-03-16 18:11:11,301 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [809852634] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:11:11,301 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:11:11,301 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 11] total 23 [2025-03-16 18:11:11,301 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1036900420] [2025-03-16 18:11:11,301 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:11,302 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2025-03-16 18:11:11,302 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:11,302 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2025-03-16 18:11:11,302 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=77, Invalid=429, Unknown=0, NotChecked=0, Total=506 [2025-03-16 18:11:11,303 INFO L87 Difference]: Start difference. First operand 133 states and 208 transitions. Second operand has 23 states, 21 states have (on average 1.5238095238095237) internal successors, (32), 20 states have internal predecessors, (32), 6 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2025-03-16 18:11:13,182 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:13,182 INFO L93 Difference]: Finished difference Result 357 states and 579 transitions. [2025-03-16 18:11:13,183 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 32 states. [2025-03-16 18:11:13,183 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 21 states have (on average 1.5238095238095237) internal successors, (32), 20 states have internal predecessors, (32), 6 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) Word has length 54 [2025-03-16 18:11:13,183 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:13,187 INFO L225 Difference]: With dead ends: 357 [2025-03-16 18:11:13,187 INFO L226 Difference]: Without dead ends: 275 [2025-03-16 18:11:13,191 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 129 GetRequests, 85 SyntacticMatches, 0 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 434 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=398, Invalid=1672, Unknown=0, NotChecked=0, Total=2070 [2025-03-16 18:11:13,191 INFO L435 NwaCegarLoop]: 22 mSDtfsCounter, 126 mSDsluCounter, 233 mSDsCounter, 0 mSdLazyCounter, 640 mSolverCounterSat, 126 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 134 SdHoareTripleChecker+Valid, 255 SdHoareTripleChecker+Invalid, 766 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 126 IncrementalHoareTripleChecker+Valid, 640 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:13,192 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [134 Valid, 255 Invalid, 766 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [126 Valid, 640 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2025-03-16 18:11:13,194 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 275 states. [2025-03-16 18:11:13,269 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 275 to 203. [2025-03-16 18:11:13,270 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 203 states, 98 states have (on average 1.316326530612245) internal successors, (129), 105 states have internal predecessors, (129), 93 states have call successors, (93), 11 states have call predecessors, (93), 11 states have return successors, (92), 86 states have call predecessors, (92), 92 states have call successors, (92) [2025-03-16 18:11:13,271 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 203 states to 203 states and 314 transitions. [2025-03-16 18:11:13,272 INFO L78 Accepts]: Start accepts. Automaton has 203 states and 314 transitions. Word has length 54 [2025-03-16 18:11:13,272 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:13,272 INFO L471 AbstractCegarLoop]: Abstraction has 203 states and 314 transitions. [2025-03-16 18:11:13,272 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 21 states have (on average 1.5238095238095237) internal successors, (32), 20 states have internal predecessors, (32), 6 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2025-03-16 18:11:13,272 INFO L276 IsEmpty]: Start isEmpty. Operand 203 states and 314 transitions. [2025-03-16 18:11:13,273 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2025-03-16 18:11:13,273 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:13,273 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 3, 2, 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] [2025-03-16 18:11:13,280 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 18:11:13,473 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:13,473 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:13,474 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:13,474 INFO L85 PathProgramCache]: Analyzing trace with hash 107169448, now seen corresponding path program 1 times [2025-03-16 18:11:13,474 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:13,474 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [776853427] [2025-03-16 18:11:13,474 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:13,474 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:13,479 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 58 statements into 1 equivalence classes. [2025-03-16 18:11:13,494 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 58 of 58 statements. [2025-03-16 18:11:13,495 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:13,495 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:13,495 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [680167402] [2025-03-16 18:11:13,495 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:13,495 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:13,496 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:13,497 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:11:13,499 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2025-03-16 18:11:13,522 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 58 statements into 1 equivalence classes. [2025-03-16 18:11:13,540 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 58 of 58 statements. [2025-03-16 18:11:13,540 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:13,540 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:13,548 INFO L256 TraceCheckSpWp]: Trace formula consists of 174 conjuncts, 49 conjuncts are in the unsatisfiable core [2025-03-16 18:11:13,550 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:13,872 INFO L134 CoverageAnalysis]: Checked inductivity of 67 backedges. 16 proven. 21 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2025-03-16 18:11:13,872 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:13,978 INFO L134 CoverageAnalysis]: Checked inductivity of 67 backedges. 18 proven. 8 refuted. 0 times theorem prover too weak. 41 trivial. 0 not checked. [2025-03-16 18:11:13,978 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:13,978 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [776853427] [2025-03-16 18:11:13,978 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:13,978 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [680167402] [2025-03-16 18:11:13,979 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [680167402] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:11:13,979 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:11:13,979 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 8] total 22 [2025-03-16 18:11:13,979 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [361082855] [2025-03-16 18:11:13,979 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:13,979 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2025-03-16 18:11:13,979 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:13,980 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2025-03-16 18:11:13,980 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=67, Invalid=395, Unknown=0, NotChecked=0, Total=462 [2025-03-16 18:11:13,980 INFO L87 Difference]: Start difference. First operand 203 states and 314 transitions. Second operand has 22 states, 22 states have (on average 2.0) internal successors, (44), 19 states have internal predecessors, (44), 6 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2025-03-16 18:11:15,075 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:15,076 INFO L93 Difference]: Finished difference Result 254 states and 393 transitions. [2025-03-16 18:11:15,076 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2025-03-16 18:11:15,076 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 22 states have (on average 2.0) internal successors, (44), 19 states have internal predecessors, (44), 6 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) Word has length 58 [2025-03-16 18:11:15,076 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:15,079 INFO L225 Difference]: With dead ends: 254 [2025-03-16 18:11:15,079 INFO L226 Difference]: Without dead ends: 252 [2025-03-16 18:11:15,080 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 135 GetRequests, 103 SyntacticMatches, 0 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 194 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=190, Invalid=932, Unknown=0, NotChecked=0, Total=1122 [2025-03-16 18:11:15,080 INFO L435 NwaCegarLoop]: 38 mSDtfsCounter, 95 mSDsluCounter, 287 mSDsCounter, 0 mSdLazyCounter, 563 mSolverCounterSat, 103 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 97 SdHoareTripleChecker+Valid, 325 SdHoareTripleChecker+Invalid, 666 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 103 IncrementalHoareTripleChecker+Valid, 563 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:15,080 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [97 Valid, 325 Invalid, 666 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [103 Valid, 563 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2025-03-16 18:11:15,081 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 252 states. [2025-03-16 18:11:15,139 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 252 to 211. [2025-03-16 18:11:15,140 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 211 states, 104 states have (on average 1.2980769230769231) internal successors, (135), 111 states have internal predecessors, (135), 93 states have call successors, (93), 13 states have call predecessors, (93), 13 states have return successors, (92), 86 states have call predecessors, (92), 92 states have call successors, (92) [2025-03-16 18:11:15,142 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 211 states to 211 states and 320 transitions. [2025-03-16 18:11:15,142 INFO L78 Accepts]: Start accepts. Automaton has 211 states and 320 transitions. Word has length 58 [2025-03-16 18:11:15,142 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:15,142 INFO L471 AbstractCegarLoop]: Abstraction has 211 states and 320 transitions. [2025-03-16 18:11:15,142 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 22 states have (on average 2.0) internal successors, (44), 19 states have internal predecessors, (44), 6 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2025-03-16 18:11:15,142 INFO L276 IsEmpty]: Start isEmpty. Operand 211 states and 320 transitions. [2025-03-16 18:11:15,143 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 66 [2025-03-16 18:11:15,143 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:15,143 INFO L218 NwaCegarLoop]: trace histogram [8, 7, 7, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:11:15,150 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2025-03-16 18:11:15,348 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2025-03-16 18:11:15,348 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:15,348 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:15,348 INFO L85 PathProgramCache]: Analyzing trace with hash 2061499091, now seen corresponding path program 1 times [2025-03-16 18:11:15,348 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:15,348 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [186908457] [2025-03-16 18:11:15,348 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:15,349 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:15,352 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 65 statements into 1 equivalence classes. [2025-03-16 18:11:15,363 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 65 of 65 statements. [2025-03-16 18:11:15,366 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:15,366 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:15,367 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1309912171] [2025-03-16 18:11:15,367 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:15,367 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:15,367 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:15,370 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:11:15,372 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2025-03-16 18:11:15,392 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 65 statements into 1 equivalence classes. [2025-03-16 18:11:15,406 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 65 of 65 statements. [2025-03-16 18:11:15,406 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:15,406 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:15,407 INFO L256 TraceCheckSpWp]: Trace formula consists of 160 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-03-16 18:11:15,411 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:15,460 INFO L134 CoverageAnalysis]: Checked inductivity of 126 backedges. 14 proven. 4 refuted. 0 times theorem prover too weak. 108 trivial. 0 not checked. [2025-03-16 18:11:15,460 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:15,509 INFO L134 CoverageAnalysis]: Checked inductivity of 126 backedges. 14 proven. 0 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2025-03-16 18:11:15,510 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:15,510 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [186908457] [2025-03-16 18:11:15,510 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:15,510 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1309912171] [2025-03-16 18:11:15,510 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1309912171] provided 1 perfect and 1 imperfect interpolant sequences [2025-03-16 18:11:15,510 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-16 18:11:15,510 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2025-03-16 18:11:15,510 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1390588630] [2025-03-16 18:11:15,510 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:11:15,510 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-16 18:11:15,511 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:15,511 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-16 18:11:15,511 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2025-03-16 18:11:15,511 INFO L87 Difference]: Start difference. First operand 211 states and 320 transitions. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2025-03-16 18:11:15,594 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:15,594 INFO L93 Difference]: Finished difference Result 217 states and 325 transitions. [2025-03-16 18:11:15,594 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-16 18:11:15,594 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) Word has length 65 [2025-03-16 18:11:15,594 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:15,597 INFO L225 Difference]: With dead ends: 217 [2025-03-16 18:11:15,597 INFO L226 Difference]: Without dead ends: 215 [2025-03-16 18:11:15,597 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 129 GetRequests, 121 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2025-03-16 18:11:15,598 INFO L435 NwaCegarLoop]: 33 mSDtfsCounter, 4 mSDsluCounter, 79 mSDsCounter, 0 mSdLazyCounter, 32 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 112 SdHoareTripleChecker+Invalid, 32 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 32 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:15,598 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 112 Invalid, 32 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 18:11:15,598 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 215 states. [2025-03-16 18:11:15,674 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 215 to 215. [2025-03-16 18:11:15,675 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 215 states, 107 states have (on average 1.2897196261682242) internal successors, (138), 114 states have internal predecessors, (138), 93 states have call successors, (93), 14 states have call predecessors, (93), 14 states have return successors, (92), 86 states have call predecessors, (92), 92 states have call successors, (92) [2025-03-16 18:11:15,677 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 215 states to 215 states and 323 transitions. [2025-03-16 18:11:15,678 INFO L78 Accepts]: Start accepts. Automaton has 215 states and 323 transitions. Word has length 65 [2025-03-16 18:11:15,678 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:15,679 INFO L471 AbstractCegarLoop]: Abstraction has 215 states and 323 transitions. [2025-03-16 18:11:15,679 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2025-03-16 18:11:15,679 INFO L276 IsEmpty]: Start isEmpty. Operand 215 states and 323 transitions. [2025-03-16 18:11:15,679 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 64 [2025-03-16 18:11:15,680 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:15,680 INFO L218 NwaCegarLoop]: trace histogram [6, 5, 5, 4, 4, 4, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:11:15,686 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2025-03-16 18:11:15,880 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:15,881 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:15,881 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:15,881 INFO L85 PathProgramCache]: Analyzing trace with hash 1341574078, now seen corresponding path program 2 times [2025-03-16 18:11:15,881 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:15,881 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1691466400] [2025-03-16 18:11:15,881 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:11:15,881 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:15,885 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 63 statements into 2 equivalence classes. [2025-03-16 18:11:15,893 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 63 of 63 statements. [2025-03-16 18:11:15,893 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:11:15,893 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:15,894 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [89698571] [2025-03-16 18:11:15,894 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:11:15,894 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:15,894 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:15,896 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:11:15,897 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2025-03-16 18:11:15,918 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 63 statements into 2 equivalence classes. [2025-03-16 18:11:15,936 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 63 of 63 statements. [2025-03-16 18:11:15,937 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:11:15,937 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:15,938 INFO L256 TraceCheckSpWp]: Trace formula consists of 183 conjuncts, 65 conjuncts are in the unsatisfiable core [2025-03-16 18:11:15,940 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:16,398 INFO L134 CoverageAnalysis]: Checked inductivity of 86 backedges. 18 proven. 25 refuted. 0 times theorem prover too weak. 43 trivial. 0 not checked. [2025-03-16 18:11:16,398 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:16,998 INFO L134 CoverageAnalysis]: Checked inductivity of 86 backedges. 15 proven. 19 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2025-03-16 18:11:16,998 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:16,999 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1691466400] [2025-03-16 18:11:16,999 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:16,999 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [89698571] [2025-03-16 18:11:16,999 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [89698571] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:11:16,999 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:11:16,999 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 15] total 31 [2025-03-16 18:11:16,999 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [499866012] [2025-03-16 18:11:16,999 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:16,999 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 31 states [2025-03-16 18:11:16,999 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:17,000 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2025-03-16 18:11:17,000 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=139, Invalid=791, Unknown=0, NotChecked=0, Total=930 [2025-03-16 18:11:17,000 INFO L87 Difference]: Start difference. First operand 215 states and 323 transitions. Second operand has 31 states, 29 states have (on average 1.5517241379310345) internal successors, (45), 27 states have internal predecessors, (45), 8 states have call successors, (17), 3 states have call predecessors, (17), 3 states have return successors, (16), 8 states have call predecessors, (16), 8 states have call successors, (16) [2025-03-16 18:11:20,575 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.68s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2025-03-16 18:11:21,501 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:21,501 INFO L93 Difference]: Finished difference Result 399 states and 591 transitions. [2025-03-16 18:11:21,502 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 39 states. [2025-03-16 18:11:21,502 INFO L78 Accepts]: Start accepts. Automaton has has 31 states, 29 states have (on average 1.5517241379310345) internal successors, (45), 27 states have internal predecessors, (45), 8 states have call successors, (17), 3 states have call predecessors, (17), 3 states have return successors, (16), 8 states have call predecessors, (16), 8 states have call successors, (16) Word has length 63 [2025-03-16 18:11:21,502 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:21,504 INFO L225 Difference]: With dead ends: 399 [2025-03-16 18:11:21,504 INFO L226 Difference]: Without dead ends: 334 [2025-03-16 18:11:21,505 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 153 GetRequests, 95 SyntacticMatches, 0 SemanticMatches, 58 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 780 ImplicationChecksByTransitivity, 2.0s TimeCoverageRelationStatistics Valid=678, Invalid=2862, Unknown=0, NotChecked=0, Total=3540 [2025-03-16 18:11:21,506 INFO L435 NwaCegarLoop]: 27 mSDtfsCounter, 144 mSDsluCounter, 359 mSDsCounter, 0 mSdLazyCounter, 939 mSolverCounterSat, 177 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 144 SdHoareTripleChecker+Valid, 386 SdHoareTripleChecker+Invalid, 1116 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 177 IncrementalHoareTripleChecker+Valid, 939 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.9s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:21,506 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [144 Valid, 386 Invalid, 1116 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [177 Valid, 939 Invalid, 0 Unknown, 0 Unchecked, 2.9s Time] [2025-03-16 18:11:21,506 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 334 states. [2025-03-16 18:11:21,613 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 334 to 287. [2025-03-16 18:11:21,614 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 287 states, 144 states have (on average 1.2708333333333333) internal successors, (183), 155 states have internal predecessors, (183), 121 states have call successors, (121), 21 states have call predecessors, (121), 21 states have return successors, (120), 110 states have call predecessors, (120), 120 states have call successors, (120) [2025-03-16 18:11:21,615 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 287 states to 287 states and 424 transitions. [2025-03-16 18:11:21,616 INFO L78 Accepts]: Start accepts. Automaton has 287 states and 424 transitions. Word has length 63 [2025-03-16 18:11:21,616 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:21,616 INFO L471 AbstractCegarLoop]: Abstraction has 287 states and 424 transitions. [2025-03-16 18:11:21,616 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 31 states, 29 states have (on average 1.5517241379310345) internal successors, (45), 27 states have internal predecessors, (45), 8 states have call successors, (17), 3 states have call predecessors, (17), 3 states have return successors, (16), 8 states have call predecessors, (16), 8 states have call successors, (16) [2025-03-16 18:11:21,616 INFO L276 IsEmpty]: Start isEmpty. Operand 287 states and 424 transitions. [2025-03-16 18:11:21,617 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 79 [2025-03-16 18:11:21,617 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:21,617 INFO L218 NwaCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:11:21,625 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 18:11:21,817 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2025-03-16 18:11:21,817 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:21,818 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:21,818 INFO L85 PathProgramCache]: Analyzing trace with hash 408526629, now seen corresponding path program 1 times [2025-03-16 18:11:21,818 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:21,818 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1506113805] [2025-03-16 18:11:21,818 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:21,818 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:21,821 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 78 statements into 1 equivalence classes. [2025-03-16 18:11:21,829 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 78 of 78 statements. [2025-03-16 18:11:21,830 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:21,830 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:21,831 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [753583896] [2025-03-16 18:11:21,832 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:21,832 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:21,832 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:21,833 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:11:21,835 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2025-03-16 18:11:21,858 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 78 statements into 1 equivalence classes. [2025-03-16 18:11:21,879 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 78 of 78 statements. [2025-03-16 18:11:21,879 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:21,879 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:21,880 INFO L256 TraceCheckSpWp]: Trace formula consists of 207 conjuncts, 70 conjuncts are in the unsatisfiable core [2025-03-16 18:11:21,882 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:22,469 INFO L134 CoverageAnalysis]: Checked inductivity of 164 backedges. 36 proven. 22 refuted. 0 times theorem prover too weak. 106 trivial. 0 not checked. [2025-03-16 18:11:22,469 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:23,189 INFO L134 CoverageAnalysis]: Checked inductivity of 164 backedges. 30 proven. 19 refuted. 0 times theorem prover too weak. 115 trivial. 0 not checked. [2025-03-16 18:11:23,189 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:23,189 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1506113805] [2025-03-16 18:11:23,189 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:23,189 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [753583896] [2025-03-16 18:11:23,189 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [753583896] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:11:23,189 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:11:23,189 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 17] total 35 [2025-03-16 18:11:23,189 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [833100256] [2025-03-16 18:11:23,189 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:23,190 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 35 states [2025-03-16 18:11:23,190 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:23,190 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 35 interpolants. [2025-03-16 18:11:23,190 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=154, Invalid=1036, Unknown=0, NotChecked=0, Total=1190 [2025-03-16 18:11:23,191 INFO L87 Difference]: Start difference. First operand 287 states and 424 transitions. Second operand has 35 states, 31 states have (on average 1.4516129032258065) internal successors, (45), 33 states have internal predecessors, (45), 10 states have call successors, (23), 3 states have call predecessors, (23), 3 states have return successors, (22), 8 states have call predecessors, (22), 8 states have call successors, (22) [2025-03-16 18:11:37,503 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:37,504 INFO L93 Difference]: Finished difference Result 519 states and 820 transitions. [2025-03-16 18:11:37,504 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 93 states. [2025-03-16 18:11:37,505 INFO L78 Accepts]: Start accepts. Automaton has has 35 states, 31 states have (on average 1.4516129032258065) internal successors, (45), 33 states have internal predecessors, (45), 10 states have call successors, (23), 3 states have call predecessors, (23), 3 states have return successors, (22), 8 states have call predecessors, (22), 8 states have call successors, (22) Word has length 78 [2025-03-16 18:11:37,505 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:37,509 INFO L225 Difference]: With dead ends: 519 [2025-03-16 18:11:37,509 INFO L226 Difference]: Without dead ends: 511 [2025-03-16 18:11:37,512 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 237 GetRequests, 121 SyntacticMatches, 0 SemanticMatches, 116 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4138 ImplicationChecksByTransitivity, 11.1s TimeCoverageRelationStatistics Valid=2405, Invalid=11401, Unknown=0, NotChecked=0, Total=13806 [2025-03-16 18:11:37,512 INFO L435 NwaCegarLoop]: 50 mSDtfsCounter, 199 mSDsluCounter, 699 mSDsCounter, 0 mSdLazyCounter, 1955 mSolverCounterSat, 289 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 199 SdHoareTripleChecker+Valid, 749 SdHoareTripleChecker+Invalid, 2244 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 289 IncrementalHoareTripleChecker+Valid, 1955 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.5s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:37,512 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [199 Valid, 749 Invalid, 2244 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [289 Valid, 1955 Invalid, 0 Unknown, 0 Unchecked, 3.5s Time] [2025-03-16 18:11:37,513 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 511 states. [2025-03-16 18:11:37,757 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 511 to 394. [2025-03-16 18:11:37,758 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 394 states, 192 states have (on average 1.3125) internal successors, (252), 206 states have internal predecessors, (252), 177 states have call successors, (177), 24 states have call predecessors, (177), 24 states have return successors, (176), 163 states have call predecessors, (176), 176 states have call successors, (176) [2025-03-16 18:11:37,760 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 394 states to 394 states and 605 transitions. [2025-03-16 18:11:37,761 INFO L78 Accepts]: Start accepts. Automaton has 394 states and 605 transitions. Word has length 78 [2025-03-16 18:11:37,761 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:37,761 INFO L471 AbstractCegarLoop]: Abstraction has 394 states and 605 transitions. [2025-03-16 18:11:37,761 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 35 states, 31 states have (on average 1.4516129032258065) internal successors, (45), 33 states have internal predecessors, (45), 10 states have call successors, (23), 3 states have call predecessors, (23), 3 states have return successors, (22), 8 states have call predecessors, (22), 8 states have call successors, (22) [2025-03-16 18:11:37,761 INFO L276 IsEmpty]: Start isEmpty. Operand 394 states and 605 transitions. [2025-03-16 18:11:37,762 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 84 [2025-03-16 18:11:37,762 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:37,762 INFO L218 NwaCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:11:37,768 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2025-03-16 18:11:37,965 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2025-03-16 18:11:37,969 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:37,969 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:37,969 INFO L85 PathProgramCache]: Analyzing trace with hash -1408173133, now seen corresponding path program 2 times [2025-03-16 18:11:37,969 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:37,969 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [149042841] [2025-03-16 18:11:37,969 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:11:37,969 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:37,973 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 83 statements into 2 equivalence classes. [2025-03-16 18:11:37,981 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 83 of 83 statements. [2025-03-16 18:11:37,981 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:11:37,981 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:38,156 INFO L134 CoverageAnalysis]: Checked inductivity of 177 backedges. 28 proven. 11 refuted. 0 times theorem prover too weak. 138 trivial. 0 not checked. [2025-03-16 18:11:38,156 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:38,156 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [149042841] [2025-03-16 18:11:38,157 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [149042841] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:11:38,157 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [805125595] [2025-03-16 18:11:38,157 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:11:38,157 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:38,157 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:38,158 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:11:38,159 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2025-03-16 18:11:38,184 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 83 statements into 2 equivalence classes. [2025-03-16 18:11:38,218 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 83 of 83 statements. [2025-03-16 18:11:38,218 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:11:38,218 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:38,219 INFO L256 TraceCheckSpWp]: Trace formula consists of 230 conjuncts, 10 conjuncts are in the unsatisfiable core [2025-03-16 18:11:38,220 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:38,274 INFO L134 CoverageAnalysis]: Checked inductivity of 177 backedges. 28 proven. 11 refuted. 0 times theorem prover too weak. 138 trivial. 0 not checked. [2025-03-16 18:11:38,274 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:38,362 INFO L134 CoverageAnalysis]: Checked inductivity of 177 backedges. 28 proven. 11 refuted. 0 times theorem prover too weak. 138 trivial. 0 not checked. [2025-03-16 18:11:38,362 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [805125595] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:11:38,362 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 18:11:38,362 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10, 10] total 13 [2025-03-16 18:11:38,362 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1113097724] [2025-03-16 18:11:38,362 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:38,363 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2025-03-16 18:11:38,363 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:38,363 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2025-03-16 18:11:38,363 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=129, Unknown=0, NotChecked=0, Total=156 [2025-03-16 18:11:38,363 INFO L87 Difference]: Start difference. First operand 394 states and 605 transitions. Second operand has 13 states, 13 states have (on average 2.5384615384615383) internal successors, (33), 13 states have internal predecessors, (33), 4 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) [2025-03-16 18:11:38,870 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:38,870 INFO L93 Difference]: Finished difference Result 651 states and 988 transitions. [2025-03-16 18:11:38,871 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2025-03-16 18:11:38,871 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 2.5384615384615383) internal successors, (33), 13 states have internal predecessors, (33), 4 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) Word has length 83 [2025-03-16 18:11:38,871 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:38,873 INFO L225 Difference]: With dead ends: 651 [2025-03-16 18:11:38,873 INFO L226 Difference]: Without dead ends: 411 [2025-03-16 18:11:38,874 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 199 GetRequests, 162 SyntacticMatches, 8 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 164 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=214, Invalid=716, Unknown=0, NotChecked=0, Total=930 [2025-03-16 18:11:38,875 INFO L435 NwaCegarLoop]: 45 mSDtfsCounter, 65 mSDsluCounter, 276 mSDsCounter, 0 mSdLazyCounter, 290 mSolverCounterSat, 91 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 69 SdHoareTripleChecker+Valid, 321 SdHoareTripleChecker+Invalid, 381 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 91 IncrementalHoareTripleChecker+Valid, 290 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:38,875 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [69 Valid, 321 Invalid, 381 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [91 Valid, 290 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-16 18:11:38,875 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 411 states. [2025-03-16 18:11:39,041 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 411 to 306. [2025-03-16 18:11:39,042 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 306 states, 163 states have (on average 1.2822085889570551) internal successors, (209), 165 states have internal predecessors, (209), 119 states have call successors, (119), 23 states have call predecessors, (119), 23 states have return successors, (118), 117 states have call predecessors, (118), 118 states have call successors, (118) [2025-03-16 18:11:39,043 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 306 states to 306 states and 446 transitions. [2025-03-16 18:11:39,044 INFO L78 Accepts]: Start accepts. Automaton has 306 states and 446 transitions. Word has length 83 [2025-03-16 18:11:39,044 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:39,044 INFO L471 AbstractCegarLoop]: Abstraction has 306 states and 446 transitions. [2025-03-16 18:11:39,044 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 2.5384615384615383) internal successors, (33), 13 states have internal predecessors, (33), 4 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) [2025-03-16 18:11:39,044 INFO L276 IsEmpty]: Start isEmpty. Operand 306 states and 446 transitions. [2025-03-16 18:11:39,045 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 97 [2025-03-16 18:11:39,045 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:39,045 INFO L218 NwaCegarLoop]: trace histogram [13, 12, 12, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:11:39,052 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2025-03-16 18:11:39,245 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2025-03-16 18:11:39,246 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:39,246 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:39,246 INFO L85 PathProgramCache]: Analyzing trace with hash -807522155, now seen corresponding path program 2 times [2025-03-16 18:11:39,246 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:39,246 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1979590264] [2025-03-16 18:11:39,246 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:11:39,246 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:39,249 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 96 statements into 2 equivalence classes. [2025-03-16 18:11:39,266 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 96 of 96 statements. [2025-03-16 18:11:39,266 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:11:39,266 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:39,267 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [787024628] [2025-03-16 18:11:39,267 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:11:39,267 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:39,267 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:39,269 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:11:39,271 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2025-03-16 18:11:39,292 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 96 statements into 2 equivalence classes. [2025-03-16 18:11:39,312 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 96 of 96 statements. [2025-03-16 18:11:39,312 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:11:39,312 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:39,313 INFO L256 TraceCheckSpWp]: Trace formula consists of 230 conjuncts, 47 conjuncts are in the unsatisfiable core [2025-03-16 18:11:39,315 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:39,721 INFO L134 CoverageAnalysis]: Checked inductivity of 329 backedges. 24 proven. 17 refuted. 0 times theorem prover too weak. 288 trivial. 0 not checked. [2025-03-16 18:11:39,721 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:40,149 INFO L134 CoverageAnalysis]: Checked inductivity of 329 backedges. 24 proven. 17 refuted. 0 times theorem prover too weak. 288 trivial. 0 not checked. [2025-03-16 18:11:40,149 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:40,149 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1979590264] [2025-03-16 18:11:40,149 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:40,149 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [787024628] [2025-03-16 18:11:40,149 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [787024628] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:11:40,149 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:11:40,149 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 22 [2025-03-16 18:11:40,149 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1176962473] [2025-03-16 18:11:40,149 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:40,150 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2025-03-16 18:11:40,150 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:40,150 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2025-03-16 18:11:40,150 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=66, Invalid=396, Unknown=0, NotChecked=0, Total=462 [2025-03-16 18:11:40,150 INFO L87 Difference]: Start difference. First operand 306 states and 446 transitions. Second operand has 22 states, 20 states have (on average 1.55) internal successors, (31), 21 states have internal predecessors, (31), 9 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (28), 7 states have call predecessors, (28), 7 states have call successors, (28) [2025-03-16 18:11:45,423 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:45,423 INFO L93 Difference]: Finished difference Result 510 states and 789 transitions. [2025-03-16 18:11:45,423 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 60 states. [2025-03-16 18:11:45,424 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 20 states have (on average 1.55) internal successors, (31), 21 states have internal predecessors, (31), 9 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (28), 7 states have call predecessors, (28), 7 states have call successors, (28) Word has length 96 [2025-03-16 18:11:45,424 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:45,426 INFO L225 Difference]: With dead ends: 510 [2025-03-16 18:11:45,426 INFO L226 Difference]: Without dead ends: 502 [2025-03-16 18:11:45,427 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 239 GetRequests, 168 SyntacticMatches, 2 SemanticMatches, 69 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1406 ImplicationChecksByTransitivity, 3.3s TimeCoverageRelationStatistics Valid=867, Invalid=4103, Unknown=0, NotChecked=0, Total=4970 [2025-03-16 18:11:45,428 INFO L435 NwaCegarLoop]: 72 mSDtfsCounter, 123 mSDsluCounter, 731 mSDsCounter, 0 mSdLazyCounter, 1176 mSolverCounterSat, 186 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 127 SdHoareTripleChecker+Valid, 803 SdHoareTripleChecker+Invalid, 1362 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 186 IncrementalHoareTripleChecker+Valid, 1176 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.9s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:45,428 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [127 Valid, 803 Invalid, 1362 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [186 Valid, 1176 Invalid, 0 Unknown, 0 Unchecked, 1.9s Time] [2025-03-16 18:11:45,428 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 502 states. [2025-03-16 18:11:45,632 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 502 to 342. [2025-03-16 18:11:45,632 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 342 states, 174 states have (on average 1.3045977011494252) internal successors, (227), 176 states have internal predecessors, (227), 143 states have call successors, (143), 24 states have call predecessors, (143), 24 states have return successors, (142), 141 states have call predecessors, (142), 142 states have call successors, (142) [2025-03-16 18:11:45,634 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 342 states to 342 states and 512 transitions. [2025-03-16 18:11:45,634 INFO L78 Accepts]: Start accepts. Automaton has 342 states and 512 transitions. Word has length 96 [2025-03-16 18:11:45,635 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:45,635 INFO L471 AbstractCegarLoop]: Abstraction has 342 states and 512 transitions. [2025-03-16 18:11:45,635 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 20 states have (on average 1.55) internal successors, (31), 21 states have internal predecessors, (31), 9 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (28), 7 states have call predecessors, (28), 7 states have call successors, (28) [2025-03-16 18:11:45,635 INFO L276 IsEmpty]: Start isEmpty. Operand 342 states and 512 transitions. [2025-03-16 18:11:45,636 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 99 [2025-03-16 18:11:45,636 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:45,636 INFO L218 NwaCegarLoop]: trace histogram [13, 12, 12, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:11:45,642 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2025-03-16 18:11:45,836 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2025-03-16 18:11:45,836 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:45,837 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:45,837 INFO L85 PathProgramCache]: Analyzing trace with hash 1069370314, now seen corresponding path program 3 times [2025-03-16 18:11:45,837 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:45,837 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [202537415] [2025-03-16 18:11:45,837 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 18:11:45,837 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:45,841 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 98 statements into 11 equivalence classes. [2025-03-16 18:11:45,862 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 11 check-sat command(s) and asserted 98 of 98 statements. [2025-03-16 18:11:45,862 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 11 check-sat command(s) [2025-03-16 18:11:45,862 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:45,863 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1917312733] [2025-03-16 18:11:45,863 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 18:11:45,863 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:45,863 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:45,865 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:11:45,866 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2025-03-16 18:11:45,889 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 98 statements into 11 equivalence classes. [2025-03-16 18:11:45,905 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) and asserted 62 of 98 statements. [2025-03-16 18:11:45,905 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2025-03-16 18:11:45,905 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:45,906 INFO L256 TraceCheckSpWp]: Trace formula consists of 167 conjuncts, 61 conjuncts are in the unsatisfiable core [2025-03-16 18:11:45,908 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:46,526 INFO L134 CoverageAnalysis]: Checked inductivity of 332 backedges. 55 proven. 27 refuted. 0 times theorem prover too weak. 250 trivial. 0 not checked. [2025-03-16 18:11:46,526 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:47,156 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:47,156 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [202537415] [2025-03-16 18:11:47,156 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:47,156 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1917312733] [2025-03-16 18:11:47,156 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1917312733] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:11:47,156 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-16 18:11:47,156 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19] total 19 [2025-03-16 18:11:47,156 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1921090743] [2025-03-16 18:11:47,156 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:47,156 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2025-03-16 18:11:47,156 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:47,156 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2025-03-16 18:11:47,157 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=126, Invalid=686, Unknown=0, NotChecked=0, Total=812 [2025-03-16 18:11:47,157 INFO L87 Difference]: Start difference. First operand 342 states and 512 transitions. Second operand has 19 states, 18 states have (on average 1.6111111111111112) internal successors, (29), 16 states have internal predecessors, (29), 4 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (13), 5 states have call predecessors, (13), 3 states have call successors, (13) [2025-03-16 18:11:47,977 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:47,977 INFO L93 Difference]: Finished difference Result 428 states and 632 transitions. [2025-03-16 18:11:47,978 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2025-03-16 18:11:47,978 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 18 states have (on average 1.6111111111111112) internal successors, (29), 16 states have internal predecessors, (29), 4 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (13), 5 states have call predecessors, (13), 3 states have call successors, (13) Word has length 98 [2025-03-16 18:11:47,978 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:47,980 INFO L225 Difference]: With dead ends: 428 [2025-03-16 18:11:47,980 INFO L226 Difference]: Without dead ends: 421 [2025-03-16 18:11:47,981 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 138 GetRequests, 103 SyntacticMatches, 0 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 273 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=227, Invalid=1105, Unknown=0, NotChecked=0, Total=1332 [2025-03-16 18:11:47,981 INFO L435 NwaCegarLoop]: 26 mSDtfsCounter, 45 mSDsluCounter, 178 mSDsCounter, 0 mSdLazyCounter, 615 mSolverCounterSat, 36 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 57 SdHoareTripleChecker+Valid, 204 SdHoareTripleChecker+Invalid, 651 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 36 IncrementalHoareTripleChecker+Valid, 615 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:47,981 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [57 Valid, 204 Invalid, 651 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [36 Valid, 615 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-03-16 18:11:47,982 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 421 states. [2025-03-16 18:11:48,242 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 421 to 410. [2025-03-16 18:11:48,244 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 410 states, 209 states have (on average 1.30622009569378) internal successors, (273), 211 states have internal predecessors, (273), 171 states have call successors, (171), 29 states have call predecessors, (171), 29 states have return successors, (170), 169 states have call predecessors, (170), 170 states have call successors, (170) [2025-03-16 18:11:48,245 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 410 states to 410 states and 614 transitions. [2025-03-16 18:11:48,246 INFO L78 Accepts]: Start accepts. Automaton has 410 states and 614 transitions. Word has length 98 [2025-03-16 18:11:48,247 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:48,247 INFO L471 AbstractCegarLoop]: Abstraction has 410 states and 614 transitions. [2025-03-16 18:11:48,247 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 18 states have (on average 1.6111111111111112) internal successors, (29), 16 states have internal predecessors, (29), 4 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (13), 5 states have call predecessors, (13), 3 states have call successors, (13) [2025-03-16 18:11:48,247 INFO L276 IsEmpty]: Start isEmpty. Operand 410 states and 614 transitions. [2025-03-16 18:11:48,249 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 102 [2025-03-16 18:11:48,250 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:48,250 INFO L218 NwaCegarLoop]: trace histogram [13, 12, 12, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:11:48,257 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2025-03-16 18:11:48,454 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable15,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:48,454 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:48,454 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:48,454 INFO L85 PathProgramCache]: Analyzing trace with hash 311264781, now seen corresponding path program 4 times [2025-03-16 18:11:48,454 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:48,454 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1251644754] [2025-03-16 18:11:48,454 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-16 18:11:48,455 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:48,459 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 101 statements into 2 equivalence classes. [2025-03-16 18:11:48,476 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 101 of 101 statements. [2025-03-16 18:11:48,476 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-03-16 18:11:48,476 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:48,477 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [880135945] [2025-03-16 18:11:48,478 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-16 18:11:48,478 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:48,478 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:48,480 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:11:48,481 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2025-03-16 18:11:48,505 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 101 statements into 2 equivalence classes. [2025-03-16 18:11:48,527 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 99 of 101 statements. [2025-03-16 18:11:48,527 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-03-16 18:11:48,527 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:48,528 INFO L256 TraceCheckSpWp]: Trace formula consists of 230 conjuncts, 84 conjuncts are in the unsatisfiable core [2025-03-16 18:11:48,530 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:49,144 INFO L134 CoverageAnalysis]: Checked inductivity of 338 backedges. 56 proven. 36 refuted. 0 times theorem prover too weak. 246 trivial. 0 not checked. [2025-03-16 18:11:49,144 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:49,922 INFO L134 CoverageAnalysis]: Checked inductivity of 338 backedges. 50 proven. 33 refuted. 0 times theorem prover too weak. 255 trivial. 0 not checked. [2025-03-16 18:11:49,922 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:49,922 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1251644754] [2025-03-16 18:11:49,922 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:49,922 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [880135945] [2025-03-16 18:11:49,922 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [880135945] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:11:49,922 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:11:49,922 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 18] total 36 [2025-03-16 18:11:49,922 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1752652929] [2025-03-16 18:11:49,923 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:49,923 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 36 states [2025-03-16 18:11:49,923 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:49,923 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 36 interpolants. [2025-03-16 18:11:49,923 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=181, Invalid=1079, Unknown=0, NotChecked=0, Total=1260 [2025-03-16 18:11:49,924 INFO L87 Difference]: Start difference. First operand 410 states and 614 transitions. Second operand has 36 states, 33 states have (on average 1.5454545454545454) internal successors, (51), 34 states have internal predecessors, (51), 11 states have call successors, (31), 3 states have call predecessors, (31), 3 states have return successors, (30), 9 states have call predecessors, (30), 9 states have call successors, (30) [2025-03-16 18:12:02,337 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:12:02,338 INFO L93 Difference]: Finished difference Result 686 states and 1014 transitions. [2025-03-16 18:12:02,338 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 84 states. [2025-03-16 18:12:02,338 INFO L78 Accepts]: Start accepts. Automaton has has 36 states, 33 states have (on average 1.5454545454545454) internal successors, (51), 34 states have internal predecessors, (51), 11 states have call successors, (31), 3 states have call predecessors, (31), 3 states have return successors, (30), 9 states have call predecessors, (30), 9 states have call successors, (30) Word has length 101 [2025-03-16 18:12:02,339 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:12:02,341 INFO L225 Difference]: With dead ends: 686 [2025-03-16 18:12:02,341 INFO L226 Difference]: Without dead ends: 555 [2025-03-16 18:12:02,344 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 272 GetRequests, 166 SyntacticMatches, 0 SemanticMatches, 106 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3174 ImplicationChecksByTransitivity, 10.6s TimeCoverageRelationStatistics Valid=2161, Invalid=9395, Unknown=0, NotChecked=0, Total=11556 [2025-03-16 18:12:02,344 INFO L435 NwaCegarLoop]: 31 mSDtfsCounter, 267 mSDsluCounter, 509 mSDsCounter, 0 mSdLazyCounter, 1358 mSolverCounterSat, 475 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 267 SdHoareTripleChecker+Valid, 540 SdHoareTripleChecker+Invalid, 1833 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 475 IncrementalHoareTripleChecker+Valid, 1358 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.0s IncrementalHoareTripleChecker+Time [2025-03-16 18:12:02,344 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [267 Valid, 540 Invalid, 1833 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [475 Valid, 1358 Invalid, 0 Unknown, 0 Unchecked, 2.0s Time] [2025-03-16 18:12:02,344 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 555 states. [2025-03-16 18:12:02,748 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 555 to 483. [2025-03-16 18:12:02,749 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 483 states, 247 states have (on average 1.2834008097165992) internal successors, (317), 250 states have internal predecessors, (317), 201 states have call successors, (201), 34 states have call predecessors, (201), 34 states have return successors, (200), 198 states have call predecessors, (200), 200 states have call successors, (200) [2025-03-16 18:12:02,751 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 483 states to 483 states and 718 transitions. [2025-03-16 18:12:02,751 INFO L78 Accepts]: Start accepts. Automaton has 483 states and 718 transitions. Word has length 101 [2025-03-16 18:12:02,752 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:12:02,752 INFO L471 AbstractCegarLoop]: Abstraction has 483 states and 718 transitions. [2025-03-16 18:12:02,752 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 36 states, 33 states have (on average 1.5454545454545454) internal successors, (51), 34 states have internal predecessors, (51), 11 states have call successors, (31), 3 states have call predecessors, (31), 3 states have return successors, (30), 9 states have call predecessors, (30), 9 states have call successors, (30) [2025-03-16 18:12:02,752 INFO L276 IsEmpty]: Start isEmpty. Operand 483 states and 718 transitions. [2025-03-16 18:12:02,753 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 105 [2025-03-16 18:12:02,753 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:12:02,753 INFO L218 NwaCegarLoop]: trace histogram [13, 12, 12, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:12:02,760 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2025-03-16 18:12:02,953 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2025-03-16 18:12:02,954 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:12:02,954 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:12:02,954 INFO L85 PathProgramCache]: Analyzing trace with hash -1999255606, now seen corresponding path program 5 times [2025-03-16 18:12:02,954 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:12:02,954 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [122759576] [2025-03-16 18:12:02,954 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-03-16 18:12:02,954 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:12:02,958 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 104 statements into 8 equivalence classes. [2025-03-16 18:12:02,970 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 8 check-sat command(s) and asserted 104 of 104 statements. [2025-03-16 18:12:02,970 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 8 check-sat command(s) [2025-03-16 18:12:02,970 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:12:02,971 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1749647963] [2025-03-16 18:12:02,971 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-03-16 18:12:02,971 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:12:02,971 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:12:02,973 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:12:02,974 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2025-03-16 18:12:03,002 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 104 statements into 8 equivalence classes. [2025-03-16 18:12:03,043 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 8 check-sat command(s) and asserted 104 of 104 statements. [2025-03-16 18:12:03,043 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 8 check-sat command(s) [2025-03-16 18:12:03,043 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:12:03,045 INFO L256 TraceCheckSpWp]: Trace formula consists of 271 conjuncts, 77 conjuncts are in the unsatisfiable core [2025-03-16 18:12:03,047 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:12:04,411 INFO L134 CoverageAnalysis]: Checked inductivity of 347 backedges. 42 proven. 98 refuted. 0 times theorem prover too weak. 207 trivial. 0 not checked. [2025-03-16 18:12:04,412 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:12:05,200 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:12:05,200 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [122759576] [2025-03-16 18:12:05,200 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:12:05,200 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1749647963] [2025-03-16 18:12:05,200 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1749647963] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:12:05,200 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-16 18:12:05,200 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [23] total 23 [2025-03-16 18:12:05,200 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [143831188] [2025-03-16 18:12:05,200 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-16 18:12:05,201 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2025-03-16 18:12:05,201 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:12:05,201 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2025-03-16 18:12:05,201 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=93, Invalid=777, Unknown=0, NotChecked=0, Total=870 [2025-03-16 18:12:05,201 INFO L87 Difference]: Start difference. First operand 483 states and 718 transitions. Second operand has 23 states, 19 states have (on average 1.6842105263157894) internal successors, (32), 19 states have internal predecessors, (32), 8 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (16), 6 states have call predecessors, (16), 7 states have call successors, (16) [2025-03-16 18:12:07,551 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:12:07,551 INFO L93 Difference]: Finished difference Result 596 states and 885 transitions. [2025-03-16 18:12:07,551 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2025-03-16 18:12:07,551 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 19 states have (on average 1.6842105263157894) internal successors, (32), 19 states have internal predecessors, (32), 8 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (16), 6 states have call predecessors, (16), 7 states have call successors, (16) Word has length 104 [2025-03-16 18:12:07,552 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:12:07,554 INFO L225 Difference]: With dead ends: 596 [2025-03-16 18:12:07,554 INFO L226 Difference]: Without dead ends: 589 [2025-03-16 18:12:07,555 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 154 GetRequests, 116 SyntacticMatches, 0 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 237 ImplicationChecksByTransitivity, 1.9s TimeCoverageRelationStatistics Valid=167, Invalid=1393, Unknown=0, NotChecked=0, Total=1560 [2025-03-16 18:12:07,555 INFO L435 NwaCegarLoop]: 46 mSDtfsCounter, 70 mSDsluCounter, 595 mSDsCounter, 0 mSdLazyCounter, 1122 mSolverCounterSat, 62 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 92 SdHoareTripleChecker+Valid, 641 SdHoareTripleChecker+Invalid, 1184 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 62 IncrementalHoareTripleChecker+Valid, 1122 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.2s IncrementalHoareTripleChecker+Time [2025-03-16 18:12:07,555 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [92 Valid, 641 Invalid, 1184 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [62 Valid, 1122 Invalid, 0 Unknown, 0 Unchecked, 1.2s Time] [2025-03-16 18:12:07,556 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 589 states. [2025-03-16 18:12:08,057 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 589 to 556. [2025-03-16 18:12:08,058 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 556 states, 280 states have (on average 1.2892857142857144) internal successors, (361), 283 states have internal predecessors, (361), 237 states have call successors, (237), 38 states have call predecessors, (237), 38 states have return successors, (236), 234 states have call predecessors, (236), 236 states have call successors, (236) [2025-03-16 18:12:08,060 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 556 states to 556 states and 834 transitions. [2025-03-16 18:12:08,061 INFO L78 Accepts]: Start accepts. Automaton has 556 states and 834 transitions. Word has length 104 [2025-03-16 18:12:08,061 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:12:08,061 INFO L471 AbstractCegarLoop]: Abstraction has 556 states and 834 transitions. [2025-03-16 18:12:08,061 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 19 states have (on average 1.6842105263157894) internal successors, (32), 19 states have internal predecessors, (32), 8 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (16), 6 states have call predecessors, (16), 7 states have call successors, (16) [2025-03-16 18:12:08,062 INFO L276 IsEmpty]: Start isEmpty. Operand 556 states and 834 transitions. [2025-03-16 18:12:08,063 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 108 [2025-03-16 18:12:08,063 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:12:08,063 INFO L218 NwaCegarLoop]: trace histogram [14, 13, 13, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:12:08,069 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2025-03-16 18:12:08,263 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2025-03-16 18:12:08,263 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:12:08,264 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:12:08,264 INFO L85 PathProgramCache]: Analyzing trace with hash 985041779, now seen corresponding path program 1 times [2025-03-16 18:12:08,264 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:12:08,264 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1471453265] [2025-03-16 18:12:08,264 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:12:08,264 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:12:08,268 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 107 statements into 1 equivalence classes. [2025-03-16 18:12:08,292 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 107 of 107 statements. [2025-03-16 18:12:08,292 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:12:08,293 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:12:08,293 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2016527078] [2025-03-16 18:12:08,293 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:12:08,293 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:12:08,293 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:12:08,296 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:12:08,298 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2025-03-16 18:12:08,322 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 107 statements into 1 equivalence classes. [2025-03-16 18:12:08,350 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 107 of 107 statements. [2025-03-16 18:12:08,350 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:12:08,350 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:12:08,355 INFO L256 TraceCheckSpWp]: Trace formula consists of 270 conjuncts, 80 conjuncts are in the unsatisfiable core [2025-03-16 18:12:08,357 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:12:09,199 INFO L134 CoverageAnalysis]: Checked inductivity of 398 backedges. 29 proven. 45 refuted. 0 times theorem prover too weak. 324 trivial. 0 not checked. [2025-03-16 18:12:09,199 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:12:10,231 INFO L134 CoverageAnalysis]: Checked inductivity of 398 backedges. 26 proven. 36 refuted. 0 times theorem prover too weak. 336 trivial. 0 not checked. [2025-03-16 18:12:10,231 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:12:10,231 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1471453265] [2025-03-16 18:12:10,231 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:12:10,231 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2016527078] [2025-03-16 18:12:10,231 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2016527078] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:12:10,231 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:12:10,231 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 17] total 36 [2025-03-16 18:12:10,232 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [824338598] [2025-03-16 18:12:10,232 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:12:10,232 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 36 states [2025-03-16 18:12:10,232 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:12:10,232 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 36 interpolants. [2025-03-16 18:12:10,233 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=226, Invalid=1034, Unknown=0, NotChecked=0, Total=1260 [2025-03-16 18:12:10,233 INFO L87 Difference]: Start difference. First operand 556 states and 834 transitions. Second operand has 36 states, 36 states have (on average 1.3611111111111112) internal successors, (49), 33 states have internal predecessors, (49), 11 states have call successors, (35), 3 states have call predecessors, (35), 2 states have return successors, (34), 11 states have call predecessors, (34), 11 states have call successors, (34) [2025-03-16 18:12:19,072 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.73s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2025-03-16 18:12:27,231 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.02s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2025-03-16 18:12:27,689 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:12:27,689 INFO L93 Difference]: Finished difference Result 863 states and 1328 transitions. [2025-03-16 18:12:27,689 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 84 states. [2025-03-16 18:12:27,689 INFO L78 Accepts]: Start accepts. Automaton has has 36 states, 36 states have (on average 1.3611111111111112) internal successors, (49), 33 states have internal predecessors, (49), 11 states have call successors, (35), 3 states have call predecessors, (35), 2 states have return successors, (34), 11 states have call predecessors, (34), 11 states have call successors, (34) Word has length 107 [2025-03-16 18:12:27,690 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:12:27,693 INFO L225 Difference]: With dead ends: 863 [2025-03-16 18:12:27,693 INFO L226 Difference]: Without dead ends: 861 [2025-03-16 18:12:27,696 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 285 GetRequests, 178 SyntacticMatches, 0 SemanticMatches, 107 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3601 ImplicationChecksByTransitivity, 11.0s TimeCoverageRelationStatistics Valid=2624, Invalid=9148, Unknown=0, NotChecked=0, Total=11772 [2025-03-16 18:12:27,696 INFO L435 NwaCegarLoop]: 36 mSDtfsCounter, 251 mSDsluCounter, 598 mSDsCounter, 0 mSdLazyCounter, 1409 mSolverCounterSat, 354 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 6.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 251 SdHoareTripleChecker+Valid, 634 SdHoareTripleChecker+Invalid, 1763 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 354 IncrementalHoareTripleChecker+Valid, 1409 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 6.3s IncrementalHoareTripleChecker+Time [2025-03-16 18:12:27,696 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [251 Valid, 634 Invalid, 1763 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [354 Valid, 1409 Invalid, 0 Unknown, 0 Unchecked, 6.3s Time] [2025-03-16 18:12:27,697 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 861 states. [2025-03-16 18:12:28,539 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 861 to 758. [2025-03-16 18:12:28,540 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 758 states, 374 states have (on average 1.3155080213903743) internal successors, (492), 378 states have internal predecessors, (492), 339 states have call successors, (339), 44 states have call predecessors, (339), 44 states have return successors, (338), 335 states have call predecessors, (338), 338 states have call successors, (338) [2025-03-16 18:12:28,543 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 758 states to 758 states and 1169 transitions. [2025-03-16 18:12:28,544 INFO L78 Accepts]: Start accepts. Automaton has 758 states and 1169 transitions. Word has length 107 [2025-03-16 18:12:28,544 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:12:28,544 INFO L471 AbstractCegarLoop]: Abstraction has 758 states and 1169 transitions. [2025-03-16 18:12:28,545 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 36 states, 36 states have (on average 1.3611111111111112) internal successors, (49), 33 states have internal predecessors, (49), 11 states have call successors, (35), 3 states have call predecessors, (35), 2 states have return successors, (34), 11 states have call predecessors, (34), 11 states have call successors, (34) [2025-03-16 18:12:28,545 INFO L276 IsEmpty]: Start isEmpty. Operand 758 states and 1169 transitions. [2025-03-16 18:12:28,546 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 113 [2025-03-16 18:12:28,546 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:12:28,546 INFO L218 NwaCegarLoop]: trace histogram [15, 14, 14, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:12:28,552 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Ended with exit code 0 [2025-03-16 18:12:28,751 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:12:28,751 INFO L396 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:12:28,751 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:12:28,751 INFO L85 PathProgramCache]: Analyzing trace with hash 448458035, now seen corresponding path program 2 times [2025-03-16 18:12:28,751 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:12:28,751 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1545185751] [2025-03-16 18:12:28,751 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:12:28,751 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:12:28,755 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 112 statements into 2 equivalence classes. [2025-03-16 18:12:28,768 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 112 of 112 statements. [2025-03-16 18:12:28,769 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:12:28,769 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:12:28,769 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1209946420] [2025-03-16 18:12:28,769 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:12:28,770 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:12:28,770 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:12:28,771 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:12:28,773 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2025-03-16 18:12:28,802 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 112 statements into 2 equivalence classes. [2025-03-16 18:12:28,830 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 112 of 112 statements. [2025-03-16 18:12:28,830 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:12:28,830 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:12:28,834 INFO L256 TraceCheckSpWp]: Trace formula consists of 279 conjuncts, 38 conjuncts are in the unsatisfiable core [2025-03-16 18:12:28,836 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:12:29,077 INFO L134 CoverageAnalysis]: Checked inductivity of 455 backedges. 40 proven. 36 refuted. 0 times theorem prover too weak. 379 trivial. 0 not checked. [2025-03-16 18:12:29,077 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:12:29,249 INFO L134 CoverageAnalysis]: Checked inductivity of 455 backedges. 48 proven. 12 refuted. 0 times theorem prover too weak. 395 trivial. 0 not checked. [2025-03-16 18:12:29,249 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:12:29,249 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1545185751] [2025-03-16 18:12:29,249 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:12:29,249 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1209946420] [2025-03-16 18:12:29,249 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1209946420] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:12:29,249 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:12:29,250 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 9] total 25 [2025-03-16 18:12:29,250 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1504151467] [2025-03-16 18:12:29,250 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:12:29,250 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2025-03-16 18:12:29,250 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:12:29,250 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2025-03-16 18:12:29,250 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=82, Invalid=518, Unknown=0, NotChecked=0, Total=600 [2025-03-16 18:12:29,251 INFO L87 Difference]: Start difference. First operand 758 states and 1169 transitions. Second operand has 25 states, 23 states have (on average 1.9130434782608696) internal successors, (44), 22 states have internal predecessors, (44), 9 states have call successors, (35), 3 states have call predecessors, (35), 2 states have return successors, (34), 9 states have call predecessors, (34), 9 states have call successors, (34) [2025-03-16 18:12:31,795 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:12:31,795 INFO L93 Difference]: Finished difference Result 1204 states and 1935 transitions. [2025-03-16 18:12:31,796 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 42 states. [2025-03-16 18:12:31,796 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 23 states have (on average 1.9130434782608696) internal successors, (44), 22 states have internal predecessors, (44), 9 states have call successors, (35), 3 states have call predecessors, (35), 2 states have return successors, (34), 9 states have call predecessors, (34), 9 states have call successors, (34) Word has length 112 [2025-03-16 18:12:31,796 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:12:31,801 INFO L225 Difference]: With dead ends: 1204 [2025-03-16 18:12:31,801 INFO L226 Difference]: Without dead ends: 1202 [2025-03-16 18:12:31,802 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 270 GetRequests, 211 SyntacticMatches, 0 SemanticMatches, 59 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 816 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=685, Invalid=2975, Unknown=0, NotChecked=0, Total=3660 [2025-03-16 18:12:31,802 INFO L435 NwaCegarLoop]: 49 mSDtfsCounter, 120 mSDsluCounter, 621 mSDsCounter, 0 mSdLazyCounter, 804 mSolverCounterSat, 138 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 124 SdHoareTripleChecker+Valid, 670 SdHoareTripleChecker+Invalid, 942 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 138 IncrementalHoareTripleChecker+Valid, 804 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2025-03-16 18:12:31,802 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [124 Valid, 670 Invalid, 942 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [138 Valid, 804 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2025-03-16 18:12:31,803 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1202 states. [2025-03-16 18:12:33,175 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1202 to 1071. [2025-03-16 18:12:33,177 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1071 states, 484 states have (on average 1.3822314049586777) internal successors, (669), 486 states have internal predecessors, (669), 535 states have call successors, (535), 51 states have call predecessors, (535), 51 states have return successors, (534), 533 states have call predecessors, (534), 534 states have call successors, (534) [2025-03-16 18:12:33,180 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1071 states to 1071 states and 1738 transitions. [2025-03-16 18:12:33,182 INFO L78 Accepts]: Start accepts. Automaton has 1071 states and 1738 transitions. Word has length 112 [2025-03-16 18:12:33,182 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:12:33,182 INFO L471 AbstractCegarLoop]: Abstraction has 1071 states and 1738 transitions. [2025-03-16 18:12:33,182 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 25 states, 23 states have (on average 1.9130434782608696) internal successors, (44), 22 states have internal predecessors, (44), 9 states have call successors, (35), 3 states have call predecessors, (35), 2 states have return successors, (34), 9 states have call predecessors, (34), 9 states have call successors, (34) [2025-03-16 18:12:33,182 INFO L276 IsEmpty]: Start isEmpty. Operand 1071 states and 1738 transitions. [2025-03-16 18:12:33,184 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 120 [2025-03-16 18:12:33,184 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:12:33,184 INFO L218 NwaCegarLoop]: trace histogram [17, 16, 16, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:12:33,190 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Forceful destruction successful, exit code 0 [2025-03-16 18:12:33,388 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,19 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:12:33,388 INFO L396 AbstractCegarLoop]: === Iteration 21 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:12:33,388 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:12:33,388 INFO L85 PathProgramCache]: Analyzing trace with hash 419380243, now seen corresponding path program 6 times [2025-03-16 18:12:33,389 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:12:33,389 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1776198803] [2025-03-16 18:12:33,389 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-03-16 18:12:33,389 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:12:33,393 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 119 statements into 12 equivalence classes. [2025-03-16 18:12:33,406 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 8 check-sat command(s) and asserted 89 of 119 statements. [2025-03-16 18:12:33,407 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 8 check-sat command(s) [2025-03-16 18:12:33,407 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:12:33,530 INFO L134 CoverageAnalysis]: Checked inductivity of 571 backedges. 35 proven. 32 refuted. 0 times theorem prover too weak. 504 trivial. 0 not checked. [2025-03-16 18:12:33,530 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:12:33,530 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1776198803] [2025-03-16 18:12:33,530 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1776198803] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:12:33,530 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1464934860] [2025-03-16 18:12:33,530 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-03-16 18:12:33,530 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:12:33,530 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:12:33,533 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:12:33,534 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Waiting until timeout for monitored process [2025-03-16 18:12:33,560 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 119 statements into 12 equivalence classes. [2025-03-16 18:12:33,585 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 8 check-sat command(s) and asserted 89 of 119 statements. [2025-03-16 18:12:33,586 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 8 check-sat command(s) [2025-03-16 18:12:33,586 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:12:33,588 INFO L256 TraceCheckSpWp]: Trace formula consists of 222 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-03-16 18:12:33,589 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:12:33,672 INFO L134 CoverageAnalysis]: Checked inductivity of 571 backedges. 35 proven. 32 refuted. 0 times theorem prover too weak. 504 trivial. 0 not checked. [2025-03-16 18:12:33,672 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:12:33,774 INFO L134 CoverageAnalysis]: Checked inductivity of 571 backedges. 35 proven. 32 refuted. 0 times theorem prover too weak. 504 trivial. 0 not checked. [2025-03-16 18:12:33,775 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1464934860] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:12:33,775 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 18:12:33,775 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10, 10] total 14 [2025-03-16 18:12:33,775 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [274684678] [2025-03-16 18:12:33,775 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 18:12:33,775 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2025-03-16 18:12:33,775 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:12:33,775 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2025-03-16 18:12:33,775 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=31, Invalid=151, Unknown=0, NotChecked=0, Total=182 [2025-03-16 18:12:33,775 INFO L87 Difference]: Start difference. First operand 1071 states and 1738 transitions. Second operand has 14 states, 14 states have (on average 2.357142857142857) internal successors, (33), 14 states have internal predecessors, (33), 7 states have call successors, (25), 2 states have call predecessors, (25), 1 states have return successors, (24), 6 states have call predecessors, (24), 6 states have call successors, (24) [2025-03-16 18:12:35,555 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:12:35,555 INFO L93 Difference]: Finished difference Result 1951 states and 3229 transitions. [2025-03-16 18:12:35,555 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-03-16 18:12:35,555 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 2.357142857142857) internal successors, (33), 14 states have internal predecessors, (33), 7 states have call successors, (25), 2 states have call predecessors, (25), 1 states have return successors, (24), 6 states have call predecessors, (24), 6 states have call successors, (24) Word has length 119 [2025-03-16 18:12:35,555 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:12:35,561 INFO L225 Difference]: With dead ends: 1951 [2025-03-16 18:12:35,561 INFO L226 Difference]: Without dead ends: 1271 [2025-03-16 18:12:35,564 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 253 GetRequests, 226 SyntacticMatches, 8 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 54 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=81, Invalid=339, Unknown=0, NotChecked=0, Total=420 [2025-03-16 18:12:35,564 INFO L435 NwaCegarLoop]: 46 mSDtfsCounter, 15 mSDsluCounter, 356 mSDsCounter, 0 mSdLazyCounter, 238 mSolverCounterSat, 32 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 402 SdHoareTripleChecker+Invalid, 270 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 32 IncrementalHoareTripleChecker+Valid, 238 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:12:35,564 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 402 Invalid, 270 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [32 Valid, 238 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 18:12:35,565 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1271 states. [2025-03-16 18:12:37,175 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1271 to 1155. [2025-03-16 18:12:37,177 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1155 states, 514 states have (on average 1.3696498054474708) internal successors, (704), 541 states have internal predecessors, (704), 589 states have call successors, (589), 51 states have call predecessors, (589), 51 states have return successors, (588), 562 states have call predecessors, (588), 588 states have call successors, (588) [2025-03-16 18:12:37,181 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1155 states to 1155 states and 1881 transitions. [2025-03-16 18:12:37,182 INFO L78 Accepts]: Start accepts. Automaton has 1155 states and 1881 transitions. Word has length 119 [2025-03-16 18:12:37,183 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:12:37,183 INFO L471 AbstractCegarLoop]: Abstraction has 1155 states and 1881 transitions. [2025-03-16 18:12:37,183 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 2.357142857142857) internal successors, (33), 14 states have internal predecessors, (33), 7 states have call successors, (25), 2 states have call predecessors, (25), 1 states have return successors, (24), 6 states have call predecessors, (24), 6 states have call successors, (24) [2025-03-16 18:12:37,183 INFO L276 IsEmpty]: Start isEmpty. Operand 1155 states and 1881 transitions. [2025-03-16 18:12:37,185 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 123 [2025-03-16 18:12:37,185 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:12:37,185 INFO L218 NwaCegarLoop]: trace histogram [17, 16, 16, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:12:37,191 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Forceful destruction successful, exit code 0 [2025-03-16 18:12:37,385 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable20,20 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:12:37,386 INFO L396 AbstractCegarLoop]: === Iteration 22 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:12:37,386 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:12:37,386 INFO L85 PathProgramCache]: Analyzing trace with hash -932847920, now seen corresponding path program 7 times [2025-03-16 18:12:37,386 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:12:37,386 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1351418584] [2025-03-16 18:12:37,386 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-03-16 18:12:37,386 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:12:37,390 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 122 statements into 1 equivalence classes. [2025-03-16 18:12:37,408 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 122 of 122 statements. [2025-03-16 18:12:37,408 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:12:37,408 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:12:37,409 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1994152244] [2025-03-16 18:12:37,409 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-03-16 18:12:37,409 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:12:37,409 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:12:37,416 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:12:37,417 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Waiting until timeout for monitored process [2025-03-16 18:12:37,450 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 122 statements into 1 equivalence classes. [2025-03-16 18:12:37,487 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 122 of 122 statements. [2025-03-16 18:12:37,487 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:12:37,487 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:12:37,494 INFO L256 TraceCheckSpWp]: Trace formula consists of 294 conjuncts, 87 conjuncts are in the unsatisfiable core [2025-03-16 18:12:37,496 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:12:38,343 INFO L134 CoverageAnalysis]: Checked inductivity of 577 backedges. 73 proven. 57 refuted. 0 times theorem prover too weak. 447 trivial. 0 not checked. [2025-03-16 18:12:38,343 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:12:40,092 INFO L134 CoverageAnalysis]: Checked inductivity of 577 backedges. 71 proven. 56 refuted. 0 times theorem prover too weak. 450 trivial. 0 not checked. [2025-03-16 18:12:40,093 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:12:40,093 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1351418584] [2025-03-16 18:12:40,093 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:12:40,093 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1994152244] [2025-03-16 18:12:40,093 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1994152244] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:12:40,093 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:12:40,093 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 21] total 39 [2025-03-16 18:12:40,093 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [824337679] [2025-03-16 18:12:40,093 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:12:40,093 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 39 states [2025-03-16 18:12:40,093 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:12:40,094 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 39 interpolants. [2025-03-16 18:12:40,094 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=184, Invalid=1298, Unknown=0, NotChecked=0, Total=1482 [2025-03-16 18:12:40,094 INFO L87 Difference]: Start difference. First operand 1155 states and 1881 transitions. Second operand has 39 states, 38 states have (on average 1.4736842105263157) internal successors, (56), 37 states have internal predecessors, (56), 15 states have call successors, (41), 3 states have call predecessors, (41), 3 states have return successors, (40), 12 states have call predecessors, (40), 13 states have call successors, (40)