./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound10.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 798a7b37 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/egcd2-ll_unwindbound10.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 aa34b6970b46b2c3f1bda76d086482188f10831dd44cba913e5171769601c6f3 --- Real Ultimate output --- This is Ultimate 0.3.0-?-798a7b3-m [2025-03-03 13:50:32,239 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-03 13:50:32,282 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2025-03-03 13:50:32,287 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-03 13:50:32,288 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-03 13:50:32,308 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-03 13:50:32,309 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-03 13:50:32,310 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-03 13:50:32,310 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-03 13:50:32,310 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-03 13:50:32,310 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-03-03 13:50:32,310 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-03-03 13:50:32,310 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-03 13:50:32,310 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-03 13:50:32,310 INFO L153 SettingsManager]: * Use SBE=true [2025-03-03 13:50:32,311 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-03 13:50:32,311 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-03-03 13:50:32,311 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-03 13:50:32,311 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-03 13:50:32,311 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-03 13:50:32,311 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-03 13:50:32,311 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-03-03 13:50:32,311 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-03-03 13:50:32,311 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-03-03 13:50:32,311 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-03 13:50:32,311 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-03 13:50:32,311 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-03 13:50:32,312 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-03 13:50:32,312 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-03 13:50:32,312 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-03 13:50:32,312 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-03-03 13:50:32,312 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-03-03 13:50:32,312 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-03 13:50:32,312 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-03 13:50:32,312 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-03-03 13:50:32,312 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-03-03 13:50:32,312 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-03-03 13:50:32,313 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-03 13:50:32,313 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-03-03 13:50:32,313 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-03-03 13:50:32,313 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-03-03 13:50:32,313 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-03-03 13:50:32,313 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-03-03 13:50:32,313 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 -> aa34b6970b46b2c3f1bda76d086482188f10831dd44cba913e5171769601c6f3 [2025-03-03 13:50:32,537 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-03 13:50:32,542 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-03 13:50:32,545 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-03 13:50:32,546 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-03 13:50:32,546 INFO L274 PluginConnector]: CDTParser initialized [2025-03-03 13:50:32,547 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound10.c [2025-03-03 13:50:33,625 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/54f8d8e18/a12a0933109f49af8a41f4ec008b5c86/FLAG86bd3f319 [2025-03-03 13:50:33,861 INFO L384 CDTParser]: Found 1 translation units. [2025-03-03 13:50:33,861 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound10.c [2025-03-03 13:50:33,867 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/54f8d8e18/a12a0933109f49af8a41f4ec008b5c86/FLAG86bd3f319 [2025-03-03 13:50:33,881 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/54f8d8e18/a12a0933109f49af8a41f4ec008b5c86 [2025-03-03 13:50:33,883 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-03 13:50:33,884 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-03 13:50:33,886 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-03 13:50:33,886 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-03 13:50:33,889 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-03 13:50:33,889 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 03.03 01:50:33" (1/1) ... [2025-03-03 13:50:33,890 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@4cf32be2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:50:33, skipping insertion in model container [2025-03-03 13:50:33,891 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 03.03 01:50:33" (1/1) ... [2025-03-03 13:50:33,902 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-03 13:50:34,008 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/egcd2-ll_unwindbound10.c[490,503] [2025-03-03 13:50:34,028 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-03 13:50:34,034 INFO L200 MainTranslator]: Completed pre-run [2025-03-03 13:50:34,041 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/egcd2-ll_unwindbound10.c[490,503] [2025-03-03 13:50:34,050 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-03 13:50:34,060 INFO L204 MainTranslator]: Completed translation [2025-03-03 13:50:34,061 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:50:34 WrapperNode [2025-03-03 13:50:34,061 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-03 13:50:34,062 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-03 13:50:34,062 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-03 13:50:34,063 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-03 13:50:34,068 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:50:34" (1/1) ... [2025-03-03 13:50:34,075 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:50:34" (1/1) ... [2025-03-03 13:50:34,088 INFO L138 Inliner]: procedures = 14, calls = 17, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 84 [2025-03-03 13:50:34,088 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-03 13:50:34,089 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-03 13:50:34,089 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-03 13:50:34,089 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-03 13:50:34,094 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:50:34" (1/1) ... [2025-03-03 13:50:34,094 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:50:34" (1/1) ... [2025-03-03 13:50:34,097 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:50:34" (1/1) ... [2025-03-03 13:50:34,107 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-03 13:50:34,107 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:50:34" (1/1) ... [2025-03-03 13:50:34,108 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:50:34" (1/1) ... [2025-03-03 13:50:34,111 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:50:34" (1/1) ... [2025-03-03 13:50:34,115 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:50:34" (1/1) ... [2025-03-03 13:50:34,115 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:50:34" (1/1) ... [2025-03-03 13:50:34,116 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:50:34" (1/1) ... [2025-03-03 13:50:34,116 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-03 13:50:34,117 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-03 13:50:34,117 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-03 13:50:34,117 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-03 13:50:34,117 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:50:34" (1/1) ... [2025-03-03 13:50:34,121 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-03 13:50:34,129 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:50:34,141 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-03 13:50:34,143 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-03 13:50:34,160 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-03 13:50:34,160 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2025-03-03 13:50:34,160 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2025-03-03 13:50:34,160 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-03-03 13:50:34,160 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-03 13:50:34,160 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-03 13:50:34,160 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2025-03-03 13:50:34,161 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2025-03-03 13:50:34,204 INFO L256 CfgBuilder]: Building ICFG [2025-03-03 13:50:34,206 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-03 13:50:34,343 INFO L? ?]: Removed 11 outVars from TransFormulas that were not future-live. [2025-03-03 13:50:34,343 INFO L307 CfgBuilder]: Performing block encoding [2025-03-03 13:50:34,349 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-03 13:50:34,349 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-03 13:50:34,349 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 03.03 01:50:34 BoogieIcfgContainer [2025-03-03 13:50:34,349 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-03 13:50:34,351 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-03-03 13:50:34,351 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-03-03 13:50:34,354 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-03-03 13:50:34,355 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 03.03 01:50:33" (1/3) ... [2025-03-03 13:50:34,355 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@28f13288 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 03.03 01:50:34, skipping insertion in model container [2025-03-03 13:50:34,355 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:50:34" (2/3) ... [2025-03-03 13:50:34,355 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@28f13288 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 03.03 01:50:34, skipping insertion in model container [2025-03-03 13:50:34,355 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 03.03 01:50:34" (3/3) ... [2025-03-03 13:50:34,356 INFO L128 eAbstractionObserver]: Analyzing ICFG egcd2-ll_unwindbound10.c [2025-03-03 13:50:34,365 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-03-03 13:50:34,366 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG egcd2-ll_unwindbound10.c that has 3 procedures, 34 locations, 1 initial locations, 2 loop locations, and 1 error locations. [2025-03-03 13:50:34,397 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-03-03 13:50:34,403 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;@7d2e9a6, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-03-03 13:50:34,403 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-03-03 13:50:34,408 INFO L276 IsEmpty]: Start isEmpty. Operand has 34 states, 20 states have (on average 1.45) internal successors, (29), 22 states have internal predecessors, (29), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2025-03-03 13:50:34,413 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2025-03-03 13:50:34,413 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:50:34,413 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-03 13:50:34,414 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:50:34,417 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:50:34,417 INFO L85 PathProgramCache]: Analyzing trace with hash 100709880, now seen corresponding path program 1 times [2025-03-03 13:50:34,422 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:50:34,424 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1093016269] [2025-03-03 13:50:34,424 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:34,425 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:50:34,470 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 28 statements into 1 equivalence classes. [2025-03-03 13:50:34,482 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 28 of 28 statements. [2025-03-03 13:50:34,482 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:34,482 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:34,525 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2025-03-03 13:50:34,525 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:50:34,526 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1093016269] [2025-03-03 13:50:34,526 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1093016269] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 13:50:34,526 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2100545030] [2025-03-03 13:50:34,526 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:34,526 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:50:34,526 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:50:34,529 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-03 13:50:34,530 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-03 13:50:34,557 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 28 statements into 1 equivalence classes. [2025-03-03 13:50:34,575 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 28 of 28 statements. [2025-03-03 13:50:34,576 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:34,576 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:34,577 INFO L256 TraceCheckSpWp]: Trace formula consists of 93 conjuncts, 1 conjuncts are in the unsatisfiable core [2025-03-03 13:50:34,581 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:50:34,589 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2025-03-03 13:50:34,589 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-03 13:50:34,589 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2100545030] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 13:50:34,589 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-03 13:50:34,589 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [2] total 2 [2025-03-03 13:50:34,591 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1254777284] [2025-03-03 13:50:34,591 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 13:50:34,593 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2025-03-03 13:50:34,593 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:50:34,603 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2025-03-03 13:50:34,603 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-03-03 13:50:34,605 INFO L87 Difference]: Start difference. First operand has 34 states, 20 states have (on average 1.45) internal successors, (29), 22 states have internal predecessors, (29), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2025-03-03 13:50:34,615 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:50:34,615 INFO L93 Difference]: Finished difference Result 65 states and 104 transitions. [2025-03-03 13:50:34,616 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2025-03-03 13:50:34,616 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) Word has length 28 [2025-03-03 13:50:34,617 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:50:34,620 INFO L225 Difference]: With dead ends: 65 [2025-03-03 13:50:34,620 INFO L226 Difference]: Without dead ends: 30 [2025-03-03 13:50:34,621 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 29 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-03-03 13:50:34,625 INFO L435 NwaCegarLoop]: 45 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 45 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-03 13:50:34,625 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 45 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-03 13:50:34,633 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 30 states. [2025-03-03 13:50:34,641 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 30 to 30. [2025-03-03 13:50:34,642 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 17 states have (on average 1.2941176470588236) internal successors, (22), 19 states have internal predecessors, (22), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2025-03-03 13:50:34,645 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 41 transitions. [2025-03-03 13:50:34,646 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 41 transitions. Word has length 28 [2025-03-03 13:50:34,647 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:50:34,647 INFO L471 AbstractCegarLoop]: Abstraction has 30 states and 41 transitions. [2025-03-03 13:50:34,647 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2025-03-03 13:50:34,647 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 41 transitions. [2025-03-03 13:50:34,648 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2025-03-03 13:50:34,648 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:50:34,648 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-03 13:50:34,653 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-03 13:50:34,848 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable0 [2025-03-03 13:50:34,848 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:50:34,849 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:50:34,849 INFO L85 PathProgramCache]: Analyzing trace with hash -1726789354, now seen corresponding path program 1 times [2025-03-03 13:50:34,849 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:50:34,849 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1185840048] [2025-03-03 13:50:34,849 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:34,849 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:50:34,855 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 29 statements into 1 equivalence classes. [2025-03-03 13:50:34,873 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 29 of 29 statements. [2025-03-03 13:50:34,873 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:34,873 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:34,953 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-03 13:50:34,953 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:50:34,954 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1185840048] [2025-03-03 13:50:34,954 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1185840048] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 13:50:34,954 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 13:50:34,954 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2025-03-03 13:50:34,954 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1384974312] [2025-03-03 13:50:34,954 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 13:50:34,954 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2025-03-03 13:50:34,954 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:50:34,955 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2025-03-03 13:50:34,955 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2025-03-03 13:50:34,955 INFO L87 Difference]: Start difference. First operand 30 states and 41 transitions. Second operand has 4 states, 4 states have (on average 2.75) 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-03 13:50:34,973 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:50:34,974 INFO L93 Difference]: Finished difference Result 40 states and 52 transitions. [2025-03-03 13:50:34,974 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2025-03-03 13:50:34,974 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.75) 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-03 13:50:34,974 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:50:34,975 INFO L225 Difference]: With dead ends: 40 [2025-03-03 13:50:34,975 INFO L226 Difference]: Without dead ends: 32 [2025-03-03 13:50:34,975 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2025-03-03 13:50:34,976 INFO L435 NwaCegarLoop]: 39 mSDtfsCounter, 7 mSDsluCounter, 61 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 100 SdHoareTripleChecker+Invalid, 9 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-03 13:50:34,976 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 100 Invalid, 9 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-03 13:50:34,976 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2025-03-03 13:50:34,980 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2025-03-03 13:50:34,980 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 19 states have (on average 1.263157894736842) internal successors, (24), 20 states have internal predecessors, (24), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2025-03-03 13:50:34,980 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 43 transitions. [2025-03-03 13:50:34,981 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 43 transitions. Word has length 29 [2025-03-03 13:50:34,981 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:50:34,981 INFO L471 AbstractCegarLoop]: Abstraction has 32 states and 43 transitions. [2025-03-03 13:50:34,981 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.75) 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-03 13:50:34,982 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 43 transitions. [2025-03-03 13:50:34,982 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2025-03-03 13:50:34,982 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:50:34,982 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] [2025-03-03 13:50:34,982 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2025-03-03 13:50:34,982 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:50:34,983 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:50:34,983 INFO L85 PathProgramCache]: Analyzing trace with hash -2044305484, now seen corresponding path program 1 times [2025-03-03 13:50:34,983 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:50:34,983 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1028988406] [2025-03-03 13:50:34,983 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:34,983 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:50:34,990 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 30 statements into 1 equivalence classes. [2025-03-03 13:50:35,005 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 30 of 30 statements. [2025-03-03 13:50:35,005 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:35,005 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:35,137 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2025-03-03 13:50:35,137 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:50:35,137 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1028988406] [2025-03-03 13:50:35,137 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1028988406] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 13:50:35,137 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1619223863] [2025-03-03 13:50:35,138 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:35,138 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:50:35,138 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:50:35,139 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-03 13:50:35,141 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-03 13:50:35,181 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 30 statements into 1 equivalence classes. [2025-03-03 13:50:35,199 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 30 of 30 statements. [2025-03-03 13:50:35,199 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:35,199 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:35,200 INFO L256 TraceCheckSpWp]: Trace formula consists of 99 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-03-03 13:50:35,202 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:50:35,331 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-03 13:50:35,333 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-03 13:50:35,334 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1619223863] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 13:50:35,334 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-03 13:50:35,334 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 10 [2025-03-03 13:50:35,334 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [236586010] [2025-03-03 13:50:35,334 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 13:50:35,334 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2025-03-03 13:50:35,334 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:50:35,334 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-03-03 13:50:35,334 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=72, Unknown=0, NotChecked=0, Total=90 [2025-03-03 13:50:35,335 INFO L87 Difference]: Start difference. First operand 32 states and 43 transitions. Second operand has 6 states, 5 states have (on average 2.4) internal successors, (12), 5 states have internal predecessors, (12), 3 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2025-03-03 13:50:35,414 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:50:35,414 INFO L93 Difference]: Finished difference Result 49 states and 67 transitions. [2025-03-03 13:50:35,414 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-03 13:50:35,414 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 2.4) internal successors, (12), 5 states have internal predecessors, (12), 3 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 30 [2025-03-03 13:50:35,415 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:50:35,415 INFO L225 Difference]: With dead ends: 49 [2025-03-03 13:50:35,415 INFO L226 Difference]: Without dead ends: 47 [2025-03-03 13:50:35,415 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 36 GetRequests, 27 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=22, Invalid=88, Unknown=0, NotChecked=0, Total=110 [2025-03-03 13:50:35,416 INFO L435 NwaCegarLoop]: 32 mSDtfsCounter, 9 mSDsluCounter, 114 mSDsCounter, 0 mSdLazyCounter, 56 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 146 SdHoareTripleChecker+Invalid, 57 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 56 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-03 13:50:35,416 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 146 Invalid, 57 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 56 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-03 13:50:35,416 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2025-03-03 13:50:35,424 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 45. [2025-03-03 13:50:35,425 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 26 states have (on average 1.3076923076923077) internal successors, (34), 28 states have internal predecessors, (34), 15 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (14), 13 states have call predecessors, (14), 14 states have call successors, (14) [2025-03-03 13:50:35,426 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 63 transitions. [2025-03-03 13:50:35,426 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 63 transitions. Word has length 30 [2025-03-03 13:50:35,426 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:50:35,426 INFO L471 AbstractCegarLoop]: Abstraction has 45 states and 63 transitions. [2025-03-03 13:50:35,427 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 2.4) internal successors, (12), 5 states have internal predecessors, (12), 3 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2025-03-03 13:50:35,427 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 63 transitions. [2025-03-03 13:50:35,427 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2025-03-03 13:50:35,427 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:50:35,427 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, 1] [2025-03-03 13:50:35,433 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2025-03-03 13:50:35,632 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-03 13:50:35,632 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:50:35,632 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:50:35,633 INFO L85 PathProgramCache]: Analyzing trace with hash -886820372, now seen corresponding path program 1 times [2025-03-03 13:50:35,633 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:50:35,633 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1471429272] [2025-03-03 13:50:35,633 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:35,633 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:50:35,638 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 32 statements into 1 equivalence classes. [2025-03-03 13:50:35,646 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 32 of 32 statements. [2025-03-03 13:50:35,646 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:35,646 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 13:50:35,647 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1584425143] [2025-03-03 13:50:35,648 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:35,648 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:50:35,648 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:50:35,650 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-03 13:50:35,651 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-03 13:50:35,681 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 32 statements into 1 equivalence classes. [2025-03-03 13:50:35,696 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 32 of 32 statements. [2025-03-03 13:50:35,697 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:35,697 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:35,699 INFO L256 TraceCheckSpWp]: Trace formula consists of 107 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-03 13:50:35,703 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:50:35,737 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-03 13:50:35,737 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-03 13:50:35,737 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:50:35,737 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1471429272] [2025-03-03 13:50:35,738 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 13:50:35,738 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1584425143] [2025-03-03 13:50:35,738 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1584425143] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 13:50:35,738 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 13:50:35,738 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-03 13:50:35,738 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1564659695] [2025-03-03 13:50:35,738 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 13:50:35,739 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-03 13:50:35,739 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:50:35,740 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-03 13:50:35,740 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-03 13:50:35,740 INFO L87 Difference]: Start difference. First operand 45 states and 63 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 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-03 13:50:35,783 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:50:35,783 INFO L93 Difference]: Finished difference Result 66 states and 95 transitions. [2025-03-03 13:50:35,783 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-03 13:50:35,784 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 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 32 [2025-03-03 13:50:35,784 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:50:35,785 INFO L225 Difference]: With dead ends: 66 [2025-03-03 13:50:35,786 INFO L226 Difference]: Without dead ends: 64 [2025-03-03 13:50:35,786 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 32 GetRequests, 28 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-03 13:50:35,786 INFO L435 NwaCegarLoop]: 38 mSDtfsCounter, 5 mSDsluCounter, 101 mSDsCounter, 0 mSdLazyCounter, 32 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 139 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-03 13:50:35,786 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 139 Invalid, 32 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-03 13:50:35,789 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2025-03-03 13:50:35,796 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 55. [2025-03-03 13:50:35,797 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 55 states, 33 states have (on average 1.303030303030303) internal successors, (43), 37 states have internal predecessors, (43), 17 states have call successors, (17), 4 states have call predecessors, (17), 4 states have return successors, (16), 13 states have call predecessors, (16), 16 states have call successors, (16) [2025-03-03 13:50:35,798 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 76 transitions. [2025-03-03 13:50:35,799 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 76 transitions. Word has length 32 [2025-03-03 13:50:35,799 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:50:35,800 INFO L471 AbstractCegarLoop]: Abstraction has 55 states and 76 transitions. [2025-03-03 13:50:35,800 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 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-03 13:50:35,800 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 76 transitions. [2025-03-03 13:50:35,800 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2025-03-03 13:50:35,800 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:50:35,800 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, 1, 1, 1] [2025-03-03 13:50:35,806 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-03 13:50:36,002 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-03 13:50:36,003 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:50:36,003 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:50:36,003 INFO L85 PathProgramCache]: Analyzing trace with hash -276176331, now seen corresponding path program 1 times [2025-03-03 13:50:36,003 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:50:36,003 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1909732524] [2025-03-03 13:50:36,003 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:36,003 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:50:36,007 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 35 statements into 1 equivalence classes. [2025-03-03 13:50:36,012 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 35 of 35 statements. [2025-03-03 13:50:36,012 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:36,012 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:36,097 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 5 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2025-03-03 13:50:36,098 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:50:36,098 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1909732524] [2025-03-03 13:50:36,098 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1909732524] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 13:50:36,100 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [253346455] [2025-03-03 13:50:36,100 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:36,101 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:50:36,101 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:50:36,102 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-03 13:50:36,104 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-03 13:50:36,128 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 35 statements into 1 equivalence classes. [2025-03-03 13:50:36,140 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 35 of 35 statements. [2025-03-03 13:50:36,140 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:36,140 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:36,141 INFO L256 TraceCheckSpWp]: Trace formula consists of 108 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-03-03 13:50:36,142 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:50:36,214 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-03-03 13:50:36,214 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-03 13:50:36,214 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [253346455] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 13:50:36,214 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-03 13:50:36,214 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 9 [2025-03-03 13:50:36,214 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [350314425] [2025-03-03 13:50:36,215 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 13:50:36,215 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-03 13:50:36,215 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:50:36,215 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-03 13:50:36,215 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=56, Unknown=0, NotChecked=0, Total=72 [2025-03-03 13:50:36,215 INFO L87 Difference]: Start difference. First operand 55 states and 76 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, (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-03 13:50:36,251 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:50:36,251 INFO L93 Difference]: Finished difference Result 63 states and 83 transitions. [2025-03-03 13:50:36,251 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-03 13:50:36,251 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, (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 35 [2025-03-03 13:50:36,252 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:50:36,252 INFO L225 Difference]: With dead ends: 63 [2025-03-03 13:50:36,252 INFO L226 Difference]: Without dead ends: 59 [2025-03-03 13:50:36,253 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 41 GetRequests, 33 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=20, Invalid=70, Unknown=0, NotChecked=0, Total=90 [2025-03-03 13:50:36,253 INFO L435 NwaCegarLoop]: 39 mSDtfsCounter, 9 mSDsluCounter, 103 mSDsCounter, 0 mSdLazyCounter, 27 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 142 SdHoareTripleChecker+Invalid, 28 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 27 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-03 13:50:36,253 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 142 Invalid, 28 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 27 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-03 13:50:36,254 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 59 states. [2025-03-03 13:50:36,258 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 59 to 58. [2025-03-03 13:50:36,259 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 58 states, 36 states have (on average 1.25) internal successors, (45), 39 states have internal predecessors, (45), 16 states have call successors, (16), 5 states have call predecessors, (16), 5 states have return successors, (15), 13 states have call predecessors, (15), 15 states have call successors, (15) [2025-03-03 13:50:36,259 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 76 transitions. [2025-03-03 13:50:36,259 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 76 transitions. Word has length 35 [2025-03-03 13:50:36,260 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:50:36,260 INFO L471 AbstractCegarLoop]: Abstraction has 58 states and 76 transitions. [2025-03-03 13:50:36,260 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, (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-03 13:50:36,260 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 76 transitions. [2025-03-03 13:50:36,260 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2025-03-03 13:50:36,260 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:50:36,260 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, 1, 1, 1] [2025-03-03 13:50:36,266 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2025-03-03 13:50:36,466 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:50:36,466 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:50:36,466 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:50:36,466 INFO L85 PathProgramCache]: Analyzing trace with hash -247836027, now seen corresponding path program 1 times [2025-03-03 13:50:36,466 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:50:36,466 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [296928748] [2025-03-03 13:50:36,467 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:36,467 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:50:36,471 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 35 statements into 1 equivalence classes. [2025-03-03 13:50:36,476 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 35 of 35 statements. [2025-03-03 13:50:36,476 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:36,476 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:36,523 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-03-03 13:50:36,523 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:50:36,523 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [296928748] [2025-03-03 13:50:36,523 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [296928748] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 13:50:36,523 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 13:50:36,523 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-03 13:50:36,523 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [777811798] [2025-03-03 13:50:36,523 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 13:50:36,524 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-03 13:50:36,524 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:50:36,524 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-03 13:50:36,525 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2025-03-03 13:50:36,525 INFO L87 Difference]: Start difference. First operand 58 states and 76 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-03 13:50:36,545 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:50:36,545 INFO L93 Difference]: Finished difference Result 84 states and 111 transitions. [2025-03-03 13:50:36,545 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-03 13:50:36,545 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-03 13:50:36,546 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:50:36,547 INFO L225 Difference]: With dead ends: 84 [2025-03-03 13:50:36,547 INFO L226 Difference]: Without dead ends: 58 [2025-03-03 13:50:36,548 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2025-03-03 13:50:36,549 INFO L435 NwaCegarLoop]: 38 mSDtfsCounter, 10 mSDsluCounter, 62 mSDsCounter, 0 mSdLazyCounter, 12 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 100 SdHoareTripleChecker+Invalid, 16 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 12 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-03 13:50:36,549 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 100 Invalid, 16 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 12 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-03 13:50:36,549 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states. [2025-03-03 13:50:36,554 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 58. [2025-03-03 13:50:36,554 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 58 states, 36 states have (on average 1.2222222222222223) internal successors, (44), 39 states have internal predecessors, (44), 16 states have call successors, (16), 5 states have call predecessors, (16), 5 states have return successors, (15), 13 states have call predecessors, (15), 15 states have call successors, (15) [2025-03-03 13:50:36,555 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 75 transitions. [2025-03-03 13:50:36,555 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 75 transitions. Word has length 35 [2025-03-03 13:50:36,555 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:50:36,555 INFO L471 AbstractCegarLoop]: Abstraction has 58 states and 75 transitions. [2025-03-03 13:50:36,556 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-03 13:50:36,556 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 75 transitions. [2025-03-03 13:50:36,556 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2025-03-03 13:50:36,556 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:50:36,556 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, 1, 1, 1] [2025-03-03 13:50:36,556 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5 [2025-03-03 13:50:36,557 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:50:36,557 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:50:36,557 INFO L85 PathProgramCache]: Analyzing trace with hash -1535941731, now seen corresponding path program 1 times [2025-03-03 13:50:36,557 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:50:36,557 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1758860404] [2025-03-03 13:50:36,557 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:36,557 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:50:36,561 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 47 statements into 1 equivalence classes. [2025-03-03 13:50:36,569 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 47 of 47 statements. [2025-03-03 13:50:36,570 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:36,571 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 13:50:36,571 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [609818218] [2025-03-03 13:50:36,571 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:36,572 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:50:36,572 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:50:36,573 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-03 13:50:36,575 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-03 13:50:36,613 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 47 statements into 1 equivalence classes. [2025-03-03 13:50:36,626 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 47 of 47 statements. [2025-03-03 13:50:36,627 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:36,627 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:36,627 INFO L256 TraceCheckSpWp]: Trace formula consists of 134 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-03-03 13:50:36,630 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:50:36,759 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-03 13:50:36,760 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-03 13:50:36,761 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:50:36,761 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1758860404] [2025-03-03 13:50:36,761 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 13:50:36,761 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [609818218] [2025-03-03 13:50:36,761 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [609818218] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 13:50:36,761 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 13:50:36,762 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-03 13:50:36,762 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1839179127] [2025-03-03 13:50:36,763 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 13:50:36,763 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-03 13:50:36,763 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:50:36,763 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-03 13:50:36,763 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-03 13:50:36,764 INFO L87 Difference]: Start difference. First operand 58 states and 75 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, (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-03 13:50:36,809 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:50:36,809 INFO L93 Difference]: Finished difference Result 65 states and 81 transitions. [2025-03-03 13:50:36,810 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-03 13:50:36,810 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, (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 47 [2025-03-03 13:50:36,810 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:50:36,810 INFO L225 Difference]: With dead ends: 65 [2025-03-03 13:50:36,811 INFO L226 Difference]: Without dead ends: 63 [2025-03-03 13:50:36,811 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 47 GetRequests, 43 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-03 13:50:36,812 INFO L435 NwaCegarLoop]: 36 mSDtfsCounter, 6 mSDsluCounter, 94 mSDsCounter, 0 mSdLazyCounter, 39 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 130 SdHoareTripleChecker+Invalid, 40 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 39 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-03 13:50:36,812 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 130 Invalid, 40 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-03 13:50:36,813 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2025-03-03 13:50:36,821 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 62. [2025-03-03 13:50:36,822 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 62 states, 39 states have (on average 1.205128205128205) internal successors, (47), 42 states have internal predecessors, (47), 16 states have call successors, (16), 6 states have call predecessors, (16), 6 states have return successors, (15), 13 states have call predecessors, (15), 15 states have call successors, (15) [2025-03-03 13:50:36,822 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 78 transitions. [2025-03-03 13:50:36,823 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 78 transitions. Word has length 47 [2025-03-03 13:50:36,823 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:50:36,823 INFO L471 AbstractCegarLoop]: Abstraction has 62 states and 78 transitions. [2025-03-03 13:50:36,823 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, (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-03 13:50:36,823 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 78 transitions. [2025-03-03 13:50:36,824 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2025-03-03 13:50:36,825 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:50:36,825 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 13:50:36,831 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-03 13:50:37,026 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-03 13:50:37,026 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:50:37,026 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:50:37,026 INFO L85 PathProgramCache]: Analyzing trace with hash 101798249, now seen corresponding path program 1 times [2025-03-03 13:50:37,026 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:50:37,026 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1617916857] [2025-03-03 13:50:37,026 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:37,026 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:50:37,030 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 55 statements into 1 equivalence classes. [2025-03-03 13:50:37,045 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 55 of 55 statements. [2025-03-03 13:50:37,045 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:37,045 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 13:50:37,045 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [230984181] [2025-03-03 13:50:37,046 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:37,046 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:50:37,046 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:50:37,048 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-03 13:50:37,049 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-03 13:50:37,073 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 55 statements into 1 equivalence classes. [2025-03-03 13:50:37,092 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 55 of 55 statements. [2025-03-03 13:50:37,093 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:37,093 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:37,095 INFO L256 TraceCheckSpWp]: Trace formula consists of 153 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-03-03 13:50:37,097 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:50:37,155 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 3 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2025-03-03 13:50:37,155 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 13:50:37,254 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 3 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2025-03-03 13:50:37,254 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:50:37,254 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1617916857] [2025-03-03 13:50:37,254 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 13:50:37,254 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [230984181] [2025-03-03 13:50:37,254 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [230984181] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 13:50:37,255 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-03 13:50:37,255 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 7 [2025-03-03 13:50:37,255 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1128520385] [2025-03-03 13:50:37,255 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-03 13:50:37,255 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2025-03-03 13:50:37,255 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:50:37,255 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2025-03-03 13:50:37,255 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2025-03-03 13:50:37,255 INFO L87 Difference]: Start difference. First operand 62 states and 78 transitions. Second operand has 7 states, 7 states have (on average 3.2857142857142856) internal successors, (23), 6 states have internal predecessors, (23), 4 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2025-03-03 13:50:37,325 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:50:37,325 INFO L93 Difference]: Finished difference Result 92 states and 127 transitions. [2025-03-03 13:50:37,325 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2025-03-03 13:50:37,326 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 3.2857142857142856) internal successors, (23), 6 states have internal predecessors, (23), 4 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) Word has length 55 [2025-03-03 13:50:37,326 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:50:37,326 INFO L225 Difference]: With dead ends: 92 [2025-03-03 13:50:37,326 INFO L226 Difference]: Without dead ends: 90 [2025-03-03 13:50:37,327 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 109 GetRequests, 100 SyntacticMatches, 3 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2025-03-03 13:50:37,327 INFO L435 NwaCegarLoop]: 45 mSDtfsCounter, 9 mSDsluCounter, 174 mSDsCounter, 0 mSdLazyCounter, 72 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 219 SdHoareTripleChecker+Invalid, 74 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 72 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-03 13:50:37,327 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 219 Invalid, 74 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 72 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-03 13:50:37,327 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 90 states. [2025-03-03 13:50:37,341 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 90 to 58. [2025-03-03 13:50:37,342 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 58 states, 37 states have (on average 1.1891891891891893) internal successors, (44), 38 states have internal predecessors, (44), 14 states have call successors, (14), 6 states have call predecessors, (14), 6 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2025-03-03 13:50:37,342 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 71 transitions. [2025-03-03 13:50:37,342 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 71 transitions. Word has length 55 [2025-03-03 13:50:37,342 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:50:37,342 INFO L471 AbstractCegarLoop]: Abstraction has 58 states and 71 transitions. [2025-03-03 13:50:37,342 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 3.2857142857142856) internal successors, (23), 6 states have internal predecessors, (23), 4 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2025-03-03 13:50:37,343 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 71 transitions. [2025-03-03 13:50:37,343 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2025-03-03 13:50:37,343 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:50:37,343 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 13:50:37,350 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2025-03-03 13:50:37,543 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-03 13:50:37,544 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:50:37,544 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:50:37,544 INFO L85 PathProgramCache]: Analyzing trace with hash -1244697335, now seen corresponding path program 1 times [2025-03-03 13:50:37,545 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:50:37,545 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1071046473] [2025-03-03 13:50:37,545 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:37,545 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:50:37,550 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 56 statements into 1 equivalence classes. [2025-03-03 13:50:37,558 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 56 of 56 statements. [2025-03-03 13:50:37,558 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:37,558 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:37,622 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-03 13:50:37,622 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:50:37,622 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1071046473] [2025-03-03 13:50:37,622 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1071046473] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 13:50:37,622 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [966166453] [2025-03-03 13:50:37,622 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:37,622 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:50:37,622 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:50:37,625 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-03 13:50:37,626 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-03 13:50:37,649 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 56 statements into 1 equivalence classes. [2025-03-03 13:50:37,663 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 56 of 56 statements. [2025-03-03 13:50:37,663 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:37,663 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:37,664 INFO L256 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-03 13:50:37,666 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:50:37,722 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-03 13:50:37,723 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 13:50:37,782 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-03 13:50:37,782 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [966166453] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 13:50:37,782 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-03 13:50:37,782 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 5, 6] total 10 [2025-03-03 13:50:37,782 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1783627876] [2025-03-03 13:50:37,782 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-03 13:50:37,782 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2025-03-03 13:50:37,782 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:50:37,783 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2025-03-03 13:50:37,783 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2025-03-03 13:50:37,783 INFO L87 Difference]: Start difference. First operand 58 states and 71 transitions. Second operand has 10 states, 10 states have (on average 3.9) internal successors, (39), 10 states have internal predecessors, (39), 5 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 4 states have call predecessors, (24), 4 states have call successors, (24) [2025-03-03 13:50:37,914 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:50:37,914 INFO L93 Difference]: Finished difference Result 211 states and 250 transitions. [2025-03-03 13:50:37,915 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2025-03-03 13:50:37,915 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 3.9) internal successors, (39), 10 states have internal predecessors, (39), 5 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 4 states have call predecessors, (24), 4 states have call successors, (24) Word has length 56 [2025-03-03 13:50:37,915 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:50:37,916 INFO L225 Difference]: With dead ends: 211 [2025-03-03 13:50:37,916 INFO L226 Difference]: Without dead ends: 203 [2025-03-03 13:50:37,916 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 120 GetRequests, 108 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=64, Invalid=118, Unknown=0, NotChecked=0, Total=182 [2025-03-03 13:50:37,917 INFO L435 NwaCegarLoop]: 38 mSDtfsCounter, 81 mSDsluCounter, 156 mSDsCounter, 0 mSdLazyCounter, 86 mSolverCounterSat, 18 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 81 SdHoareTripleChecker+Valid, 194 SdHoareTripleChecker+Invalid, 104 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 18 IncrementalHoareTripleChecker+Valid, 86 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-03 13:50:37,917 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [81 Valid, 194 Invalid, 104 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [18 Valid, 86 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-03 13:50:37,917 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 203 states. [2025-03-03 13:50:37,942 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 203 to 195. [2025-03-03 13:50:37,942 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 195 states, 125 states have (on average 1.192) internal successors, (149), 129 states have internal predecessors, (149), 44 states have call successors, (44), 25 states have call predecessors, (44), 25 states have return successors, (40), 40 states have call predecessors, (40), 40 states have call successors, (40) [2025-03-03 13:50:37,945 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 195 states to 195 states and 233 transitions. [2025-03-03 13:50:37,945 INFO L78 Accepts]: Start accepts. Automaton has 195 states and 233 transitions. Word has length 56 [2025-03-03 13:50:37,946 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:50:37,946 INFO L471 AbstractCegarLoop]: Abstraction has 195 states and 233 transitions. [2025-03-03 13:50:37,946 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 3.9) internal successors, (39), 10 states have internal predecessors, (39), 5 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 4 states have call predecessors, (24), 4 states have call successors, (24) [2025-03-03 13:50:37,946 INFO L276 IsEmpty]: Start isEmpty. Operand 195 states and 233 transitions. [2025-03-03 13:50:37,946 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 58 [2025-03-03 13:50:37,946 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:50:37,947 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 4, 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, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 13:50:37,953 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2025-03-03 13:50:38,148 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-03 13:50:38,148 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:50:38,149 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:50:38,149 INFO L85 PathProgramCache]: Analyzing trace with hash 15645217, now seen corresponding path program 1 times [2025-03-03 13:50:38,149 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:50:38,149 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1383081123] [2025-03-03 13:50:38,149 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:38,149 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:50:38,153 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 57 statements into 1 equivalence classes. [2025-03-03 13:50:38,158 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 57 of 57 statements. [2025-03-03 13:50:38,158 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:38,158 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:38,234 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 12 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2025-03-03 13:50:38,234 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:50:38,235 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1383081123] [2025-03-03 13:50:38,235 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1383081123] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 13:50:38,235 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [397572251] [2025-03-03 13:50:38,235 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:38,235 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:50:38,235 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:50:38,237 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-03 13:50:38,238 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-03 13:50:38,261 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 57 statements into 1 equivalence classes. [2025-03-03 13:50:38,276 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 57 of 57 statements. [2025-03-03 13:50:38,276 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:38,276 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:38,277 INFO L256 TraceCheckSpWp]: Trace formula consists of 163 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-03-03 13:50:38,278 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:50:38,315 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 12 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2025-03-03 13:50:38,316 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 13:50:38,388 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 12 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2025-03-03 13:50:38,388 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [397572251] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 13:50:38,388 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-03 13:50:38,388 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 9 [2025-03-03 13:50:38,389 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1634049886] [2025-03-03 13:50:38,389 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-03 13:50:38,389 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2025-03-03 13:50:38,389 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:50:38,389 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2025-03-03 13:50:38,389 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2025-03-03 13:50:38,389 INFO L87 Difference]: Start difference. First operand 195 states and 233 transitions. Second operand has 9 states, 9 states have (on average 3.0) internal successors, (27), 8 states have internal predecessors, (27), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2025-03-03 13:50:38,524 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:50:38,525 INFO L93 Difference]: Finished difference Result 279 states and 364 transitions. [2025-03-03 13:50:38,526 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-03-03 13:50:38,526 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 3.0) internal successors, (27), 8 states have internal predecessors, (27), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) Word has length 57 [2025-03-03 13:50:38,527 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:50:38,528 INFO L225 Difference]: With dead ends: 279 [2025-03-03 13:50:38,528 INFO L226 Difference]: Without dead ends: 259 [2025-03-03 13:50:38,528 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 125 GetRequests, 109 SyntacticMatches, 4 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=48, Invalid=134, Unknown=0, NotChecked=0, Total=182 [2025-03-03 13:50:38,529 INFO L435 NwaCegarLoop]: 48 mSDtfsCounter, 60 mSDsluCounter, 201 mSDsCounter, 0 mSdLazyCounter, 71 mSolverCounterSat, 38 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 65 SdHoareTripleChecker+Valid, 249 SdHoareTripleChecker+Invalid, 109 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 38 IncrementalHoareTripleChecker+Valid, 71 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-03 13:50:38,529 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [65 Valid, 249 Invalid, 109 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [38 Valid, 71 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-03 13:50:38,531 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 259 states. [2025-03-03 13:50:38,560 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 259 to 235. [2025-03-03 13:50:38,560 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 235 states, 152 states have (on average 1.2236842105263157) internal successors, (186), 155 states have internal predecessors, (186), 58 states have call successors, (58), 24 states have call predecessors, (58), 24 states have return successors, (55), 55 states have call predecessors, (55), 55 states have call successors, (55) [2025-03-03 13:50:38,562 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 235 states to 235 states and 299 transitions. [2025-03-03 13:50:38,562 INFO L78 Accepts]: Start accepts. Automaton has 235 states and 299 transitions. Word has length 57 [2025-03-03 13:50:38,563 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:50:38,563 INFO L471 AbstractCegarLoop]: Abstraction has 235 states and 299 transitions. [2025-03-03 13:50:38,563 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 3.0) internal successors, (27), 8 states have internal predecessors, (27), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2025-03-03 13:50:38,563 INFO L276 IsEmpty]: Start isEmpty. Operand 235 states and 299 transitions. [2025-03-03 13:50:38,564 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2025-03-03 13:50:38,564 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:50:38,565 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 13:50:38,572 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-03 13:50:38,766 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-03 13:50:38,766 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:50:38,767 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:50:38,767 INFO L85 PathProgramCache]: Analyzing trace with hash -351822558, now seen corresponding path program 1 times [2025-03-03 13:50:38,767 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:50:38,767 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [151140927] [2025-03-03 13:50:38,767 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:38,767 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:50:38,770 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 59 statements into 1 equivalence classes. [2025-03-03 13:50:38,774 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 59 of 59 statements. [2025-03-03 13:50:38,774 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:38,774 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:38,817 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2025-03-03 13:50:38,817 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:50:38,817 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [151140927] [2025-03-03 13:50:38,818 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [151140927] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 13:50:38,818 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [128437181] [2025-03-03 13:50:38,818 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:38,818 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:50:38,818 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:50:38,819 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-03 13:50:38,821 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-03 13:50:38,842 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 59 statements into 1 equivalence classes. [2025-03-03 13:50:38,855 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 59 of 59 statements. [2025-03-03 13:50:38,855 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:38,855 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:38,856 INFO L256 TraceCheckSpWp]: Trace formula consists of 172 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-03 13:50:38,857 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:50:38,901 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2025-03-03 13:50:38,901 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 13:50:38,961 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2025-03-03 13:50:38,961 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [128437181] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 13:50:38,961 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-03 13:50:38,961 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 5, 6] total 10 [2025-03-03 13:50:38,961 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [183982463] [2025-03-03 13:50:38,961 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-03 13:50:38,961 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2025-03-03 13:50:38,961 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:50:38,962 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2025-03-03 13:50:38,962 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2025-03-03 13:50:38,962 INFO L87 Difference]: Start difference. First operand 235 states and 299 transitions. Second operand has 10 states, 10 states have (on average 4.1) internal successors, (41), 10 states have internal predecessors, (41), 5 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 4 states have call predecessors, (24), 4 states have call successors, (24) [2025-03-03 13:50:39,090 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:50:39,091 INFO L93 Difference]: Finished difference Result 344 states and 448 transitions. [2025-03-03 13:50:39,091 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2025-03-03 13:50:39,091 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 4.1) internal successors, (41), 10 states have internal predecessors, (41), 5 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 4 states have call predecessors, (24), 4 states have call successors, (24) Word has length 59 [2025-03-03 13:50:39,092 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:50:39,093 INFO L225 Difference]: With dead ends: 344 [2025-03-03 13:50:39,093 INFO L226 Difference]: Without dead ends: 248 [2025-03-03 13:50:39,094 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 126 GetRequests, 114 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=63, Invalid=119, Unknown=0, NotChecked=0, Total=182 [2025-03-03 13:50:39,094 INFO L435 NwaCegarLoop]: 38 mSDtfsCounter, 68 mSDsluCounter, 141 mSDsCounter, 0 mSdLazyCounter, 70 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 68 SdHoareTripleChecker+Valid, 179 SdHoareTripleChecker+Invalid, 83 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 70 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-03 13:50:39,094 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [68 Valid, 179 Invalid, 83 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 70 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-03 13:50:39,095 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 248 states. [2025-03-03 13:50:39,122 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 248 to 244. [2025-03-03 13:50:39,122 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 244 states, 161 states have (on average 1.173913043478261) internal successors, (189), 164 states have internal predecessors, (189), 58 states have call successors, (58), 24 states have call predecessors, (58), 24 states have return successors, (55), 55 states have call predecessors, (55), 55 states have call successors, (55) [2025-03-03 13:50:39,124 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 244 states to 244 states and 302 transitions. [2025-03-03 13:50:39,124 INFO L78 Accepts]: Start accepts. Automaton has 244 states and 302 transitions. Word has length 59 [2025-03-03 13:50:39,125 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:50:39,125 INFO L471 AbstractCegarLoop]: Abstraction has 244 states and 302 transitions. [2025-03-03 13:50:39,125 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 4.1) internal successors, (41), 10 states have internal predecessors, (41), 5 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 4 states have call predecessors, (24), 4 states have call successors, (24) [2025-03-03 13:50:39,125 INFO L276 IsEmpty]: Start isEmpty. Operand 244 states and 302 transitions. [2025-03-03 13:50:39,126 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2025-03-03 13:50:39,126 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:50:39,126 INFO L218 NwaCegarLoop]: trace histogram [6, 5, 5, 4, 4, 4, 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, 1] [2025-03-03 13:50:39,132 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2025-03-03 13:50:39,327 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-03 13:50:39,327 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:50:39,331 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:50:39,331 INFO L85 PathProgramCache]: Analyzing trace with hash -1287548176, now seen corresponding path program 1 times [2025-03-03 13:50:39,331 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:50:39,331 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [875240644] [2025-03-03 13:50:39,331 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:39,331 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:50:39,339 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 64 statements into 1 equivalence classes. [2025-03-03 13:50:39,354 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 64 of 64 statements. [2025-03-03 13:50:39,354 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:39,354 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 13:50:39,355 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1942454719] [2025-03-03 13:50:39,355 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:39,355 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:50:39,355 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:50:39,368 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-03 13:50:39,370 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-03 13:50:39,409 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 64 statements into 1 equivalence classes. [2025-03-03 13:50:39,435 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 64 of 64 statements. [2025-03-03 13:50:39,436 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:39,436 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:39,436 INFO L256 TraceCheckSpWp]: Trace formula consists of 180 conjuncts, 17 conjuncts are in the unsatisfiable core [2025-03-03 13:50:39,438 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:50:39,539 INFO L134 CoverageAnalysis]: Checked inductivity of 81 backedges. 10 proven. 7 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2025-03-03 13:50:39,539 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 13:50:39,568 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:50:39,569 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [875240644] [2025-03-03 13:50:39,569 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 13:50:39,569 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1942454719] [2025-03-03 13:50:39,569 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1942454719] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 13:50:39,569 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-03 13:50:39,569 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6] total 6 [2025-03-03 13:50:39,569 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [737030096] [2025-03-03 13:50:39,569 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-03 13:50:39,569 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2025-03-03 13:50:39,570 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:50:39,570 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-03-03 13:50:39,570 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2025-03-03 13:50:39,570 INFO L87 Difference]: Start difference. First operand 244 states and 302 transitions. Second operand has 6 states, 6 states have (on average 4.0) internal successors, (24), 5 states have internal predecessors, (24), 3 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2025-03-03 13:50:39,680 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:50:39,681 INFO L93 Difference]: Finished difference Result 283 states and 355 transitions. [2025-03-03 13:50:39,681 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-03 13:50:39,681 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 4.0) internal successors, (24), 5 states have internal predecessors, (24), 3 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) Word has length 64 [2025-03-03 13:50:39,681 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:50:39,682 INFO L225 Difference]: With dead ends: 283 [2025-03-03 13:50:39,682 INFO L226 Difference]: Without dead ends: 278 [2025-03-03 13:50:39,683 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 69 GetRequests, 61 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=16, Invalid=40, Unknown=0, NotChecked=0, Total=56 [2025-03-03 13:50:39,683 INFO L435 NwaCegarLoop]: 53 mSDtfsCounter, 10 mSDsluCounter, 160 mSDsCounter, 0 mSdLazyCounter, 67 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 213 SdHoareTripleChecker+Invalid, 69 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 67 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-03 13:50:39,683 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 213 Invalid, 69 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 67 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-03 13:50:39,684 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 278 states. [2025-03-03 13:50:39,713 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 278 to 276. [2025-03-03 13:50:39,714 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 276 states, 183 states have (on average 1.185792349726776) internal successors, (217), 187 states have internal predecessors, (217), 65 states have call successors, (65), 27 states have call predecessors, (65), 27 states have return successors, (61), 61 states have call predecessors, (61), 61 states have call successors, (61) [2025-03-03 13:50:39,716 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 276 states to 276 states and 343 transitions. [2025-03-03 13:50:39,716 INFO L78 Accepts]: Start accepts. Automaton has 276 states and 343 transitions. Word has length 64 [2025-03-03 13:50:39,716 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:50:39,716 INFO L471 AbstractCegarLoop]: Abstraction has 276 states and 343 transitions. [2025-03-03 13:50:39,716 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 4.0) internal successors, (24), 5 states have internal predecessors, (24), 3 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2025-03-03 13:50:39,716 INFO L276 IsEmpty]: Start isEmpty. Operand 276 states and 343 transitions. [2025-03-03 13:50:39,717 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 70 [2025-03-03 13:50:39,717 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:50:39,717 INFO L218 NwaCegarLoop]: trace histogram [7, 6, 6, 4, 4, 4, 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] [2025-03-03 13:50:39,723 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2025-03-03 13:50:39,921 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-03 13:50:39,921 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:50:39,922 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:50:39,922 INFO L85 PathProgramCache]: Analyzing trace with hash 691051449, now seen corresponding path program 2 times [2025-03-03 13:50:39,922 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:50:39,922 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [332807626] [2025-03-03 13:50:39,922 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-03 13:50:39,922 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:50:39,926 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 69 statements into 2 equivalence classes. [2025-03-03 13:50:39,934 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 69 of 69 statements. [2025-03-03 13:50:39,934 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-03 13:50:39,934 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 13:50:39,935 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [434756095] [2025-03-03 13:50:39,935 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-03 13:50:39,935 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:50:39,935 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:50:39,936 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-03 13:50:39,938 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-03 13:50:39,961 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 69 statements into 2 equivalence classes. [2025-03-03 13:50:39,978 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 69 of 69 statements. [2025-03-03 13:50:39,978 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-03 13:50:39,978 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:39,979 INFO L256 TraceCheckSpWp]: Trace formula consists of 189 conjuncts, 23 conjuncts are in the unsatisfiable core [2025-03-03 13:50:39,980 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:50:40,116 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 12 proven. 8 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2025-03-03 13:50:40,116 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 13:50:40,186 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:50:40,186 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [332807626] [2025-03-03 13:50:40,186 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 13:50:40,186 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [434756095] [2025-03-03 13:50:40,186 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [434756095] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 13:50:40,186 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-03 13:50:40,186 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2025-03-03 13:50:40,186 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1329116444] [2025-03-03 13:50:40,186 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-03 13:50:40,187 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2025-03-03 13:50:40,187 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:50:40,187 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2025-03-03 13:50:40,187 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2025-03-03 13:50:40,187 INFO L87 Difference]: Start difference. First operand 276 states and 343 transitions. Second operand has 7 states, 7 states have (on average 3.4285714285714284) internal successors, (24), 6 states have internal predecessors, (24), 4 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) [2025-03-03 13:50:40,288 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:50:40,288 INFO L93 Difference]: Finished difference Result 291 states and 357 transitions. [2025-03-03 13:50:40,288 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2025-03-03 13:50:40,289 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 3.4285714285714284) internal successors, (24), 6 states have internal predecessors, (24), 4 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) Word has length 69 [2025-03-03 13:50:40,289 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:50:40,290 INFO L225 Difference]: With dead ends: 291 [2025-03-03 13:50:40,290 INFO L226 Difference]: Without dead ends: 289 [2025-03-03 13:50:40,290 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 92 GetRequests, 81 SyntacticMatches, 2 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=26, Invalid=84, Unknown=0, NotChecked=0, Total=110 [2025-03-03 13:50:40,290 INFO L435 NwaCegarLoop]: 46 mSDtfsCounter, 16 mSDsluCounter, 182 mSDsCounter, 0 mSdLazyCounter, 96 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 228 SdHoareTripleChecker+Invalid, 103 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 96 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-03 13:50:40,291 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 228 Invalid, 103 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 96 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-03 13:50:40,291 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 289 states. [2025-03-03 13:50:40,308 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 289 to 288. [2025-03-03 13:50:40,309 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 288 states, 192 states have (on average 1.1770833333333333) internal successors, (226), 196 states have internal predecessors, (226), 65 states have call successors, (65), 30 states have call predecessors, (65), 30 states have return successors, (61), 61 states have call predecessors, (61), 61 states have call successors, (61) [2025-03-03 13:50:40,310 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 288 states to 288 states and 352 transitions. [2025-03-03 13:50:40,310 INFO L78 Accepts]: Start accepts. Automaton has 288 states and 352 transitions. Word has length 69 [2025-03-03 13:50:40,310 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:50:40,310 INFO L471 AbstractCegarLoop]: Abstraction has 288 states and 352 transitions. [2025-03-03 13:50:40,310 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 3.4285714285714284) internal successors, (24), 6 states have internal predecessors, (24), 4 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) [2025-03-03 13:50:40,310 INFO L276 IsEmpty]: Start isEmpty. Operand 288 states and 352 transitions. [2025-03-03 13:50:40,311 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2025-03-03 13:50:40,311 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:50:40,311 INFO L218 NwaCegarLoop]: trace histogram [8, 7, 7, 4, 4, 4, 2, 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] [2025-03-03 13:50:40,317 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-03 13:50:40,515 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-03 13:50:40,515 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:50:40,515 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:50:40,515 INFO L85 PathProgramCache]: Analyzing trace with hash 239571152, now seen corresponding path program 3 times [2025-03-03 13:50:40,515 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:50:40,515 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [453786685] [2025-03-03 13:50:40,515 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-03 13:50:40,515 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:50:40,519 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 74 statements into 5 equivalence classes. [2025-03-03 13:50:40,532 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) and asserted 74 of 74 statements. [2025-03-03 13:50:40,532 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2025-03-03 13:50:40,532 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 13:50:40,532 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1314425075] [2025-03-03 13:50:40,532 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-03 13:50:40,532 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:50:40,533 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:50:40,534 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-03 13:50:40,536 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-03 13:50:40,559 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 74 statements into 5 equivalence classes. [2025-03-03 13:50:40,574 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) and asserted 54 of 74 statements. [2025-03-03 13:50:40,574 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2025-03-03 13:50:40,574 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:40,575 INFO L256 TraceCheckSpWp]: Trace formula consists of 162 conjuncts, 42 conjuncts are in the unsatisfiable core [2025-03-03 13:50:40,577 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:50:40,875 INFO L134 CoverageAnalysis]: Checked inductivity of 131 backedges. 40 proven. 10 refuted. 0 times theorem prover too weak. 81 trivial. 0 not checked. [2025-03-03 13:50:40,875 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 13:50:41,089 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:50:41,090 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [453786685] [2025-03-03 13:50:41,090 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 13:50:41,090 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1314425075] [2025-03-03 13:50:41,090 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1314425075] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 13:50:41,090 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-03 13:50:41,090 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2025-03-03 13:50:41,090 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [716639659] [2025-03-03 13:50:41,090 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-03 13:50:41,091 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2025-03-03 13:50:41,091 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:50:41,091 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2025-03-03 13:50:41,091 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=41, Invalid=231, Unknown=0, NotChecked=0, Total=272 [2025-03-03 13:50:41,091 INFO L87 Difference]: Start difference. First operand 288 states and 352 transitions. Second operand has 12 states, 11 states have (on average 2.727272727272727) internal successors, (30), 11 states have internal predecessors, (30), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 5 states have call predecessors, (11), 4 states have call successors, (11) [2025-03-03 13:50:41,308 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:50:41,309 INFO L93 Difference]: Finished difference Result 303 states and 366 transitions. [2025-03-03 13:50:41,309 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2025-03-03 13:50:41,309 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 2.727272727272727) internal successors, (30), 11 states have internal predecessors, (30), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 5 states have call predecessors, (11), 4 states have call successors, (11) Word has length 74 [2025-03-03 13:50:41,310 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:50:41,312 INFO L225 Difference]: With dead ends: 303 [2025-03-03 13:50:41,312 INFO L226 Difference]: Without dead ends: 299 [2025-03-03 13:50:41,312 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 102 GetRequests, 85 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 30 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=55, Invalid=287, Unknown=0, NotChecked=0, Total=342 [2025-03-03 13:50:41,313 INFO L435 NwaCegarLoop]: 34 mSDtfsCounter, 26 mSDsluCounter, 247 mSDsCounter, 0 mSdLazyCounter, 271 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 31 SdHoareTripleChecker+Valid, 281 SdHoareTripleChecker+Invalid, 287 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 271 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-03 13:50:41,313 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [31 Valid, 281 Invalid, 287 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 271 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-03 13:50:41,313 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 299 states. [2025-03-03 13:50:41,350 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 299 to 298. [2025-03-03 13:50:41,350 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 298 states, 200 states have (on average 1.165) internal successors, (233), 203 states have internal predecessors, (233), 65 states have call successors, (65), 33 states have call predecessors, (65), 32 states have return successors, (61), 61 states have call predecessors, (61), 61 states have call successors, (61) [2025-03-03 13:50:41,352 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 298 states to 298 states and 359 transitions. [2025-03-03 13:50:41,353 INFO L78 Accepts]: Start accepts. Automaton has 298 states and 359 transitions. Word has length 74 [2025-03-03 13:50:41,353 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:50:41,353 INFO L471 AbstractCegarLoop]: Abstraction has 298 states and 359 transitions. [2025-03-03 13:50:41,353 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 2.727272727272727) internal successors, (30), 11 states have internal predecessors, (30), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 5 states have call predecessors, (11), 4 states have call successors, (11) [2025-03-03 13:50:41,353 INFO L276 IsEmpty]: Start isEmpty. Operand 298 states and 359 transitions. [2025-03-03 13:50:41,353 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 81 [2025-03-03 13:50:41,353 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:50:41,354 INFO L218 NwaCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 2, 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-03 13:50:41,359 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-03 13:50:41,554 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-03 13:50:41,554 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:50:41,555 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:50:41,555 INFO L85 PathProgramCache]: Analyzing trace with hash 852496708, now seen corresponding path program 1 times [2025-03-03 13:50:41,555 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:50:41,555 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1156491126] [2025-03-03 13:50:41,555 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:41,555 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:50:41,560 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 80 statements into 1 equivalence classes. [2025-03-03 13:50:41,572 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 80 of 80 statements. [2025-03-03 13:50:41,572 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:41,572 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 13:50:41,573 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [312837730] [2025-03-03 13:50:41,573 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:41,573 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:50:41,573 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:50:41,575 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-03 13:50:41,576 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-03 13:50:41,602 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 80 statements into 1 equivalence classes. [2025-03-03 13:50:41,623 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 80 of 80 statements. [2025-03-03 13:50:41,623 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:41,623 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:41,629 INFO L256 TraceCheckSpWp]: Trace formula consists of 209 conjuncts, 41 conjuncts are in the unsatisfiable core [2025-03-03 13:50:41,630 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:50:42,109 INFO L134 CoverageAnalysis]: Checked inductivity of 162 backedges. 16 proven. 19 refuted. 0 times theorem prover too weak. 127 trivial. 0 not checked. [2025-03-03 13:50:42,110 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 13:50:42,406 INFO L134 CoverageAnalysis]: Checked inductivity of 162 backedges. 16 proven. 10 refuted. 0 times theorem prover too weak. 136 trivial. 0 not checked. [2025-03-03 13:50:42,407 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:50:42,407 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1156491126] [2025-03-03 13:50:42,408 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 13:50:42,408 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [312837730] [2025-03-03 13:50:42,408 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [312837730] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 13:50:42,408 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-03 13:50:42,408 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 10] total 21 [2025-03-03 13:50:42,408 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1515451239] [2025-03-03 13:50:42,408 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-03 13:50:42,408 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2025-03-03 13:50:42,408 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:50:42,409 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2025-03-03 13:50:42,410 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=64, Invalid=356, Unknown=0, NotChecked=0, Total=420 [2025-03-03 13:50:42,410 INFO L87 Difference]: Start difference. First operand 298 states and 359 transitions. Second operand has 21 states, 19 states have (on average 2.3157894736842106) internal successors, (44), 18 states have internal predecessors, (44), 10 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2025-03-03 13:50:44,105 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:50:44,105 INFO L93 Difference]: Finished difference Result 435 states and 581 transitions. [2025-03-03 13:50:44,106 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2025-03-03 13:50:44,106 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 19 states have (on average 2.3157894736842106) internal successors, (44), 18 states have internal predecessors, (44), 10 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) Word has length 80 [2025-03-03 13:50:44,106 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:50:44,108 INFO L225 Difference]: With dead ends: 435 [2025-03-03 13:50:44,108 INFO L226 Difference]: Without dead ends: 428 [2025-03-03 13:50:44,108 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 177 GetRequests, 139 SyntacticMatches, 0 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 265 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=296, Invalid=1264, Unknown=0, NotChecked=0, Total=1560 [2025-03-03 13:50:44,108 INFO L435 NwaCegarLoop]: 61 mSDtfsCounter, 134 mSDsluCounter, 700 mSDsCounter, 0 mSdLazyCounter, 559 mSolverCounterSat, 131 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 139 SdHoareTripleChecker+Valid, 761 SdHoareTripleChecker+Invalid, 690 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 131 IncrementalHoareTripleChecker+Valid, 559 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.1s IncrementalHoareTripleChecker+Time [2025-03-03 13:50:44,109 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [139 Valid, 761 Invalid, 690 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [131 Valid, 559 Invalid, 0 Unknown, 0 Unchecked, 1.1s Time] [2025-03-03 13:50:44,109 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 428 states. [2025-03-03 13:50:44,151 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 428 to 391. [2025-03-03 13:50:44,152 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 391 states, 256 states have (on average 1.23046875) internal successors, (315), 259 states have internal predecessors, (315), 100 states have call successors, (100), 34 states have call predecessors, (100), 34 states have return successors, (98), 97 states have call predecessors, (98), 98 states have call successors, (98) [2025-03-03 13:50:44,154 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 391 states to 391 states and 513 transitions. [2025-03-03 13:50:44,154 INFO L78 Accepts]: Start accepts. Automaton has 391 states and 513 transitions. Word has length 80 [2025-03-03 13:50:44,154 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:50:44,154 INFO L471 AbstractCegarLoop]: Abstraction has 391 states and 513 transitions. [2025-03-03 13:50:44,154 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 19 states have (on average 2.3157894736842106) internal successors, (44), 18 states have internal predecessors, (44), 10 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2025-03-03 13:50:44,155 INFO L276 IsEmpty]: Start isEmpty. Operand 391 states and 513 transitions. [2025-03-03 13:50:44,155 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 92 [2025-03-03 13:50:44,155 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:50:44,155 INFO L218 NwaCegarLoop]: trace histogram [10, 9, 9, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 13:50:44,161 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2025-03-03 13:50:44,360 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-03 13:50:44,360 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:50:44,360 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:50:44,361 INFO L85 PathProgramCache]: Analyzing trace with hash 2042434077, now seen corresponding path program 4 times [2025-03-03 13:50:44,361 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:50:44,361 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [786367118] [2025-03-03 13:50:44,361 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-03 13:50:44,361 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:50:44,365 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 91 statements into 2 equivalence classes. [2025-03-03 13:50:44,369 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 87 of 91 statements. [2025-03-03 13:50:44,370 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-03-03 13:50:44,370 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:44,419 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 43 proven. 0 refuted. 0 times theorem prover too weak. 168 trivial. 0 not checked. [2025-03-03 13:50:44,419 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:50:44,420 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [786367118] [2025-03-03 13:50:44,420 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [786367118] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 13:50:44,420 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 13:50:44,420 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-03 13:50:44,420 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [380826140] [2025-03-03 13:50:44,420 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 13:50:44,420 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-03 13:50:44,420 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:50:44,421 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-03 13:50:44,421 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-03 13:50:44,421 INFO L87 Difference]: Start difference. First operand 391 states and 513 transitions. Second operand has 5 states, 5 states have (on average 6.2) internal successors, (31), 5 states have internal predecessors, (31), 3 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (13), 3 states have call predecessors, (13), 3 states have call successors, (13) [2025-03-03 13:50:44,517 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:50:44,517 INFO L93 Difference]: Finished difference Result 587 states and 831 transitions. [2025-03-03 13:50:44,518 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-03 13:50:44,518 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 6.2) internal successors, (31), 5 states have internal predecessors, (31), 3 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (13), 3 states have call predecessors, (13), 3 states have call successors, (13) Word has length 91 [2025-03-03 13:50:44,518 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:50:44,520 INFO L225 Difference]: With dead ends: 587 [2025-03-03 13:50:44,520 INFO L226 Difference]: Without dead ends: 462 [2025-03-03 13:50:44,521 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-03 13:50:44,521 INFO L435 NwaCegarLoop]: 55 mSDtfsCounter, 12 mSDsluCounter, 131 mSDsCounter, 0 mSdLazyCounter, 45 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 186 SdHoareTripleChecker+Invalid, 49 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 45 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-03 13:50:44,521 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 186 Invalid, 49 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 45 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-03 13:50:44,522 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 462 states. [2025-03-03 13:50:44,594 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 462 to 410. [2025-03-03 13:50:44,594 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 410 states, 267 states have (on average 1.2397003745318351) internal successors, (331), 270 states have internal predecessors, (331), 108 states have call successors, (108), 34 states have call predecessors, (108), 34 states have return successors, (106), 105 states have call predecessors, (106), 106 states have call successors, (106) [2025-03-03 13:50:44,596 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 410 states to 410 states and 545 transitions. [2025-03-03 13:50:44,597 INFO L78 Accepts]: Start accepts. Automaton has 410 states and 545 transitions. Word has length 91 [2025-03-03 13:50:44,597 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:50:44,597 INFO L471 AbstractCegarLoop]: Abstraction has 410 states and 545 transitions. [2025-03-03 13:50:44,597 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 6.2) internal successors, (31), 5 states have internal predecessors, (31), 3 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (13), 3 states have call predecessors, (13), 3 states have call successors, (13) [2025-03-03 13:50:44,597 INFO L276 IsEmpty]: Start isEmpty. Operand 410 states and 545 transitions. [2025-03-03 13:50:44,598 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 98 [2025-03-03 13:50:44,598 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:50:44,598 INFO L218 NwaCegarLoop]: trace histogram [12, 11, 11, 4, 4, 4, 3, 3, 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, 1, 1] [2025-03-03 13:50:44,598 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable15 [2025-03-03 13:50:44,598 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:50:44,598 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:50:44,598 INFO L85 PathProgramCache]: Analyzing trace with hash 777061389, now seen corresponding path program 1 times [2025-03-03 13:50:44,598 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:50:44,598 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [341690196] [2025-03-03 13:50:44,598 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:44,599 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:50:44,602 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 97 statements into 1 equivalence classes. [2025-03-03 13:50:44,611 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 97 of 97 statements. [2025-03-03 13:50:44,611 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:44,611 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 13:50:44,612 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [848228311] [2025-03-03 13:50:44,612 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:44,612 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:50:44,612 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:50:44,614 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-03 13:50:44,615 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-03 13:50:44,640 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 97 statements into 1 equivalence classes. [2025-03-03 13:50:44,661 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 97 of 97 statements. [2025-03-03 13:50:44,661 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:44,661 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:44,662 INFO L256 TraceCheckSpWp]: Trace formula consists of 244 conjuncts, 53 conjuncts are in the unsatisfiable core [2025-03-03 13:50:44,664 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:50:45,346 INFO L134 CoverageAnalysis]: Checked inductivity of 288 backedges. 68 proven. 39 refuted. 0 times theorem prover too weak. 181 trivial. 0 not checked. [2025-03-03 13:50:45,346 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 13:51:12,733 INFO L134 CoverageAnalysis]: Checked inductivity of 288 backedges. 68 proven. 30 refuted. 0 times theorem prover too weak. 190 trivial. 0 not checked. [2025-03-03 13:51:12,733 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:51:12,733 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [341690196] [2025-03-03 13:51:12,733 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 13:51:12,733 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [848228311] [2025-03-03 13:51:12,733 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [848228311] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 13:51:12,733 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-03 13:51:12,734 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 13] total 26 [2025-03-03 13:51:12,734 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1322838238] [2025-03-03 13:51:12,734 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-03 13:51:12,734 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2025-03-03 13:51:12,734 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:51:12,734 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2025-03-03 13:51:12,735 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=111, Invalid=538, Unknown=1, NotChecked=0, Total=650 [2025-03-03 13:51:12,735 INFO L87 Difference]: Start difference. First operand 410 states and 545 transitions. Second operand has 26 states, 25 states have (on average 2.12) internal successors, (53), 21 states have internal predecessors, (53), 11 states have call successors, (31), 3 states have call predecessors, (31), 3 states have return successors, (30), 13 states have call predecessors, (30), 10 states have call successors, (30) [2025-03-03 13:51:14,323 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.20s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2025-03-03 13:51:35,013 WARN L286 SmtUtils]: Spent 16.24s on a formula simplification. DAG size of input: 76 DAG size of output: 75 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2025-03-03 13:51:44,100 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2025-03-03 13:51:48,765 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2025-03-03 13:51:56,968 WARN L286 SmtUtils]: Spent 8.11s on a formula simplification. DAG size of input: 64 DAG size of output: 63 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2025-03-03 13:52:01,704 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2025-03-03 13:52:07,109 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2025-03-03 13:52:08,437 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.33s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2025-03-03 13:52:11,280 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.84s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2025-03-03 13:52:14,314 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 3.03s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers []