./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound100.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 8fc3dc66 Calling Ultimate with: /root/.sdkman/candidates/java/21.0.5-tem/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound100.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 c3e4caaff40cd418d8c93f0410c37d1e421cc5f90c41578bfaa7bb16ff289f1e --- Real Ultimate output --- This is Ultimate 0.3.0-?-8fc3dc6-m [2025-03-16 18:11:10,158 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-16 18:11:10,206 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2025-03-16 18:11:10,210 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-16 18:11:10,210 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-16 18:11:10,231 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-16 18:11:10,232 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-16 18:11:10,232 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-16 18:11:10,232 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-16 18:11:10,233 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-16 18:11:10,233 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-03-16 18:11:10,233 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-03-16 18:11:10,234 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-16 18:11:10,234 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-16 18:11:10,234 INFO L153 SettingsManager]: * Use SBE=true [2025-03-16 18:11:10,234 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-16 18:11:10,234 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-03-16 18:11:10,235 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-16 18:11:10,235 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-16 18:11:10,235 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-16 18:11:10,235 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-16 18:11:10,235 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-03-16 18:11:10,235 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-03-16 18:11:10,235 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-03-16 18:11:10,235 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-16 18:11:10,235 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-16 18:11:10,235 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-16 18:11:10,235 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-16 18:11:10,235 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-16 18:11:10,236 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-16 18:11:10,236 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-03-16 18:11:10,236 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-03-16 18:11:10,236 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-16 18:11:10,236 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-16 18:11:10,236 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-03-16 18:11:10,236 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-03-16 18:11:10,237 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-03-16 18:11:10,237 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-16 18:11:10,237 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-03-16 18:11:10,237 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-03-16 18:11:10,237 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-03-16 18:11:10,237 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-03-16 18:11:10,237 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-03-16 18:11:10,237 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 -> c3e4caaff40cd418d8c93f0410c37d1e421cc5f90c41578bfaa7bb16ff289f1e [2025-03-16 18:11:10,447 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-16 18:11:10,456 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-16 18:11:10,458 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-16 18:11:10,459 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-16 18:11:10,459 INFO L274 PluginConnector]: CDTParser initialized [2025-03-16 18:11:10,460 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound100.c [2025-03-16 18:11:11,596 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/277adf000/d0e49a73b5814240b6c0340c9ee06560/FLAGa0e041548 [2025-03-16 18:11:11,786 INFO L384 CDTParser]: Found 1 translation units. [2025-03-16 18:11:11,789 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound100.c [2025-03-16 18:11:11,796 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/277adf000/d0e49a73b5814240b6c0340c9ee06560/FLAGa0e041548 [2025-03-16 18:11:12,151 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/277adf000/d0e49a73b5814240b6c0340c9ee06560 [2025-03-16 18:11:12,152 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-16 18:11:12,153 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-16 18:11:12,154 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-16 18:11:12,154 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-16 18:11:12,157 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-16 18:11:12,157 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.03 06:11:12" (1/1) ... [2025-03-16 18:11:12,158 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@1d076140 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:12, skipping insertion in model container [2025-03-16 18:11:12,158 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.03 06:11:12" (1/1) ... [2025-03-16 18:11:12,167 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-16 18:11:12,254 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound100.c[490,503] [2025-03-16 18:11:12,266 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-16 18:11:12,272 INFO L200 MainTranslator]: Completed pre-run [2025-03-16 18:11:12,278 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound100.c[490,503] [2025-03-16 18:11:12,284 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-16 18:11:12,294 INFO L204 MainTranslator]: Completed translation [2025-03-16 18:11:12,296 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:12 WrapperNode [2025-03-16 18:11:12,296 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-16 18:11:12,297 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-16 18:11:12,297 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-16 18:11:12,297 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-16 18:11:12,301 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:12" (1/1) ... [2025-03-16 18:11:12,306 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:12" (1/1) ... [2025-03-16 18:11:12,317 INFO L138 Inliner]: procedures = 14, calls = 16, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 74 [2025-03-16 18:11:12,319 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-16 18:11:12,319 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-16 18:11:12,319 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-16 18:11:12,319 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-16 18:11:12,325 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:12" (1/1) ... [2025-03-16 18:11:12,325 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:12" (1/1) ... [2025-03-16 18:11:12,326 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:12" (1/1) ... [2025-03-16 18:11:12,331 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2025-03-16 18:11:12,332 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:12" (1/1) ... [2025-03-16 18:11:12,332 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:12" (1/1) ... [2025-03-16 18:11:12,333 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:12" (1/1) ... [2025-03-16 18:11:12,334 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:12" (1/1) ... [2025-03-16 18:11:12,334 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:12" (1/1) ... [2025-03-16 18:11:12,335 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:12" (1/1) ... [2025-03-16 18:11:12,335 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-16 18:11:12,336 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-16 18:11:12,336 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-16 18:11:12,336 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-16 18:11:12,337 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:12" (1/1) ... [2025-03-16 18:11:12,340 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-16 18:11:12,348 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:12,358 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2025-03-16 18:11:12,360 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2025-03-16 18:11:12,376 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-16 18:11:12,376 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2025-03-16 18:11:12,376 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2025-03-16 18:11:12,376 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-03-16 18:11:12,376 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-16 18:11:12,376 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-16 18:11:12,376 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2025-03-16 18:11:12,376 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2025-03-16 18:11:12,417 INFO L256 CfgBuilder]: Building ICFG [2025-03-16 18:11:12,419 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-16 18:11:12,556 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2025-03-16 18:11:12,557 INFO L307 CfgBuilder]: Performing block encoding [2025-03-16 18:11:12,568 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-16 18:11:12,569 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-16 18:11:12,569 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 16.03 06:11:12 BoogieIcfgContainer [2025-03-16 18:11:12,569 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-16 18:11:12,572 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-03-16 18:11:12,572 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-03-16 18:11:12,576 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-03-16 18:11:12,576 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 16.03 06:11:12" (1/3) ... [2025-03-16 18:11:12,577 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@606dfcb3 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.03 06:11:12, skipping insertion in model container [2025-03-16 18:11:12,577 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:12" (2/3) ... [2025-03-16 18:11:12,577 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@606dfcb3 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.03 06:11:12, skipping insertion in model container [2025-03-16 18:11:12,577 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 16.03 06:11:12" (3/3) ... [2025-03-16 18:11:12,578 INFO L128 eAbstractionObserver]: Analyzing ICFG egcd3-ll_valuebound100.c [2025-03-16 18:11:12,589 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-03-16 18:11:12,590 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG egcd3-ll_valuebound100.c that has 3 procedures, 30 locations, 1 initial locations, 3 loop locations, and 1 error locations. [2025-03-16 18:11:12,632 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-03-16 18:11:12,643 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;@2655eee0, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-03-16 18:11:12,644 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-03-16 18:11:12,647 INFO L276 IsEmpty]: Start isEmpty. Operand has 30 states, 18 states have (on average 1.4444444444444444) internal successors, (26), 18 states have internal predecessors, (26), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2025-03-16 18:11:12,651 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2025-03-16 18:11:12,651 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:12,652 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:11:12,652 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:12,656 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:12,656 INFO L85 PathProgramCache]: Analyzing trace with hash -1461292294, now seen corresponding path program 1 times [2025-03-16 18:11:12,661 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:12,663 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1388766104] [2025-03-16 18:11:12,664 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:12,664 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:12,721 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 28 statements into 1 equivalence classes. [2025-03-16 18:11:12,754 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 28 of 28 statements. [2025-03-16 18:11:12,755 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:12,755 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:12,940 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 9 proven. 0 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2025-03-16 18:11:12,940 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:12,941 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1388766104] [2025-03-16 18:11:12,941 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1388766104] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 18:11:12,941 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 18:11:12,941 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2025-03-16 18:11:12,942 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [94555906] [2025-03-16 18:11:12,942 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:11:12,945 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2025-03-16 18:11:12,945 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:12,956 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-03-16 18:11:12,957 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2025-03-16 18:11:12,958 INFO L87 Difference]: Start difference. First operand has 30 states, 18 states have (on average 1.4444444444444444) internal successors, (26), 18 states have internal predecessors, (26), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Second operand has 6 states, 6 states have (on average 2.1666666666666665) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 1 states have call successors, (4) [2025-03-16 18:11:13,096 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:13,096 INFO L93 Difference]: Finished difference Result 67 states and 117 transitions. [2025-03-16 18:11:13,097 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-16 18:11:13,098 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.1666666666666665) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 1 states have call successors, (4) Word has length 28 [2025-03-16 18:11:13,098 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:13,102 INFO L225 Difference]: With dead ends: 67 [2025-03-16 18:11:13,102 INFO L226 Difference]: Without dead ends: 36 [2025-03-16 18:11:13,105 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2025-03-16 18:11:13,106 INFO L435 NwaCegarLoop]: 29 mSDtfsCounter, 22 mSDsluCounter, 90 mSDsCounter, 0 mSdLazyCounter, 57 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 119 SdHoareTripleChecker+Invalid, 65 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 57 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:13,107 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [27 Valid, 119 Invalid, 65 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 57 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 18:11:13,117 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36 states. [2025-03-16 18:11:13,130 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36 to 28. [2025-03-16 18:11:13,131 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 28 states, 16 states have (on average 1.25) internal successors, (20), 17 states have internal predecessors, (20), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2025-03-16 18:11:13,133 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28 states to 28 states and 37 transitions. [2025-03-16 18:11:13,135 INFO L78 Accepts]: Start accepts. Automaton has 28 states and 37 transitions. Word has length 28 [2025-03-16 18:11:13,135 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:13,135 INFO L471 AbstractCegarLoop]: Abstraction has 28 states and 37 transitions. [2025-03-16 18:11:13,136 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.1666666666666665) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 1 states have call successors, (4) [2025-03-16 18:11:13,136 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 37 transitions. [2025-03-16 18:11:13,137 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2025-03-16 18:11:13,137 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:13,137 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:11:13,137 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2025-03-16 18:11:13,137 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:13,138 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:13,138 INFO L85 PathProgramCache]: Analyzing trace with hash 1979049318, now seen corresponding path program 1 times [2025-03-16 18:11:13,138 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:13,138 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1638901060] [2025-03-16 18:11:13,138 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:13,138 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:13,146 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 29 statements into 1 equivalence classes. [2025-03-16 18:11:13,164 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 29 of 29 statements. [2025-03-16 18:11:13,166 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:13,166 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:13,168 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1457259480] [2025-03-16 18:11:13,168 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:13,168 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:13,168 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:13,173 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:11:13,174 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2025-03-16 18:11:13,212 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 29 statements into 1 equivalence classes. [2025-03-16 18:11:13,228 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 29 of 29 statements. [2025-03-16 18:11:13,229 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:13,229 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:13,230 INFO L256 TraceCheckSpWp]: Trace formula consists of 92 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-03-16 18:11:13,236 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:13,322 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-03-16 18:11:13,322 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-16 18:11:13,322 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:13,322 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1638901060] [2025-03-16 18:11:13,323 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:13,323 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1457259480] [2025-03-16 18:11:13,323 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1457259480] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 18:11:13,323 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 18:11:13,323 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-16 18:11:13,324 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1367039032] [2025-03-16 18:11:13,324 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:11:13,324 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-16 18:11:13,324 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:13,324 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-16 18:11:13,324 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-16 18:11:13,325 INFO L87 Difference]: Start difference. First operand 28 states and 37 transitions. Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2025-03-16 18:11:13,360 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:13,360 INFO L93 Difference]: Finished difference Result 42 states and 56 transitions. [2025-03-16 18:11:13,360 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-16 18:11:13,360 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 29 [2025-03-16 18:11:13,361 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:13,361 INFO L225 Difference]: With dead ends: 42 [2025-03-16 18:11:13,361 INFO L226 Difference]: Without dead ends: 40 [2025-03-16 18:11:13,362 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 25 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2025-03-16 18:11:13,362 INFO L435 NwaCegarLoop]: 31 mSDtfsCounter, 7 mSDsluCounter, 87 mSDsCounter, 0 mSdLazyCounter, 25 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 118 SdHoareTripleChecker+Invalid, 25 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 25 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:13,362 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 118 Invalid, 25 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 25 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 18:11:13,363 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40 states. [2025-03-16 18:11:13,367 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40 to 39. [2025-03-16 18:11:13,367 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 39 states, 22 states have (on average 1.2727272727272727) internal successors, (28), 23 states have internal predecessors, (28), 13 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2025-03-16 18:11:13,368 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 53 transitions. [2025-03-16 18:11:13,368 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 53 transitions. Word has length 29 [2025-03-16 18:11:13,369 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:13,369 INFO L471 AbstractCegarLoop]: Abstraction has 39 states and 53 transitions. [2025-03-16 18:11:13,369 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2025-03-16 18:11:13,369 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 53 transitions. [2025-03-16 18:11:13,369 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2025-03-16 18:11:13,369 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:13,370 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:11:13,377 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2025-03-16 18:11:13,574 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:13,574 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:13,574 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:13,574 INFO L85 PathProgramCache]: Analyzing trace with hash 351925117, now seen corresponding path program 1 times [2025-03-16 18:11:13,575 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:13,575 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [434882559] [2025-03-16 18:11:13,575 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:13,575 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:13,580 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-03-16 18:11:13,594 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-03-16 18:11:13,595 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:13,595 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:13,717 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 6 proven. 4 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2025-03-16 18:11:13,718 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:13,718 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [434882559] [2025-03-16 18:11:13,718 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [434882559] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:11:13,718 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [923190067] [2025-03-16 18:11:13,718 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:13,718 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:13,718 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:13,720 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:11:13,722 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2025-03-16 18:11:13,744 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-03-16 18:11:13,756 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-03-16 18:11:13,756 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:13,756 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:13,757 INFO L256 TraceCheckSpWp]: Trace formula consists of 102 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-03-16 18:11:13,758 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:13,783 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 6 proven. 4 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2025-03-16 18:11:13,784 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:13,876 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 6 proven. 4 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2025-03-16 18:11:13,876 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [923190067] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:11:13,876 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 18:11:13,876 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 9 [2025-03-16 18:11:13,876 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [991091923] [2025-03-16 18:11:13,876 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:13,877 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2025-03-16 18:11:13,877 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:13,877 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2025-03-16 18:11:13,877 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2025-03-16 18:11:13,877 INFO L87 Difference]: Start difference. First operand 39 states and 53 transitions. Second operand has 9 states, 9 states have (on average 2.0) internal successors, (18), 8 states have internal predecessors, (18), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2025-03-16 18:11:13,996 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:13,996 INFO L93 Difference]: Finished difference Result 81 states and 121 transitions. [2025-03-16 18:11:13,996 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-03-16 18:11:13,997 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.0) internal successors, (18), 8 states have internal predecessors, (18), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 31 [2025-03-16 18:11:13,997 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:13,997 INFO L225 Difference]: With dead ends: 81 [2025-03-16 18:11:13,997 INFO L226 Difference]: Without dead ends: 74 [2025-03-16 18:11:13,998 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 72 GetRequests, 57 SyntacticMatches, 4 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=42, Invalid=114, Unknown=0, NotChecked=0, Total=156 [2025-03-16 18:11:13,998 INFO L435 NwaCegarLoop]: 33 mSDtfsCounter, 44 mSDsluCounter, 136 mSDsCounter, 0 mSdLazyCounter, 88 mSolverCounterSat, 28 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 48 SdHoareTripleChecker+Valid, 169 SdHoareTripleChecker+Invalid, 116 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 28 IncrementalHoareTripleChecker+Valid, 88 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:13,998 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [48 Valid, 169 Invalid, 116 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [28 Valid, 88 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 18:11:13,999 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 74 states. [2025-03-16 18:11:14,010 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 74 to 53. [2025-03-16 18:11:14,011 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 53 states, 32 states have (on average 1.375) internal successors, (44), 33 states have internal predecessors, (44), 17 states have call successors, (17), 3 states have call predecessors, (17), 3 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2025-03-16 18:11:14,013 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 77 transitions. [2025-03-16 18:11:14,013 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 77 transitions. Word has length 31 [2025-03-16 18:11:14,013 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:14,013 INFO L471 AbstractCegarLoop]: Abstraction has 53 states and 77 transitions. [2025-03-16 18:11:14,013 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.0) internal successors, (18), 8 states have internal predecessors, (18), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2025-03-16 18:11:14,014 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 77 transitions. [2025-03-16 18:11:14,015 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2025-03-16 18:11:14,015 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:14,015 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:11:14,021 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2025-03-16 18:11:14,215 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2025-03-16 18:11:14,215 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:14,216 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:14,216 INFO L85 PathProgramCache]: Analyzing trace with hash -1940753085, now seen corresponding path program 1 times [2025-03-16 18:11:14,216 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:14,216 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [613726200] [2025-03-16 18:11:14,216 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:14,216 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:14,220 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 32 statements into 1 equivalence classes. [2025-03-16 18:11:14,234 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 32 of 32 statements. [2025-03-16 18:11:14,234 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:14,234 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:14,235 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1713452349] [2025-03-16 18:11:14,235 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:14,235 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:14,235 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:14,238 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:11:14,239 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2025-03-16 18:11:14,260 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 32 statements into 1 equivalence classes. [2025-03-16 18:11:14,272 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 32 of 32 statements. [2025-03-16 18:11:14,272 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:14,272 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:14,272 INFO L256 TraceCheckSpWp]: Trace formula consists of 110 conjuncts, 15 conjuncts are in the unsatisfiable core [2025-03-16 18:11:14,274 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:14,340 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-03-16 18:11:14,340 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:14,457 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-03-16 18:11:14,457 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:14,457 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [613726200] [2025-03-16 18:11:14,457 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:14,457 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1713452349] [2025-03-16 18:11:14,457 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1713452349] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:11:14,457 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:11:14,458 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 8 [2025-03-16 18:11:14,458 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1951137354] [2025-03-16 18:11:14,458 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:14,458 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2025-03-16 18:11:14,458 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:14,458 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-03-16 18:11:14,459 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2025-03-16 18:11:14,459 INFO L87 Difference]: Start difference. First operand 53 states and 77 transitions. Second operand has 8 states, 8 states have (on average 2.5) internal successors, (20), 7 states have internal predecessors, (20), 3 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2025-03-16 18:11:14,541 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:14,542 INFO L93 Difference]: Finished difference Result 82 states and 119 transitions. [2025-03-16 18:11:14,542 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-16 18:11:14,542 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 2.5) internal successors, (20), 7 states have internal predecessors, (20), 3 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 32 [2025-03-16 18:11:14,542 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:14,543 INFO L225 Difference]: With dead ends: 82 [2025-03-16 18:11:14,543 INFO L226 Difference]: Without dead ends: 80 [2025-03-16 18:11:14,543 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 63 GetRequests, 54 SyntacticMatches, 2 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2025-03-16 18:11:14,544 INFO L435 NwaCegarLoop]: 50 mSDtfsCounter, 17 mSDsluCounter, 190 mSDsCounter, 0 mSdLazyCounter, 82 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 240 SdHoareTripleChecker+Invalid, 87 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 82 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:14,544 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [25 Valid, 240 Invalid, 87 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 82 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 18:11:14,544 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 80 states. [2025-03-16 18:11:14,554 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 80 to 76. [2025-03-16 18:11:14,554 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 76 states, 46 states have (on average 1.391304347826087) internal successors, (64), 47 states have internal predecessors, (64), 25 states have call successors, (25), 4 states have call predecessors, (25), 4 states have return successors, (24), 24 states have call predecessors, (24), 24 states have call successors, (24) [2025-03-16 18:11:14,555 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 76 states to 76 states and 113 transitions. [2025-03-16 18:11:14,555 INFO L78 Accepts]: Start accepts. Automaton has 76 states and 113 transitions. Word has length 32 [2025-03-16 18:11:14,556 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:14,556 INFO L471 AbstractCegarLoop]: Abstraction has 76 states and 113 transitions. [2025-03-16 18:11:14,556 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 2.5) internal successors, (20), 7 states have internal predecessors, (20), 3 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2025-03-16 18:11:14,556 INFO L276 IsEmpty]: Start isEmpty. Operand 76 states and 113 transitions. [2025-03-16 18:11:14,556 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2025-03-16 18:11:14,556 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:14,557 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:11:14,562 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2025-03-16 18:11:14,761 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:14,761 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:14,761 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:14,762 INFO L85 PathProgramCache]: Analyzing trace with hash -908329914, now seen corresponding path program 2 times [2025-03-16 18:11:14,762 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:14,762 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1005862480] [2025-03-16 18:11:14,762 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:11:14,762 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:14,766 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 35 statements into 2 equivalence classes. [2025-03-16 18:11:14,778 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 35 of 35 statements. [2025-03-16 18:11:14,779 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:11:14,779 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:14,868 INFO L134 CoverageAnalysis]: Checked inductivity of 31 backedges. 7 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-03-16 18:11:14,870 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:14,870 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1005862480] [2025-03-16 18:11:14,870 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1005862480] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 18:11:14,870 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 18:11:14,870 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-16 18:11:14,870 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [453670183] [2025-03-16 18:11:14,870 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:11:14,870 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-16 18:11:14,870 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:14,871 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-16 18:11:14,871 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-16 18:11:14,871 INFO L87 Difference]: Start difference. First operand 76 states and 113 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2025-03-16 18:11:14,953 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:14,953 INFO L93 Difference]: Finished difference Result 115 states and 177 transitions. [2025-03-16 18:11:14,955 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-16 18:11:14,955 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 35 [2025-03-16 18:11:14,955 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:14,956 INFO L225 Difference]: With dead ends: 115 [2025-03-16 18:11:14,956 INFO L226 Difference]: Without dead ends: 86 [2025-03-16 18:11:14,956 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2025-03-16 18:11:14,957 INFO L435 NwaCegarLoop]: 34 mSDtfsCounter, 13 mSDsluCounter, 84 mSDsCounter, 0 mSdLazyCounter, 50 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 118 SdHoareTripleChecker+Invalid, 58 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 50 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:14,957 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 118 Invalid, 58 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 50 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 18:11:14,957 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 86 states. [2025-03-16 18:11:14,972 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 86 to 57. [2025-03-16 18:11:14,973 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 57 states, 35 states have (on average 1.2857142857142858) internal successors, (45), 36 states have internal predecessors, (45), 17 states have call successors, (17), 4 states have call predecessors, (17), 4 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2025-03-16 18:11:14,974 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 78 transitions. [2025-03-16 18:11:14,975 INFO L78 Accepts]: Start accepts. Automaton has 57 states and 78 transitions. Word has length 35 [2025-03-16 18:11:14,975 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:14,975 INFO L471 AbstractCegarLoop]: Abstraction has 57 states and 78 transitions. [2025-03-16 18:11:14,975 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2025-03-16 18:11:14,976 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 78 transitions. [2025-03-16 18:11:14,976 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2025-03-16 18:11:14,977 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:14,977 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:11:14,977 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4 [2025-03-16 18:11:14,977 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:14,978 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:14,978 INFO L85 PathProgramCache]: Analyzing trace with hash -1361869309, now seen corresponding path program 1 times [2025-03-16 18:11:14,978 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:14,978 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1396638896] [2025-03-16 18:11:14,978 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:14,978 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:14,985 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 37 statements into 1 equivalence classes. [2025-03-16 18:11:14,994 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 37 of 37 statements. [2025-03-16 18:11:14,994 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:14,994 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:14,995 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2007748185] [2025-03-16 18:11:14,995 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:14,995 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:14,995 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:14,997 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:11:15,002 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2025-03-16 18:11:15,027 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 37 statements into 1 equivalence classes. [2025-03-16 18:11:15,040 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 37 of 37 statements. [2025-03-16 18:11:15,040 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:15,040 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:15,041 INFO L256 TraceCheckSpWp]: Trace formula consists of 119 conjuncts, 21 conjuncts are in the unsatisfiable core [2025-03-16 18:11:15,043 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:15,140 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-03-16 18:11:15,141 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:15,190 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:15,190 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1396638896] [2025-03-16 18:11:15,190 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:15,191 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2007748185] [2025-03-16 18:11:15,191 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2007748185] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:11:15,191 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-16 18:11:15,191 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2025-03-16 18:11:15,191 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2095990145] [2025-03-16 18:11:15,191 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:15,191 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2025-03-16 18:11:15,191 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:15,191 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2025-03-16 18:11:15,191 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2025-03-16 18:11:15,191 INFO L87 Difference]: Start difference. First operand 57 states and 78 transitions. Second operand has 7 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 6 states have internal predecessors, (17), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2025-03-16 18:11:15,307 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:15,307 INFO L93 Difference]: Finished difference Result 78 states and 109 transitions. [2025-03-16 18:11:15,308 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2025-03-16 18:11:15,308 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 6 states have internal predecessors, (17), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 37 [2025-03-16 18:11:15,308 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:15,309 INFO L225 Difference]: With dead ends: 78 [2025-03-16 18:11:15,309 INFO L226 Difference]: Without dead ends: 76 [2025-03-16 18:11:15,310 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 43 GetRequests, 33 SyntacticMatches, 2 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=22, Invalid=68, Unknown=0, NotChecked=0, Total=90 [2025-03-16 18:11:15,310 INFO L435 NwaCegarLoop]: 35 mSDtfsCounter, 21 mSDsluCounter, 138 mSDsCounter, 0 mSdLazyCounter, 109 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 28 SdHoareTripleChecker+Valid, 173 SdHoareTripleChecker+Invalid, 120 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 109 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:15,310 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [28 Valid, 173 Invalid, 120 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 109 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 18:11:15,311 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 76 states. [2025-03-16 18:11:15,326 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 76 to 74. [2025-03-16 18:11:15,326 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 74 states, 43 states have (on average 1.302325581395349) internal successors, (56), 44 states have internal predecessors, (56), 25 states have call successors, (25), 5 states have call predecessors, (25), 5 states have return successors, (24), 24 states have call predecessors, (24), 24 states have call successors, (24) [2025-03-16 18:11:15,327 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 74 states to 74 states and 105 transitions. [2025-03-16 18:11:15,327 INFO L78 Accepts]: Start accepts. Automaton has 74 states and 105 transitions. Word has length 37 [2025-03-16 18:11:15,327 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:15,327 INFO L471 AbstractCegarLoop]: Abstraction has 74 states and 105 transitions. [2025-03-16 18:11:15,327 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 6 states have internal predecessors, (17), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2025-03-16 18:11:15,327 INFO L276 IsEmpty]: Start isEmpty. Operand 74 states and 105 transitions. [2025-03-16 18:11:15,328 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2025-03-16 18:11:15,328 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:15,328 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:11:15,333 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2025-03-16 18:11:15,532 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:15,532 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:15,532 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:15,532 INFO L85 PathProgramCache]: Analyzing trace with hash -1979591293, now seen corresponding path program 1 times [2025-03-16 18:11:15,532 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:15,532 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [126560543] [2025-03-16 18:11:15,532 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:15,532 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:15,538 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 42 statements into 1 equivalence classes. [2025-03-16 18:11:15,545 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 42 of 42 statements. [2025-03-16 18:11:15,545 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:15,545 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:15,546 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2022031611] [2025-03-16 18:11:15,546 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:15,546 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:15,546 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:15,548 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:11:15,549 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2025-03-16 18:11:15,573 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 42 statements into 1 equivalence classes. [2025-03-16 18:11:15,586 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 42 of 42 statements. [2025-03-16 18:11:15,586 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:15,586 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:15,589 INFO L256 TraceCheckSpWp]: Trace formula consists of 128 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-16 18:11:15,590 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:15,624 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 5 proven. 0 refuted. 0 times theorem prover too weak. 29 trivial. 0 not checked. [2025-03-16 18:11:15,624 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-16 18:11:15,624 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:15,624 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [126560543] [2025-03-16 18:11:15,624 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:15,624 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2022031611] [2025-03-16 18:11:15,624 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2022031611] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 18:11:15,624 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 18:11:15,624 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-16 18:11:15,624 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1182367783] [2025-03-16 18:11:15,624 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:11:15,625 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-16 18:11:15,625 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:15,625 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-16 18:11:15,625 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-16 18:11:15,625 INFO L87 Difference]: Start difference. First operand 74 states and 105 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2025-03-16 18:11:15,675 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:15,676 INFO L93 Difference]: Finished difference Result 103 states and 147 transitions. [2025-03-16 18:11:15,676 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-16 18:11:15,676 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 42 [2025-03-16 18:11:15,676 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:15,677 INFO L225 Difference]: With dead ends: 103 [2025-03-16 18:11:15,677 INFO L226 Difference]: Without dead ends: 101 [2025-03-16 18:11:15,678 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 42 GetRequests, 38 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2025-03-16 18:11:15,678 INFO L435 NwaCegarLoop]: 30 mSDtfsCounter, 6 mSDsluCounter, 78 mSDsCounter, 0 mSdLazyCounter, 43 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 108 SdHoareTripleChecker+Invalid, 43 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 43 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:15,678 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 108 Invalid, 43 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 43 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 18:11:15,679 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 101 states. [2025-03-16 18:11:15,691 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 101 to 97. [2025-03-16 18:11:15,691 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 97 states, 52 states have (on average 1.3076923076923077) internal successors, (68), 53 states have internal predecessors, (68), 37 states have call successors, (37), 7 states have call predecessors, (37), 7 states have return successors, (36), 36 states have call predecessors, (36), 36 states have call successors, (36) [2025-03-16 18:11:15,692 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 97 states to 97 states and 141 transitions. [2025-03-16 18:11:15,692 INFO L78 Accepts]: Start accepts. Automaton has 97 states and 141 transitions. Word has length 42 [2025-03-16 18:11:15,692 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:15,693 INFO L471 AbstractCegarLoop]: Abstraction has 97 states and 141 transitions. [2025-03-16 18:11:15,693 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2025-03-16 18:11:15,693 INFO L276 IsEmpty]: Start isEmpty. Operand 97 states and 141 transitions. [2025-03-16 18:11:15,693 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2025-03-16 18:11:15,693 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:15,693 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:11:15,699 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2025-03-16 18:11:15,898 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:15,898 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:15,898 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:15,898 INFO L85 PathProgramCache]: Analyzing trace with hash 146539456, now seen corresponding path program 1 times [2025-03-16 18:11:15,898 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:15,898 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [612042417] [2025-03-16 18:11:15,898 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:15,899 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:15,902 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 44 statements into 1 equivalence classes. [2025-03-16 18:11:15,909 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 44 of 44 statements. [2025-03-16 18:11:15,911 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:15,911 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:15,912 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2031110834] [2025-03-16 18:11:15,913 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:15,914 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:15,914 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:15,915 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:11:15,917 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2025-03-16 18:11:15,939 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 44 statements into 1 equivalence classes. [2025-03-16 18:11:15,952 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 44 of 44 statements. [2025-03-16 18:11:15,953 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:15,953 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:15,953 INFO L256 TraceCheckSpWp]: Trace formula consists of 119 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-16 18:11:15,955 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:15,985 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2025-03-16 18:11:15,985 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-16 18:11:15,985 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:15,985 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [612042417] [2025-03-16 18:11:15,985 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:15,985 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2031110834] [2025-03-16 18:11:15,985 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2031110834] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 18:11:15,986 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 18:11:15,986 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-16 18:11:15,986 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1457437848] [2025-03-16 18:11:15,986 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:11:15,986 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-16 18:11:15,986 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:15,986 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-16 18:11:15,987 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-16 18:11:15,987 INFO L87 Difference]: Start difference. First operand 97 states and 141 transitions. Second operand has 5 states, 4 states have (on average 3.5) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2025-03-16 18:11:16,048 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:16,048 INFO L93 Difference]: Finished difference Result 147 states and 230 transitions. [2025-03-16 18:11:16,049 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-16 18:11:16,049 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 3.5) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 44 [2025-03-16 18:11:16,049 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:16,050 INFO L225 Difference]: With dead ends: 147 [2025-03-16 18:11:16,050 INFO L226 Difference]: Without dead ends: 145 [2025-03-16 18:11:16,050 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 44 GetRequests, 40 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2025-03-16 18:11:16,051 INFO L435 NwaCegarLoop]: 33 mSDtfsCounter, 4 mSDsluCounter, 83 mSDsCounter, 0 mSdLazyCounter, 35 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 116 SdHoareTripleChecker+Invalid, 35 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 35 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:16,051 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 116 Invalid, 35 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 35 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 18:11:16,051 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 145 states. [2025-03-16 18:11:16,076 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 145 to 133. [2025-03-16 18:11:16,077 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 133 states, 55 states have (on average 1.290909090909091) internal successors, (71), 64 states have internal predecessors, (71), 69 states have call successors, (69), 8 states have call predecessors, (69), 8 states have return successors, (68), 60 states have call predecessors, (68), 68 states have call successors, (68) [2025-03-16 18:11:16,078 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 133 states to 133 states and 208 transitions. [2025-03-16 18:11:16,079 INFO L78 Accepts]: Start accepts. Automaton has 133 states and 208 transitions. Word has length 44 [2025-03-16 18:11:16,079 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:16,079 INFO L471 AbstractCegarLoop]: Abstraction has 133 states and 208 transitions. [2025-03-16 18:11:16,079 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 3.5) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2025-03-16 18:11:16,079 INFO L276 IsEmpty]: Start isEmpty. Operand 133 states and 208 transitions. [2025-03-16 18:11:16,080 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2025-03-16 18:11:16,081 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:16,081 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:11:16,087 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2025-03-16 18:11:16,282 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:16,282 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:16,282 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:16,282 INFO L85 PathProgramCache]: Analyzing trace with hash 89640629, now seen corresponding path program 1 times [2025-03-16 18:11:16,282 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:16,282 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1006436689] [2025-03-16 18:11:16,282 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:16,282 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:16,286 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 54 statements into 1 equivalence classes. [2025-03-16 18:11:16,297 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 54 of 54 statements. [2025-03-16 18:11:16,297 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:16,297 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:16,297 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [472776049] [2025-03-16 18:11:16,297 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:16,298 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:16,298 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:16,299 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:11:16,301 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2025-03-16 18:11:16,322 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 54 statements into 1 equivalence classes. [2025-03-16 18:11:16,337 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 54 of 54 statements. [2025-03-16 18:11:16,337 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:16,337 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:16,338 INFO L256 TraceCheckSpWp]: Trace formula consists of 148 conjuncts, 51 conjuncts are in the unsatisfiable core [2025-03-16 18:11:16,340 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:16,791 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 14 proven. 5 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2025-03-16 18:11:16,791 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:17,154 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2025-03-16 18:11:17,154 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:17,154 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1006436689] [2025-03-16 18:11:17,154 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:17,154 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [472776049] [2025-03-16 18:11:17,154 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [472776049] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:11:17,154 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:11:17,154 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 11] total 23 [2025-03-16 18:11:17,154 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [173540034] [2025-03-16 18:11:17,154 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:17,154 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2025-03-16 18:11:17,155 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:17,155 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2025-03-16 18:11:17,155 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=77, Invalid=429, Unknown=0, NotChecked=0, Total=506 [2025-03-16 18:11:17,155 INFO L87 Difference]: Start difference. First operand 133 states and 208 transitions. Second operand has 23 states, 21 states have (on average 1.5238095238095237) internal successors, (32), 20 states have internal predecessors, (32), 6 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2025-03-16 18:11:21,697 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 3.62s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2025-03-16 18:11:22,424 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:22,424 INFO L93 Difference]: Finished difference Result 357 states and 579 transitions. [2025-03-16 18:11:22,424 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 32 states. [2025-03-16 18:11:22,425 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 21 states have (on average 1.5238095238095237) internal successors, (32), 20 states have internal predecessors, (32), 6 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) Word has length 54 [2025-03-16 18:11:22,425 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:22,427 INFO L225 Difference]: With dead ends: 357 [2025-03-16 18:11:22,427 INFO L226 Difference]: Without dead ends: 275 [2025-03-16 18:11:22,431 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 129 GetRequests, 85 SyntacticMatches, 0 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 434 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=398, Invalid=1672, Unknown=0, NotChecked=0, Total=2070 [2025-03-16 18:11:22,432 INFO L435 NwaCegarLoop]: 22 mSDtfsCounter, 126 mSDsluCounter, 233 mSDsCounter, 0 mSdLazyCounter, 640 mSolverCounterSat, 126 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 134 SdHoareTripleChecker+Valid, 255 SdHoareTripleChecker+Invalid, 766 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 126 IncrementalHoareTripleChecker+Valid, 640 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.3s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:22,432 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [134 Valid, 255 Invalid, 766 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [126 Valid, 640 Invalid, 0 Unknown, 0 Unchecked, 4.3s Time] [2025-03-16 18:11:22,433 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 275 states. [2025-03-16 18:11:22,485 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 275 to 203. [2025-03-16 18:11:22,486 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 203 states, 98 states have (on average 1.316326530612245) internal successors, (129), 105 states have internal predecessors, (129), 93 states have call successors, (93), 11 states have call predecessors, (93), 11 states have return successors, (92), 86 states have call predecessors, (92), 92 states have call successors, (92) [2025-03-16 18:11:22,487 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 203 states to 203 states and 314 transitions. [2025-03-16 18:11:22,487 INFO L78 Accepts]: Start accepts. Automaton has 203 states and 314 transitions. Word has length 54 [2025-03-16 18:11:22,488 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:22,488 INFO L471 AbstractCegarLoop]: Abstraction has 203 states and 314 transitions. [2025-03-16 18:11:22,488 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 21 states have (on average 1.5238095238095237) internal successors, (32), 20 states have internal predecessors, (32), 6 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2025-03-16 18:11:22,488 INFO L276 IsEmpty]: Start isEmpty. Operand 203 states and 314 transitions. [2025-03-16 18:11:22,489 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2025-03-16 18:11:22,489 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:22,489 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:11:22,495 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2025-03-16 18:11:22,689 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:22,689 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:22,690 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:22,690 INFO L85 PathProgramCache]: Analyzing trace with hash 107169448, now seen corresponding path program 1 times [2025-03-16 18:11:22,690 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:22,690 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [455145418] [2025-03-16 18:11:22,690 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:22,690 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:22,693 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 58 statements into 1 equivalence classes. [2025-03-16 18:11:22,703 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 58 of 58 statements. [2025-03-16 18:11:22,703 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:22,703 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:22,704 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [124067136] [2025-03-16 18:11:22,704 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:22,704 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:22,704 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:22,706 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:11:22,707 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2025-03-16 18:11:22,731 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 58 statements into 1 equivalence classes. [2025-03-16 18:11:22,749 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 58 of 58 statements. [2025-03-16 18:11:22,749 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:22,749 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:22,750 INFO L256 TraceCheckSpWp]: Trace formula consists of 174 conjuncts, 49 conjuncts are in the unsatisfiable core [2025-03-16 18:11:22,752 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:23,114 INFO L134 CoverageAnalysis]: Checked inductivity of 67 backedges. 16 proven. 21 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2025-03-16 18:11:23,114 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:23,245 INFO L134 CoverageAnalysis]: Checked inductivity of 67 backedges. 18 proven. 8 refuted. 0 times theorem prover too weak. 41 trivial. 0 not checked. [2025-03-16 18:11:23,245 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:23,245 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [455145418] [2025-03-16 18:11:23,245 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:23,245 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [124067136] [2025-03-16 18:11:23,246 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [124067136] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:11:23,246 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:11:23,246 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 8] total 22 [2025-03-16 18:11:23,246 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [961004986] [2025-03-16 18:11:23,246 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:23,246 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2025-03-16 18:11:23,246 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:23,247 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2025-03-16 18:11:23,247 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=67, Invalid=395, Unknown=0, NotChecked=0, Total=462 [2025-03-16 18:11:23,247 INFO L87 Difference]: Start difference. First operand 203 states and 314 transitions. Second operand has 22 states, 22 states have (on average 2.0) internal successors, (44), 19 states have internal predecessors, (44), 6 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2025-03-16 18:11:24,454 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:24,454 INFO L93 Difference]: Finished difference Result 254 states and 393 transitions. [2025-03-16 18:11:24,454 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2025-03-16 18:11:24,454 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 22 states have (on average 2.0) internal successors, (44), 19 states have internal predecessors, (44), 6 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) Word has length 58 [2025-03-16 18:11:24,455 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:24,457 INFO L225 Difference]: With dead ends: 254 [2025-03-16 18:11:24,457 INFO L226 Difference]: Without dead ends: 252 [2025-03-16 18:11:24,458 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 135 GetRequests, 103 SyntacticMatches, 0 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 194 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=190, Invalid=932, Unknown=0, NotChecked=0, Total=1122 [2025-03-16 18:11:24,458 INFO L435 NwaCegarLoop]: 38 mSDtfsCounter, 95 mSDsluCounter, 287 mSDsCounter, 0 mSdLazyCounter, 563 mSolverCounterSat, 103 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 97 SdHoareTripleChecker+Valid, 325 SdHoareTripleChecker+Invalid, 666 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 103 IncrementalHoareTripleChecker+Valid, 563 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:24,459 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [97 Valid, 325 Invalid, 666 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [103 Valid, 563 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2025-03-16 18:11:24,460 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 252 states. [2025-03-16 18:11:24,538 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 252 to 211. [2025-03-16 18:11:24,538 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 211 states, 104 states have (on average 1.2980769230769231) internal successors, (135), 111 states have internal predecessors, (135), 93 states have call successors, (93), 13 states have call predecessors, (93), 13 states have return successors, (92), 86 states have call predecessors, (92), 92 states have call successors, (92) [2025-03-16 18:11:24,540 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 211 states to 211 states and 320 transitions. [2025-03-16 18:11:24,540 INFO L78 Accepts]: Start accepts. Automaton has 211 states and 320 transitions. Word has length 58 [2025-03-16 18:11:24,540 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:24,540 INFO L471 AbstractCegarLoop]: Abstraction has 211 states and 320 transitions. [2025-03-16 18:11:24,540 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 22 states have (on average 2.0) internal successors, (44), 19 states have internal predecessors, (44), 6 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2025-03-16 18:11:24,541 INFO L276 IsEmpty]: Start isEmpty. Operand 211 states and 320 transitions. [2025-03-16 18:11:24,541 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 66 [2025-03-16 18:11:24,541 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:24,541 INFO L218 NwaCegarLoop]: trace histogram [8, 7, 7, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:11:24,547 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2025-03-16 18:11:24,746 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2025-03-16 18:11:24,746 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:24,746 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:24,746 INFO L85 PathProgramCache]: Analyzing trace with hash 2061499091, now seen corresponding path program 1 times [2025-03-16 18:11:24,746 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:24,746 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [571900535] [2025-03-16 18:11:24,746 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:24,746 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:24,749 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 65 statements into 1 equivalence classes. [2025-03-16 18:11:24,759 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 65 of 65 statements. [2025-03-16 18:11:24,760 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:24,761 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:24,761 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [341333885] [2025-03-16 18:11:24,762 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:24,762 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:24,762 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:24,763 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:11:24,765 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2025-03-16 18:11:24,784 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 65 statements into 1 equivalence classes. [2025-03-16 18:11:24,798 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 65 of 65 statements. [2025-03-16 18:11:24,798 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:24,798 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:24,800 INFO L256 TraceCheckSpWp]: Trace formula consists of 160 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-03-16 18:11:24,802 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:24,845 INFO L134 CoverageAnalysis]: Checked inductivity of 126 backedges. 14 proven. 4 refuted. 0 times theorem prover too weak. 108 trivial. 0 not checked. [2025-03-16 18:11:24,845 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:24,896 INFO L134 CoverageAnalysis]: Checked inductivity of 126 backedges. 14 proven. 0 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2025-03-16 18:11:24,897 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:24,897 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [571900535] [2025-03-16 18:11:24,897 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:24,898 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [341333885] [2025-03-16 18:11:24,898 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [341333885] provided 1 perfect and 1 imperfect interpolant sequences [2025-03-16 18:11:24,898 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-16 18:11:24,898 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2025-03-16 18:11:24,898 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1622936342] [2025-03-16 18:11:24,898 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:11:24,898 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-16 18:11:24,898 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:24,899 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-16 18:11:24,899 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2025-03-16 18:11:24,899 INFO L87 Difference]: Start difference. First operand 211 states and 320 transitions. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2025-03-16 18:11:24,985 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:24,986 INFO L93 Difference]: Finished difference Result 217 states and 325 transitions. [2025-03-16 18:11:24,986 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-16 18:11:24,986 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) Word has length 65 [2025-03-16 18:11:24,986 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:24,988 INFO L225 Difference]: With dead ends: 217 [2025-03-16 18:11:24,988 INFO L226 Difference]: Without dead ends: 215 [2025-03-16 18:11:24,988 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 129 GetRequests, 121 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2025-03-16 18:11:24,988 INFO L435 NwaCegarLoop]: 33 mSDtfsCounter, 4 mSDsluCounter, 79 mSDsCounter, 0 mSdLazyCounter, 32 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 112 SdHoareTripleChecker+Invalid, 32 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 32 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:24,988 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 112 Invalid, 32 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 18:11:24,989 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 215 states. [2025-03-16 18:11:25,041 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 215 to 215. [2025-03-16 18:11:25,041 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 215 states, 107 states have (on average 1.2897196261682242) internal successors, (138), 114 states have internal predecessors, (138), 93 states have call successors, (93), 14 states have call predecessors, (93), 14 states have return successors, (92), 86 states have call predecessors, (92), 92 states have call successors, (92) [2025-03-16 18:11:25,043 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 215 states to 215 states and 323 transitions. [2025-03-16 18:11:25,044 INFO L78 Accepts]: Start accepts. Automaton has 215 states and 323 transitions. Word has length 65 [2025-03-16 18:11:25,044 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:25,044 INFO L471 AbstractCegarLoop]: Abstraction has 215 states and 323 transitions. [2025-03-16 18:11:25,045 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2025-03-16 18:11:25,045 INFO L276 IsEmpty]: Start isEmpty. Operand 215 states and 323 transitions. [2025-03-16 18:11:25,045 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 64 [2025-03-16 18:11:25,045 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:25,045 INFO L218 NwaCegarLoop]: trace histogram [6, 5, 5, 4, 4, 4, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:11:25,051 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2025-03-16 18:11:25,246 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:25,246 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:25,246 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:25,246 INFO L85 PathProgramCache]: Analyzing trace with hash 1341574078, now seen corresponding path program 2 times [2025-03-16 18:11:25,246 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:25,246 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [513687340] [2025-03-16 18:11:25,246 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:11:25,246 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:25,249 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 63 statements into 2 equivalence classes. [2025-03-16 18:11:25,261 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 63 of 63 statements. [2025-03-16 18:11:25,261 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:11:25,261 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:25,263 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1560322705] [2025-03-16 18:11:25,263 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:11:25,264 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:25,264 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:25,265 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:11:25,279 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2025-03-16 18:11:25,298 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 63 statements into 2 equivalence classes. [2025-03-16 18:11:25,315 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 63 of 63 statements. [2025-03-16 18:11:25,315 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:11:25,315 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:25,317 INFO L256 TraceCheckSpWp]: Trace formula consists of 183 conjuncts, 65 conjuncts are in the unsatisfiable core [2025-03-16 18:11:25,318 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:25,799 INFO L134 CoverageAnalysis]: Checked inductivity of 86 backedges. 18 proven. 25 refuted. 0 times theorem prover too weak. 43 trivial. 0 not checked. [2025-03-16 18:11:25,800 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:26,250 INFO L134 CoverageAnalysis]: Checked inductivity of 86 backedges. 15 proven. 19 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2025-03-16 18:11:26,250 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:26,250 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [513687340] [2025-03-16 18:11:26,250 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:26,250 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1560322705] [2025-03-16 18:11:26,250 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1560322705] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:11:26,250 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:11:26,250 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 15] total 31 [2025-03-16 18:11:26,250 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1006121309] [2025-03-16 18:11:26,250 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:26,251 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 31 states [2025-03-16 18:11:26,251 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:26,251 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2025-03-16 18:11:26,251 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=139, Invalid=791, Unknown=0, NotChecked=0, Total=930 [2025-03-16 18:11:26,251 INFO L87 Difference]: Start difference. First operand 215 states and 323 transitions. Second operand has 31 states, 29 states have (on average 1.5517241379310345) internal successors, (45), 27 states have internal predecessors, (45), 8 states have call successors, (17), 3 states have call predecessors, (17), 3 states have return successors, (16), 8 states have call predecessors, (16), 8 states have call successors, (16) [2025-03-16 18:11:29,360 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:29,361 INFO L93 Difference]: Finished difference Result 399 states and 591 transitions. [2025-03-16 18:11:29,361 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 39 states. [2025-03-16 18:11:29,361 INFO L78 Accepts]: Start accepts. Automaton has has 31 states, 29 states have (on average 1.5517241379310345) internal successors, (45), 27 states have internal predecessors, (45), 8 states have call successors, (17), 3 states have call predecessors, (17), 3 states have return successors, (16), 8 states have call predecessors, (16), 8 states have call successors, (16) Word has length 63 [2025-03-16 18:11:29,361 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:29,363 INFO L225 Difference]: With dead ends: 399 [2025-03-16 18:11:29,363 INFO L226 Difference]: Without dead ends: 334 [2025-03-16 18:11:29,364 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 153 GetRequests, 95 SyntacticMatches, 0 SemanticMatches, 58 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 780 ImplicationChecksByTransitivity, 2.0s TimeCoverageRelationStatistics Valid=678, Invalid=2862, Unknown=0, NotChecked=0, Total=3540 [2025-03-16 18:11:29,364 INFO L435 NwaCegarLoop]: 27 mSDtfsCounter, 144 mSDsluCounter, 359 mSDsCounter, 0 mSdLazyCounter, 939 mSolverCounterSat, 177 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 144 SdHoareTripleChecker+Valid, 386 SdHoareTripleChecker+Invalid, 1116 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 177 IncrementalHoareTripleChecker+Valid, 939 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.5s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:29,365 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [144 Valid, 386 Invalid, 1116 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [177 Valid, 939 Invalid, 0 Unknown, 0 Unchecked, 1.5s Time] [2025-03-16 18:11:29,365 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 334 states. [2025-03-16 18:11:29,462 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 334 to 287. [2025-03-16 18:11:29,463 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 287 states, 144 states have (on average 1.2708333333333333) internal successors, (183), 155 states have internal predecessors, (183), 121 states have call successors, (121), 21 states have call predecessors, (121), 21 states have return successors, (120), 110 states have call predecessors, (120), 120 states have call successors, (120) [2025-03-16 18:11:29,464 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 287 states to 287 states and 424 transitions. [2025-03-16 18:11:29,465 INFO L78 Accepts]: Start accepts. Automaton has 287 states and 424 transitions. Word has length 63 [2025-03-16 18:11:29,465 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:29,465 INFO L471 AbstractCegarLoop]: Abstraction has 287 states and 424 transitions. [2025-03-16 18:11:29,465 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 31 states, 29 states have (on average 1.5517241379310345) internal successors, (45), 27 states have internal predecessors, (45), 8 states have call successors, (17), 3 states have call predecessors, (17), 3 states have return successors, (16), 8 states have call predecessors, (16), 8 states have call successors, (16) [2025-03-16 18:11:29,465 INFO L276 IsEmpty]: Start isEmpty. Operand 287 states and 424 transitions. [2025-03-16 18:11:29,465 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 79 [2025-03-16 18:11:29,466 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:29,466 INFO L218 NwaCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:11:29,474 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2025-03-16 18:11:29,670 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2025-03-16 18:11:29,670 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:29,670 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:29,670 INFO L85 PathProgramCache]: Analyzing trace with hash 408526629, now seen corresponding path program 1 times [2025-03-16 18:11:29,670 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:29,670 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [168016960] [2025-03-16 18:11:29,671 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:29,671 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:29,675 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 78 statements into 1 equivalence classes. [2025-03-16 18:11:29,685 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 78 of 78 statements. [2025-03-16 18:11:29,685 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:29,685 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:29,685 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1156171832] [2025-03-16 18:11:29,685 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:29,685 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:29,685 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:29,689 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:11:29,690 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2025-03-16 18:11:29,711 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 78 statements into 1 equivalence classes. [2025-03-16 18:11:29,731 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 78 of 78 statements. [2025-03-16 18:11:29,731 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:29,731 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:29,732 INFO L256 TraceCheckSpWp]: Trace formula consists of 207 conjuncts, 70 conjuncts are in the unsatisfiable core [2025-03-16 18:11:29,734 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:30,290 INFO L134 CoverageAnalysis]: Checked inductivity of 164 backedges. 36 proven. 22 refuted. 0 times theorem prover too weak. 106 trivial. 0 not checked. [2025-03-16 18:11:30,291 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:31,052 INFO L134 CoverageAnalysis]: Checked inductivity of 164 backedges. 30 proven. 19 refuted. 0 times theorem prover too weak. 115 trivial. 0 not checked. [2025-03-16 18:11:31,052 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:31,052 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [168016960] [2025-03-16 18:11:31,052 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:31,052 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1156171832] [2025-03-16 18:11:31,052 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1156171832] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:11:31,052 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:11:31,052 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 17] total 35 [2025-03-16 18:11:31,052 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [247368077] [2025-03-16 18:11:31,052 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:31,053 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 35 states [2025-03-16 18:11:31,053 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:31,053 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 35 interpolants. [2025-03-16 18:11:31,053 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=154, Invalid=1036, Unknown=0, NotChecked=0, Total=1190 [2025-03-16 18:11:31,053 INFO L87 Difference]: Start difference. First operand 287 states and 424 transitions. Second operand has 35 states, 31 states have (on average 1.4516129032258065) internal successors, (45), 33 states have internal predecessors, (45), 10 states have call successors, (23), 3 states have call predecessors, (23), 3 states have return successors, (22), 8 states have call predecessors, (22), 8 states have call successors, (22) [2025-03-16 18:11:50,624 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:50,624 INFO L93 Difference]: Finished difference Result 519 states and 820 transitions. [2025-03-16 18:11:50,625 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 93 states. [2025-03-16 18:11:50,625 INFO L78 Accepts]: Start accepts. Automaton has has 35 states, 31 states have (on average 1.4516129032258065) internal successors, (45), 33 states have internal predecessors, (45), 10 states have call successors, (23), 3 states have call predecessors, (23), 3 states have return successors, (22), 8 states have call predecessors, (22), 8 states have call successors, (22) Word has length 78 [2025-03-16 18:11:50,625 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:50,628 INFO L225 Difference]: With dead ends: 519 [2025-03-16 18:11:50,629 INFO L226 Difference]: Without dead ends: 511 [2025-03-16 18:11:50,632 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 237 GetRequests, 121 SyntacticMatches, 0 SemanticMatches, 116 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4138 ImplicationChecksByTransitivity, 16.5s TimeCoverageRelationStatistics Valid=2405, Invalid=11401, Unknown=0, NotChecked=0, Total=13806 [2025-03-16 18:11:50,632 INFO L435 NwaCegarLoop]: 50 mSDtfsCounter, 199 mSDsluCounter, 699 mSDsCounter, 0 mSdLazyCounter, 1955 mSolverCounterSat, 289 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 199 SdHoareTripleChecker+Valid, 749 SdHoareTripleChecker+Invalid, 2244 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 289 IncrementalHoareTripleChecker+Valid, 1955 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.3s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:50,632 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [199 Valid, 749 Invalid, 2244 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [289 Valid, 1955 Invalid, 0 Unknown, 0 Unchecked, 3.3s Time] [2025-03-16 18:11:50,633 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 511 states. [2025-03-16 18:11:50,880 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 511 to 394. [2025-03-16 18:11:50,880 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 394 states, 192 states have (on average 1.3125) internal successors, (252), 206 states have internal predecessors, (252), 177 states have call successors, (177), 24 states have call predecessors, (177), 24 states have return successors, (176), 163 states have call predecessors, (176), 176 states have call successors, (176) [2025-03-16 18:11:50,882 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 394 states to 394 states and 605 transitions. [2025-03-16 18:11:50,883 INFO L78 Accepts]: Start accepts. Automaton has 394 states and 605 transitions. Word has length 78 [2025-03-16 18:11:50,883 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:50,883 INFO L471 AbstractCegarLoop]: Abstraction has 394 states and 605 transitions. [2025-03-16 18:11:50,883 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 35 states, 31 states have (on average 1.4516129032258065) internal successors, (45), 33 states have internal predecessors, (45), 10 states have call successors, (23), 3 states have call predecessors, (23), 3 states have return successors, (22), 8 states have call predecessors, (22), 8 states have call successors, (22) [2025-03-16 18:11:50,883 INFO L276 IsEmpty]: Start isEmpty. Operand 394 states and 605 transitions. [2025-03-16 18:11:50,884 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 84 [2025-03-16 18:11:50,884 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:50,884 INFO L218 NwaCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:11:50,891 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2025-03-16 18:11:51,085 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2025-03-16 18:11:51,085 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:51,085 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:51,085 INFO L85 PathProgramCache]: Analyzing trace with hash -1408173133, now seen corresponding path program 2 times [2025-03-16 18:11:51,085 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:51,085 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [400112509] [2025-03-16 18:11:51,086 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:11:51,086 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:51,089 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 83 statements into 2 equivalence classes. [2025-03-16 18:11:51,101 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 83 of 83 statements. [2025-03-16 18:11:51,101 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:11:51,101 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:51,245 INFO L134 CoverageAnalysis]: Checked inductivity of 177 backedges. 28 proven. 11 refuted. 0 times theorem prover too weak. 138 trivial. 0 not checked. [2025-03-16 18:11:51,245 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:51,245 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [400112509] [2025-03-16 18:11:51,245 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [400112509] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:11:51,245 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [80037049] [2025-03-16 18:11:51,245 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:11:51,245 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:51,245 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:51,247 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:11:51,249 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2025-03-16 18:11:51,274 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 83 statements into 2 equivalence classes. [2025-03-16 18:11:51,309 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 83 of 83 statements. [2025-03-16 18:11:51,309 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:11:51,309 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:51,310 INFO L256 TraceCheckSpWp]: Trace formula consists of 230 conjuncts, 10 conjuncts are in the unsatisfiable core [2025-03-16 18:11:51,312 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:51,361 INFO L134 CoverageAnalysis]: Checked inductivity of 177 backedges. 28 proven. 11 refuted. 0 times theorem prover too weak. 138 trivial. 0 not checked. [2025-03-16 18:11:51,362 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:51,446 INFO L134 CoverageAnalysis]: Checked inductivity of 177 backedges. 28 proven. 11 refuted. 0 times theorem prover too weak. 138 trivial. 0 not checked. [2025-03-16 18:11:51,446 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [80037049] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:11:51,446 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 18:11:51,446 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10, 10] total 13 [2025-03-16 18:11:51,446 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [124314665] [2025-03-16 18:11:51,446 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:51,446 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2025-03-16 18:11:51,447 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:51,447 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2025-03-16 18:11:51,447 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=129, Unknown=0, NotChecked=0, Total=156 [2025-03-16 18:11:51,448 INFO L87 Difference]: Start difference. First operand 394 states and 605 transitions. Second operand has 13 states, 13 states have (on average 2.5384615384615383) internal successors, (33), 13 states have internal predecessors, (33), 4 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) [2025-03-16 18:11:51,950 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:51,950 INFO L93 Difference]: Finished difference Result 651 states and 988 transitions. [2025-03-16 18:11:51,950 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2025-03-16 18:11:51,951 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 2.5384615384615383) internal successors, (33), 13 states have internal predecessors, (33), 4 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) Word has length 83 [2025-03-16 18:11:51,951 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:51,953 INFO L225 Difference]: With dead ends: 651 [2025-03-16 18:11:51,953 INFO L226 Difference]: Without dead ends: 411 [2025-03-16 18:11:51,954 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 199 GetRequests, 162 SyntacticMatches, 8 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 164 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=214, Invalid=716, Unknown=0, NotChecked=0, Total=930 [2025-03-16 18:11:51,954 INFO L435 NwaCegarLoop]: 45 mSDtfsCounter, 65 mSDsluCounter, 276 mSDsCounter, 0 mSdLazyCounter, 290 mSolverCounterSat, 91 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 69 SdHoareTripleChecker+Valid, 321 SdHoareTripleChecker+Invalid, 381 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 91 IncrementalHoareTripleChecker+Valid, 290 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:51,954 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [69 Valid, 321 Invalid, 381 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [91 Valid, 290 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-16 18:11:51,955 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 411 states. [2025-03-16 18:11:52,149 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 411 to 306. [2025-03-16 18:11:52,150 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 306 states, 163 states have (on average 1.2822085889570551) internal successors, (209), 165 states have internal predecessors, (209), 119 states have call successors, (119), 23 states have call predecessors, (119), 23 states have return successors, (118), 117 states have call predecessors, (118), 118 states have call successors, (118) [2025-03-16 18:11:52,151 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 306 states to 306 states and 446 transitions. [2025-03-16 18:11:52,152 INFO L78 Accepts]: Start accepts. Automaton has 306 states and 446 transitions. Word has length 83 [2025-03-16 18:11:52,152 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:52,152 INFO L471 AbstractCegarLoop]: Abstraction has 306 states and 446 transitions. [2025-03-16 18:11:52,152 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 2.5384615384615383) internal successors, (33), 13 states have internal predecessors, (33), 4 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) [2025-03-16 18:11:52,152 INFO L276 IsEmpty]: Start isEmpty. Operand 306 states and 446 transitions. [2025-03-16 18:11:52,153 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 97 [2025-03-16 18:11:52,153 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:52,153 INFO L218 NwaCegarLoop]: trace histogram [13, 12, 12, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:11:52,159 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2025-03-16 18:11:52,354 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2025-03-16 18:11:52,354 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:52,354 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:52,354 INFO L85 PathProgramCache]: Analyzing trace with hash -807522155, now seen corresponding path program 2 times [2025-03-16 18:11:52,354 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:52,354 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [239366610] [2025-03-16 18:11:52,354 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:11:52,354 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:52,359 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 96 statements into 2 equivalence classes. [2025-03-16 18:11:52,374 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 96 of 96 statements. [2025-03-16 18:11:52,375 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:11:52,375 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:52,378 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1151147932] [2025-03-16 18:11:52,378 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:11:52,379 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:52,379 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:52,381 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:11:52,383 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2025-03-16 18:11:52,409 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 96 statements into 2 equivalence classes. [2025-03-16 18:11:52,432 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 96 of 96 statements. [2025-03-16 18:11:52,432 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:11:52,432 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:52,433 INFO L256 TraceCheckSpWp]: Trace formula consists of 230 conjuncts, 47 conjuncts are in the unsatisfiable core [2025-03-16 18:11:52,435 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:52,838 INFO L134 CoverageAnalysis]: Checked inductivity of 329 backedges. 24 proven. 17 refuted. 0 times theorem prover too weak. 288 trivial. 0 not checked. [2025-03-16 18:11:52,838 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:53,233 INFO L134 CoverageAnalysis]: Checked inductivity of 329 backedges. 24 proven. 17 refuted. 0 times theorem prover too weak. 288 trivial. 0 not checked. [2025-03-16 18:11:53,234 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:53,234 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [239366610] [2025-03-16 18:11:53,234 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:53,234 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1151147932] [2025-03-16 18:11:53,234 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1151147932] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:11:53,234 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:11:53,234 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 22 [2025-03-16 18:11:53,234 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1665297581] [2025-03-16 18:11:53,234 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:53,234 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2025-03-16 18:11:53,234 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:53,235 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2025-03-16 18:11:53,235 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=66, Invalid=396, Unknown=0, NotChecked=0, Total=462 [2025-03-16 18:11:53,235 INFO L87 Difference]: Start difference. First operand 306 states and 446 transitions. Second operand has 22 states, 20 states have (on average 1.55) internal successors, (31), 21 states have internal predecessors, (31), 9 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (28), 7 states have call predecessors, (28), 7 states have call successors, (28) [2025-03-16 18:11:57,615 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:57,615 INFO L93 Difference]: Finished difference Result 510 states and 789 transitions. [2025-03-16 18:11:57,616 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 60 states. [2025-03-16 18:11:57,616 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 20 states have (on average 1.55) internal successors, (31), 21 states have internal predecessors, (31), 9 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (28), 7 states have call predecessors, (28), 7 states have call successors, (28) Word has length 96 [2025-03-16 18:11:57,616 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:57,618 INFO L225 Difference]: With dead ends: 510 [2025-03-16 18:11:57,618 INFO L226 Difference]: Without dead ends: 502 [2025-03-16 18:11:57,619 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 239 GetRequests, 168 SyntacticMatches, 2 SemanticMatches, 69 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1406 ImplicationChecksByTransitivity, 3.1s TimeCoverageRelationStatistics Valid=867, Invalid=4103, Unknown=0, NotChecked=0, Total=4970 [2025-03-16 18:11:57,620 INFO L435 NwaCegarLoop]: 72 mSDtfsCounter, 123 mSDsluCounter, 731 mSDsCounter, 0 mSdLazyCounter, 1176 mSolverCounterSat, 186 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 127 SdHoareTripleChecker+Valid, 803 SdHoareTripleChecker+Invalid, 1362 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 186 IncrementalHoareTripleChecker+Valid, 1176 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.2s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:57,620 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [127 Valid, 803 Invalid, 1362 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [186 Valid, 1176 Invalid, 0 Unknown, 0 Unchecked, 1.2s Time] [2025-03-16 18:11:57,621 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 502 states. [2025-03-16 18:11:57,811 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 502 to 342. [2025-03-16 18:11:57,811 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 342 states, 174 states have (on average 1.3045977011494252) internal successors, (227), 176 states have internal predecessors, (227), 143 states have call successors, (143), 24 states have call predecessors, (143), 24 states have return successors, (142), 141 states have call predecessors, (142), 142 states have call successors, (142) [2025-03-16 18:11:57,812 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 342 states to 342 states and 512 transitions. [2025-03-16 18:11:57,813 INFO L78 Accepts]: Start accepts. Automaton has 342 states and 512 transitions. Word has length 96 [2025-03-16 18:11:57,813 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:57,813 INFO L471 AbstractCegarLoop]: Abstraction has 342 states and 512 transitions. [2025-03-16 18:11:57,813 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 20 states have (on average 1.55) internal successors, (31), 21 states have internal predecessors, (31), 9 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (28), 7 states have call predecessors, (28), 7 states have call successors, (28) [2025-03-16 18:11:57,813 INFO L276 IsEmpty]: Start isEmpty. Operand 342 states and 512 transitions. [2025-03-16 18:11:57,814 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 99 [2025-03-16 18:11:57,814 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:57,814 INFO L218 NwaCegarLoop]: trace histogram [13, 12, 12, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:11:57,820 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2025-03-16 18:11:58,015 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2025-03-16 18:11:58,015 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:58,015 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:58,015 INFO L85 PathProgramCache]: Analyzing trace with hash 1069370314, now seen corresponding path program 3 times [2025-03-16 18:11:58,015 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:58,015 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1933101515] [2025-03-16 18:11:58,016 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 18:11:58,016 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:58,021 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 98 statements into 11 equivalence classes. [2025-03-16 18:11:58,045 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 11 check-sat command(s) and asserted 98 of 98 statements. [2025-03-16 18:11:58,046 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 11 check-sat command(s) [2025-03-16 18:11:58,046 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:58,047 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [214584234] [2025-03-16 18:11:58,047 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 18:11:58,047 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:58,047 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:58,049 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:11:58,051 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2025-03-16 18:11:58,075 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 98 statements into 11 equivalence classes. [2025-03-16 18:11:58,092 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) and asserted 62 of 98 statements. [2025-03-16 18:11:58,092 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2025-03-16 18:11:58,092 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:58,093 INFO L256 TraceCheckSpWp]: Trace formula consists of 167 conjuncts, 61 conjuncts are in the unsatisfiable core [2025-03-16 18:11:58,095 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:58,764 INFO L134 CoverageAnalysis]: Checked inductivity of 332 backedges. 55 proven. 27 refuted. 0 times theorem prover too weak. 250 trivial. 0 not checked. [2025-03-16 18:11:58,764 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:59,261 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:59,261 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1933101515] [2025-03-16 18:11:59,261 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:59,261 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [214584234] [2025-03-16 18:11:59,261 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [214584234] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:11:59,261 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-16 18:11:59,261 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19] total 19 [2025-03-16 18:11:59,261 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1878887761] [2025-03-16 18:11:59,261 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:59,261 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2025-03-16 18:11:59,261 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:59,262 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2025-03-16 18:11:59,262 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=126, Invalid=686, Unknown=0, NotChecked=0, Total=812 [2025-03-16 18:11:59,262 INFO L87 Difference]: Start difference. First operand 342 states and 512 transitions. Second operand has 19 states, 18 states have (on average 1.6111111111111112) internal successors, (29), 16 states have internal predecessors, (29), 4 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (13), 5 states have call predecessors, (13), 3 states have call successors, (13) [2025-03-16 18:12:00,049 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:12:00,049 INFO L93 Difference]: Finished difference Result 428 states and 632 transitions. [2025-03-16 18:12:00,050 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2025-03-16 18:12:00,050 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 18 states have (on average 1.6111111111111112) internal successors, (29), 16 states have internal predecessors, (29), 4 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (13), 5 states have call predecessors, (13), 3 states have call successors, (13) Word has length 98 [2025-03-16 18:12:00,050 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:12:00,052 INFO L225 Difference]: With dead ends: 428 [2025-03-16 18:12:00,052 INFO L226 Difference]: Without dead ends: 421 [2025-03-16 18:12:00,052 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 138 GetRequests, 103 SyntacticMatches, 0 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 273 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=227, Invalid=1105, Unknown=0, NotChecked=0, Total=1332 [2025-03-16 18:12:00,053 INFO L435 NwaCegarLoop]: 26 mSDtfsCounter, 45 mSDsluCounter, 178 mSDsCounter, 0 mSdLazyCounter, 615 mSolverCounterSat, 36 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 57 SdHoareTripleChecker+Valid, 204 SdHoareTripleChecker+Invalid, 651 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 36 IncrementalHoareTripleChecker+Valid, 615 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-03-16 18:12:00,053 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [57 Valid, 204 Invalid, 651 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [36 Valid, 615 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-03-16 18:12:00,053 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 421 states. [2025-03-16 18:12:00,296 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 421 to 410. [2025-03-16 18:12:00,296 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 410 states, 209 states have (on average 1.30622009569378) internal successors, (273), 211 states have internal predecessors, (273), 171 states have call successors, (171), 29 states have call predecessors, (171), 29 states have return successors, (170), 169 states have call predecessors, (170), 170 states have call successors, (170) [2025-03-16 18:12:00,298 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 410 states to 410 states and 614 transitions. [2025-03-16 18:12:00,298 INFO L78 Accepts]: Start accepts. Automaton has 410 states and 614 transitions. Word has length 98 [2025-03-16 18:12:00,298 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:12:00,298 INFO L471 AbstractCegarLoop]: Abstraction has 410 states and 614 transitions. [2025-03-16 18:12:00,298 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 18 states have (on average 1.6111111111111112) internal successors, (29), 16 states have internal predecessors, (29), 4 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (13), 5 states have call predecessors, (13), 3 states have call successors, (13) [2025-03-16 18:12:00,299 INFO L276 IsEmpty]: Start isEmpty. Operand 410 states and 614 transitions. [2025-03-16 18:12:00,300 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 102 [2025-03-16 18:12:00,300 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:12:00,300 INFO L218 NwaCegarLoop]: trace histogram [13, 12, 12, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:12:00,306 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2025-03-16 18:12:00,500 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable15,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:12:00,500 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:12:00,501 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:12:00,501 INFO L85 PathProgramCache]: Analyzing trace with hash 311264781, now seen corresponding path program 4 times [2025-03-16 18:12:00,501 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:12:00,501 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [176508946] [2025-03-16 18:12:00,501 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-16 18:12:00,501 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:12:00,504 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 101 statements into 2 equivalence classes. [2025-03-16 18:12:00,516 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 101 of 101 statements. [2025-03-16 18:12:00,516 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-03-16 18:12:00,516 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:12:00,517 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [845472445] [2025-03-16 18:12:00,517 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-16 18:12:00,517 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:12:00,517 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:12:00,519 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:12:00,520 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2025-03-16 18:12:00,542 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 101 statements into 2 equivalence classes. [2025-03-16 18:12:00,566 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 97 of 101 statements. [2025-03-16 18:12:00,566 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-03-16 18:12:00,566 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:12:00,571 INFO L256 TraceCheckSpWp]: Trace formula consists of 222 conjuncts, 75 conjuncts are in the unsatisfiable core [2025-03-16 18:12:00,572 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:12:01,196 INFO L134 CoverageAnalysis]: Checked inductivity of 338 backedges. 30 proven. 29 refuted. 0 times theorem prover too weak. 279 trivial. 0 not checked. [2025-03-16 18:12:01,196 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:12:01,752 INFO L134 CoverageAnalysis]: Checked inductivity of 338 backedges. 24 proven. 26 refuted. 0 times theorem prover too weak. 288 trivial. 0 not checked. [2025-03-16 18:12:01,752 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:12:01,752 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [176508946] [2025-03-16 18:12:01,752 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:12:01,752 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [845472445] [2025-03-16 18:12:01,752 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [845472445] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:12:01,752 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:12:01,752 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 16] total 33 [2025-03-16 18:12:01,753 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [70158266] [2025-03-16 18:12:01,753 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:12:01,753 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 33 states [2025-03-16 18:12:01,753 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:12:01,754 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2025-03-16 18:12:01,754 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=137, Invalid=919, Unknown=0, NotChecked=0, Total=1056 [2025-03-16 18:12:01,754 INFO L87 Difference]: Start difference. First operand 410 states and 614 transitions. Second operand has 33 states, 31 states have (on average 1.4838709677419355) internal successors, (46), 30 states have internal predecessors, (46), 10 states have call successors, (31), 3 states have call predecessors, (31), 2 states have return successors, (30), 8 states have call predecessors, (30), 8 states have call successors, (30) [2025-03-16 18:12:11,857 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:12:11,857 INFO L93 Difference]: Finished difference Result 676 states and 1057 transitions. [2025-03-16 18:12:11,857 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 93 states. [2025-03-16 18:12:11,857 INFO L78 Accepts]: Start accepts. Automaton has has 33 states, 31 states have (on average 1.4838709677419355) internal successors, (46), 30 states have internal predecessors, (46), 10 states have call successors, (31), 3 states have call predecessors, (31), 2 states have return successors, (30), 8 states have call predecessors, (30), 8 states have call successors, (30) Word has length 101 [2025-03-16 18:12:11,858 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:12:11,860 INFO L225 Difference]: With dead ends: 676 [2025-03-16 18:12:11,860 INFO L226 Difference]: Without dead ends: 668 [2025-03-16 18:12:11,863 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 284 GetRequests, 169 SyntacticMatches, 0 SemanticMatches, 115 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4029 ImplicationChecksByTransitivity, 7.2s TimeCoverageRelationStatistics Valid=2038, Invalid=11534, Unknown=0, NotChecked=0, Total=13572 [2025-03-16 18:12:11,863 INFO L435 NwaCegarLoop]: 37 mSDtfsCounter, 293 mSDsluCounter, 614 mSDsCounter, 0 mSdLazyCounter, 1471 mSolverCounterSat, 434 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 293 SdHoareTripleChecker+Valid, 651 SdHoareTripleChecker+Invalid, 1905 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 434 IncrementalHoareTripleChecker+Valid, 1471 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.8s IncrementalHoareTripleChecker+Time [2025-03-16 18:12:11,863 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [293 Valid, 651 Invalid, 1905 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [434 Valid, 1471 Invalid, 0 Unknown, 0 Unchecked, 2.8s Time] [2025-03-16 18:12:11,864 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 668 states. [2025-03-16 18:12:12,280 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 668 to 515. [2025-03-16 18:12:12,281 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 515 states, 255 states have (on average 1.3254901960784313) internal successors, (338), 257 states have internal predecessors, (338), 227 states have call successors, (227), 32 states have call predecessors, (227), 32 states have return successors, (226), 225 states have call predecessors, (226), 226 states have call successors, (226) [2025-03-16 18:12:12,283 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 515 states to 515 states and 791 transitions. [2025-03-16 18:12:12,283 INFO L78 Accepts]: Start accepts. Automaton has 515 states and 791 transitions. Word has length 101 [2025-03-16 18:12:12,284 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:12:12,284 INFO L471 AbstractCegarLoop]: Abstraction has 515 states and 791 transitions. [2025-03-16 18:12:12,284 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 33 states, 31 states have (on average 1.4838709677419355) internal successors, (46), 30 states have internal predecessors, (46), 10 states have call successors, (31), 3 states have call predecessors, (31), 2 states have return successors, (30), 8 states have call predecessors, (30), 8 states have call successors, (30) [2025-03-16 18:12:12,284 INFO L276 IsEmpty]: Start isEmpty. Operand 515 states and 791 transitions. [2025-03-16 18:12:12,285 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 105 [2025-03-16 18:12:12,285 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:12:12,285 INFO L218 NwaCegarLoop]: trace histogram [13, 12, 12, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:12:12,292 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2025-03-16 18:12:12,490 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2025-03-16 18:12:12,490 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:12:12,490 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:12:12,490 INFO L85 PathProgramCache]: Analyzing trace with hash -1999255606, now seen corresponding path program 5 times [2025-03-16 18:12:12,490 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:12:12,490 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [498416502] [2025-03-16 18:12:12,490 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-03-16 18:12:12,490 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:12:12,494 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 104 statements into 8 equivalence classes. [2025-03-16 18:12:12,509 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 8 check-sat command(s) and asserted 104 of 104 statements. [2025-03-16 18:12:12,509 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 8 check-sat command(s) [2025-03-16 18:12:12,509 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:12:12,509 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [823984396] [2025-03-16 18:12:12,509 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-03-16 18:12:12,509 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:12:12,509 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:12:12,512 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:12:12,513 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2025-03-16 18:12:12,536 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 104 statements into 8 equivalence classes. [2025-03-16 18:12:12,570 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 8 check-sat command(s) and asserted 104 of 104 statements. [2025-03-16 18:12:12,570 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 8 check-sat command(s) [2025-03-16 18:12:12,570 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:12:12,572 INFO L256 TraceCheckSpWp]: Trace formula consists of 271 conjuncts, 77 conjuncts are in the unsatisfiable core [2025-03-16 18:12:12,574 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:12:14,036 INFO L134 CoverageAnalysis]: Checked inductivity of 347 backedges. 42 proven. 98 refuted. 0 times theorem prover too weak. 207 trivial. 0 not checked. [2025-03-16 18:12:14,036 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:12:14,585 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:12:14,585 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [498416502] [2025-03-16 18:12:14,585 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:12:14,585 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [823984396] [2025-03-16 18:12:14,585 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [823984396] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:12:14,585 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-16 18:12:14,585 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [23] total 23 [2025-03-16 18:12:14,585 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [764694639] [2025-03-16 18:12:14,585 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-16 18:12:14,585 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2025-03-16 18:12:14,585 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:12:14,586 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2025-03-16 18:12:14,586 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=93, Invalid=777, Unknown=0, NotChecked=0, Total=870 [2025-03-16 18:12:14,586 INFO L87 Difference]: Start difference. First operand 515 states and 791 transitions. Second operand has 23 states, 19 states have (on average 1.6842105263157894) internal successors, (32), 19 states have internal predecessors, (32), 8 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (16), 6 states have call predecessors, (16), 7 states have call successors, (16) [2025-03-16 18:12:16,665 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:12:16,665 INFO L93 Difference]: Finished difference Result 605 states and 919 transitions. [2025-03-16 18:12:16,665 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2025-03-16 18:12:16,665 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 19 states have (on average 1.6842105263157894) internal successors, (32), 19 states have internal predecessors, (32), 8 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (16), 6 states have call predecessors, (16), 7 states have call successors, (16) Word has length 104 [2025-03-16 18:12:16,666 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:12:16,668 INFO L225 Difference]: With dead ends: 605 [2025-03-16 18:12:16,668 INFO L226 Difference]: Without dead ends: 598 [2025-03-16 18:12:16,668 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 154 GetRequests, 116 SyntacticMatches, 0 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 237 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=167, Invalid=1393, Unknown=0, NotChecked=0, Total=1560 [2025-03-16 18:12:16,669 INFO L435 NwaCegarLoop]: 46 mSDtfsCounter, 64 mSDsluCounter, 635 mSDsCounter, 0 mSdLazyCounter, 1164 mSolverCounterSat, 50 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 86 SdHoareTripleChecker+Valid, 681 SdHoareTripleChecker+Invalid, 1214 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 50 IncrementalHoareTripleChecker+Valid, 1164 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.2s IncrementalHoareTripleChecker+Time [2025-03-16 18:12:16,669 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [86 Valid, 681 Invalid, 1214 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [50 Valid, 1164 Invalid, 0 Unknown, 0 Unchecked, 1.2s Time] [2025-03-16 18:12:16,669 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 598 states. [2025-03-16 18:12:17,194 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 598 to 566. [2025-03-16 18:12:17,195 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 566 states, 278 states have (on average 1.3237410071942446) internal successors, (368), 280 states have internal predecessors, (368), 251 states have call successors, (251), 36 states have call predecessors, (251), 36 states have return successors, (250), 249 states have call predecessors, (250), 250 states have call successors, (250) [2025-03-16 18:12:17,197 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 566 states to 566 states and 869 transitions. [2025-03-16 18:12:17,198 INFO L78 Accepts]: Start accepts. Automaton has 566 states and 869 transitions. Word has length 104 [2025-03-16 18:12:17,198 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:12:17,198 INFO L471 AbstractCegarLoop]: Abstraction has 566 states and 869 transitions. [2025-03-16 18:12:17,198 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 19 states have (on average 1.6842105263157894) internal successors, (32), 19 states have internal predecessors, (32), 8 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (16), 6 states have call predecessors, (16), 7 states have call successors, (16) [2025-03-16 18:12:17,198 INFO L276 IsEmpty]: Start isEmpty. Operand 566 states and 869 transitions. [2025-03-16 18:12:17,199 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 108 [2025-03-16 18:12:17,200 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:12:17,200 INFO L218 NwaCegarLoop]: trace histogram [14, 13, 13, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:12:17,206 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Ended with exit code 0 [2025-03-16 18:12:17,400 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2025-03-16 18:12:17,400 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:12:17,400 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:12:17,401 INFO L85 PathProgramCache]: Analyzing trace with hash 985041779, now seen corresponding path program 1 times [2025-03-16 18:12:17,401 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:12:17,401 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1047453080] [2025-03-16 18:12:17,401 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:12:17,401 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:12:17,405 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 107 statements into 1 equivalence classes. [2025-03-16 18:12:17,417 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 107 of 107 statements. [2025-03-16 18:12:17,417 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:12:17,417 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:12:17,417 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2143856231] [2025-03-16 18:12:17,418 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:12:17,418 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:12:17,418 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:12:17,420 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:12:17,421 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2025-03-16 18:12:17,446 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 107 statements into 1 equivalence classes. [2025-03-16 18:12:17,474 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 107 of 107 statements. [2025-03-16 18:12:17,475 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:12:17,475 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:12:17,476 INFO L256 TraceCheckSpWp]: Trace formula consists of 270 conjuncts, 73 conjuncts are in the unsatisfiable core [2025-03-16 18:12:17,478 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:12:18,141 INFO L134 CoverageAnalysis]: Checked inductivity of 398 backedges. 32 proven. 39 refuted. 0 times theorem prover too weak. 327 trivial. 0 not checked. [2025-03-16 18:12:18,141 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:12:18,956 INFO L134 CoverageAnalysis]: Checked inductivity of 398 backedges. 26 proven. 36 refuted. 0 times theorem prover too weak. 336 trivial. 0 not checked. [2025-03-16 18:12:18,957 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:12:18,957 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1047453080] [2025-03-16 18:12:18,957 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:12:18,957 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2143856231] [2025-03-16 18:12:18,957 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2143856231] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:12:18,957 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:12:18,957 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 17] total 35 [2025-03-16 18:12:18,957 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1380138858] [2025-03-16 18:12:18,957 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:12:18,957 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 35 states [2025-03-16 18:12:18,957 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:12:18,958 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 35 interpolants. [2025-03-16 18:12:18,958 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=177, Invalid=1013, Unknown=0, NotChecked=0, Total=1190 [2025-03-16 18:12:18,958 INFO L87 Difference]: Start difference. First operand 566 states and 869 transitions. Second operand has 35 states, 35 states have (on average 1.3714285714285714) internal successors, (48), 32 states have internal predecessors, (48), 10 states have call successors, (33), 3 states have call predecessors, (33), 2 states have return successors, (32), 10 states have call predecessors, (32), 10 states have call successors, (32) [2025-03-16 18:12:42,769 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:12:42,769 INFO L93 Difference]: Finished difference Result 840 states and 1308 transitions. [2025-03-16 18:12:42,770 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 80 states. [2025-03-16 18:12:42,770 INFO L78 Accepts]: Start accepts. Automaton has has 35 states, 35 states have (on average 1.3714285714285714) internal successors, (48), 32 states have internal predecessors, (48), 10 states have call successors, (33), 3 states have call predecessors, (33), 2 states have return successors, (32), 10 states have call predecessors, (32), 10 states have call successors, (32) Word has length 107 [2025-03-16 18:12:42,770 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:12:42,774 INFO L225 Difference]: With dead ends: 840 [2025-03-16 18:12:42,774 INFO L226 Difference]: Without dead ends: 838 [2025-03-16 18:12:42,776 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 284 GetRequests, 179 SyntacticMatches, 0 SemanticMatches, 105 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3212 ImplicationChecksByTransitivity, 20.1s TimeCoverageRelationStatistics Valid=2276, Invalid=9066, Unknown=0, NotChecked=0, Total=11342 [2025-03-16 18:12:42,776 INFO L435 NwaCegarLoop]: 43 mSDtfsCounter, 237 mSDsluCounter, 572 mSDsCounter, 0 mSdLazyCounter, 1557 mSolverCounterSat, 314 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 237 SdHoareTripleChecker+Valid, 615 SdHoareTripleChecker+Invalid, 1871 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 314 IncrementalHoareTripleChecker+Valid, 1557 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.5s IncrementalHoareTripleChecker+Time [2025-03-16 18:12:42,776 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [237 Valid, 615 Invalid, 1871 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [314 Valid, 1557 Invalid, 0 Unknown, 0 Unchecked, 3.5s Time] [2025-03-16 18:12:42,777 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 838 states. [2025-03-16 18:12:43,560 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 838 to 731. [2025-03-16 18:12:43,561 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 731 states, 355 states have (on average 1.3380281690140845) internal successors, (475), 358 states have internal predecessors, (475), 333 states have call successors, (333), 42 states have call predecessors, (333), 42 states have return successors, (332), 330 states have call predecessors, (332), 332 states have call successors, (332) [2025-03-16 18:12:43,563 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 731 states to 731 states and 1140 transitions. [2025-03-16 18:12:43,564 INFO L78 Accepts]: Start accepts. Automaton has 731 states and 1140 transitions. Word has length 107 [2025-03-16 18:12:43,564 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:12:43,564 INFO L471 AbstractCegarLoop]: Abstraction has 731 states and 1140 transitions. [2025-03-16 18:12:43,564 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 35 states, 35 states have (on average 1.3714285714285714) internal successors, (48), 32 states have internal predecessors, (48), 10 states have call successors, (33), 3 states have call predecessors, (33), 2 states have return successors, (32), 10 states have call predecessors, (32), 10 states have call successors, (32) [2025-03-16 18:12:43,564 INFO L276 IsEmpty]: Start isEmpty. Operand 731 states and 1140 transitions. [2025-03-16 18:12:43,565 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 113 [2025-03-16 18:12:43,565 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:12:43,566 INFO L218 NwaCegarLoop]: trace histogram [15, 14, 14, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:12:43,572 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Ended with exit code 0 [2025-03-16 18:12:43,770 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:12:43,770 INFO L396 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:12:43,770 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:12:43,770 INFO L85 PathProgramCache]: Analyzing trace with hash 448458035, now seen corresponding path program 2 times [2025-03-16 18:12:43,770 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:12:43,770 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1833707924] [2025-03-16 18:12:43,770 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:12:43,770 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:12:43,774 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 112 statements into 2 equivalence classes. [2025-03-16 18:12:43,784 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 112 of 112 statements. [2025-03-16 18:12:43,784 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:12:43,784 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:12:43,785 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1341437679] [2025-03-16 18:12:43,785 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:12:43,785 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:12:43,785 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:12:43,793 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:12:43,796 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2025-03-16 18:12:43,822 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 112 statements into 2 equivalence classes. [2025-03-16 18:12:43,844 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 112 of 112 statements. [2025-03-16 18:12:43,844 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:12:43,844 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:12:43,845 INFO L256 TraceCheckSpWp]: Trace formula consists of 279 conjuncts, 44 conjuncts are in the unsatisfiable core [2025-03-16 18:12:43,847 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:12:44,038 INFO L134 CoverageAnalysis]: Checked inductivity of 455 backedges. 40 proven. 36 refuted. 0 times theorem prover too weak. 379 trivial. 0 not checked. [2025-03-16 18:12:44,039 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:12:44,203 INFO L134 CoverageAnalysis]: Checked inductivity of 455 backedges. 48 proven. 12 refuted. 0 times theorem prover too weak. 395 trivial. 0 not checked. [2025-03-16 18:12:44,204 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:12:44,204 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1833707924] [2025-03-16 18:12:44,204 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:12:44,204 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1341437679] [2025-03-16 18:12:44,204 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1341437679] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:12:44,204 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:12:44,204 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 9] total 25 [2025-03-16 18:12:44,204 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1130212173] [2025-03-16 18:12:44,204 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:12:44,204 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2025-03-16 18:12:44,204 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:12:44,204 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2025-03-16 18:12:44,205 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=82, Invalid=518, Unknown=0, NotChecked=0, Total=600 [2025-03-16 18:12:44,205 INFO L87 Difference]: Start difference. First operand 731 states and 1140 transitions. Second operand has 25 states, 23 states have (on average 1.9130434782608696) internal successors, (44), 22 states have internal predecessors, (44), 9 states have call successors, (35), 3 states have call predecessors, (35), 2 states have return successors, (34), 9 states have call predecessors, (34), 9 states have call successors, (34) [2025-03-16 18:12:46,571 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:12:46,572 INFO L93 Difference]: Finished difference Result 1131 states and 1830 transitions. [2025-03-16 18:12:46,572 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 42 states. [2025-03-16 18:12:46,572 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 23 states have (on average 1.9130434782608696) internal successors, (44), 22 states have internal predecessors, (44), 9 states have call successors, (35), 3 states have call predecessors, (35), 2 states have return successors, (34), 9 states have call predecessors, (34), 9 states have call successors, (34) Word has length 112 [2025-03-16 18:12:46,572 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:12:46,577 INFO L225 Difference]: With dead ends: 1131 [2025-03-16 18:12:46,577 INFO L226 Difference]: Without dead ends: 1129 [2025-03-16 18:12:46,578 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 270 GetRequests, 211 SyntacticMatches, 0 SemanticMatches, 59 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 816 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=685, Invalid=2975, Unknown=0, NotChecked=0, Total=3660 [2025-03-16 18:12:46,578 INFO L435 NwaCegarLoop]: 49 mSDtfsCounter, 114 mSDsluCounter, 499 mSDsCounter, 0 mSdLazyCounter, 763 mSolverCounterSat, 133 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 118 SdHoareTripleChecker+Valid, 548 SdHoareTripleChecker+Invalid, 896 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 133 IncrementalHoareTripleChecker+Valid, 763 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2025-03-16 18:12:46,578 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [118 Valid, 548 Invalid, 896 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [133 Valid, 763 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2025-03-16 18:12:46,579 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1129 states. [2025-03-16 18:12:47,817 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1129 to 1006. [2025-03-16 18:12:47,819 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1006 states, 450 states have (on average 1.3955555555555557) internal successors, (628), 452 states have internal predecessors, (628), 507 states have call successors, (507), 48 states have call predecessors, (507), 48 states have return successors, (506), 505 states have call predecessors, (506), 506 states have call successors, (506) [2025-03-16 18:12:47,822 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1006 states to 1006 states and 1641 transitions. [2025-03-16 18:12:47,823 INFO L78 Accepts]: Start accepts. Automaton has 1006 states and 1641 transitions. Word has length 112 [2025-03-16 18:12:47,824 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:12:47,824 INFO L471 AbstractCegarLoop]: Abstraction has 1006 states and 1641 transitions. [2025-03-16 18:12:47,824 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 25 states, 23 states have (on average 1.9130434782608696) internal successors, (44), 22 states have internal predecessors, (44), 9 states have call successors, (35), 3 states have call predecessors, (35), 2 states have return successors, (34), 9 states have call predecessors, (34), 9 states have call successors, (34) [2025-03-16 18:12:47,824 INFO L276 IsEmpty]: Start isEmpty. Operand 1006 states and 1641 transitions. [2025-03-16 18:12:47,826 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 120 [2025-03-16 18:12:47,826 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:12:47,826 INFO L218 NwaCegarLoop]: trace histogram [17, 16, 16, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:12:47,832 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Ended with exit code 0 [2025-03-16 18:12:48,026 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,19 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:12:48,026 INFO L396 AbstractCegarLoop]: === Iteration 21 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:12:48,027 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:12:48,027 INFO L85 PathProgramCache]: Analyzing trace with hash 419380243, now seen corresponding path program 6 times [2025-03-16 18:12:48,027 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:12:48,027 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2082130577] [2025-03-16 18:12:48,027 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-03-16 18:12:48,027 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:12:48,031 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 119 statements into 12 equivalence classes. [2025-03-16 18:12:48,047 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 8 check-sat command(s) and asserted 89 of 119 statements. [2025-03-16 18:12:48,047 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 8 check-sat command(s) [2025-03-16 18:12:48,047 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:12:48,168 INFO L134 CoverageAnalysis]: Checked inductivity of 571 backedges. 35 proven. 32 refuted. 0 times theorem prover too weak. 504 trivial. 0 not checked. [2025-03-16 18:12:48,169 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:12:48,169 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2082130577] [2025-03-16 18:12:48,169 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2082130577] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:12:48,169 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [753007474] [2025-03-16 18:12:48,169 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-03-16 18:12:48,169 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:12:48,169 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:12:48,171 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:12:48,172 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Waiting until timeout for monitored process [2025-03-16 18:12:48,196 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 119 statements into 12 equivalence classes. [2025-03-16 18:12:48,219 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 8 check-sat command(s) and asserted 89 of 119 statements. [2025-03-16 18:12:48,220 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 8 check-sat command(s) [2025-03-16 18:12:48,220 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:12:48,221 INFO L256 TraceCheckSpWp]: Trace formula consists of 222 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-03-16 18:12:48,222 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:12:48,306 INFO L134 CoverageAnalysis]: Checked inductivity of 571 backedges. 35 proven. 32 refuted. 0 times theorem prover too weak. 504 trivial. 0 not checked. [2025-03-16 18:12:48,306 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:12:48,403 INFO L134 CoverageAnalysis]: Checked inductivity of 571 backedges. 35 proven. 32 refuted. 0 times theorem prover too weak. 504 trivial. 0 not checked. [2025-03-16 18:12:48,403 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [753007474] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:12:48,403 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 18:12:48,403 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10, 10] total 14 [2025-03-16 18:12:48,403 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1060505557] [2025-03-16 18:12:48,403 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 18:12:48,403 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2025-03-16 18:12:48,403 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:12:48,403 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2025-03-16 18:12:48,404 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=31, Invalid=151, Unknown=0, NotChecked=0, Total=182 [2025-03-16 18:12:48,404 INFO L87 Difference]: Start difference. First operand 1006 states and 1641 transitions. Second operand has 14 states, 14 states have (on average 2.357142857142857) internal successors, (33), 14 states have internal predecessors, (33), 7 states have call successors, (25), 2 states have call predecessors, (25), 1 states have return successors, (24), 6 states have call predecessors, (24), 6 states have call successors, (24) [2025-03-16 18:12:49,918 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:12:49,918 INFO L93 Difference]: Finished difference Result 1795 states and 2967 transitions. [2025-03-16 18:12:49,918 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-03-16 18:12:49,918 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 2.357142857142857) internal successors, (33), 14 states have internal predecessors, (33), 7 states have call successors, (25), 2 states have call predecessors, (25), 1 states have return successors, (24), 6 states have call predecessors, (24), 6 states have call successors, (24) Word has length 119 [2025-03-16 18:12:49,918 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:12:49,924 INFO L225 Difference]: With dead ends: 1795 [2025-03-16 18:12:49,924 INFO L226 Difference]: Without dead ends: 1147 [2025-03-16 18:12:49,925 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 253 GetRequests, 226 SyntacticMatches, 8 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 54 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=81, Invalid=339, Unknown=0, NotChecked=0, Total=420 [2025-03-16 18:12:49,926 INFO L435 NwaCegarLoop]: 46 mSDtfsCounter, 15 mSDsluCounter, 254 mSDsCounter, 0 mSdLazyCounter, 191 mSolverCounterSat, 32 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 300 SdHoareTripleChecker+Invalid, 223 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 32 IncrementalHoareTripleChecker+Valid, 191 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:12:49,926 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 300 Invalid, 223 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [32 Valid, 191 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 18:12:49,927 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1147 states. [2025-03-16 18:12:51,281 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1147 to 1052. [2025-03-16 18:12:51,282 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1052 states, 470 states have (on average 1.3829787234042554) internal successors, (650), 493 states have internal predecessors, (650), 533 states have call successors, (533), 48 states have call predecessors, (533), 48 states have return successors, (532), 510 states have call predecessors, (532), 532 states have call successors, (532) [2025-03-16 18:12:51,286 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1052 states to 1052 states and 1715 transitions. [2025-03-16 18:12:51,288 INFO L78 Accepts]: Start accepts. Automaton has 1052 states and 1715 transitions. Word has length 119 [2025-03-16 18:12:51,288 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:12:51,288 INFO L471 AbstractCegarLoop]: Abstraction has 1052 states and 1715 transitions. [2025-03-16 18:12:51,288 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 2.357142857142857) internal successors, (33), 14 states have internal predecessors, (33), 7 states have call successors, (25), 2 states have call predecessors, (25), 1 states have return successors, (24), 6 states have call predecessors, (24), 6 states have call successors, (24) [2025-03-16 18:12:51,288 INFO L276 IsEmpty]: Start isEmpty. Operand 1052 states and 1715 transitions. [2025-03-16 18:12:51,290 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 123 [2025-03-16 18:12:51,290 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:12:51,290 INFO L218 NwaCegarLoop]: trace histogram [17, 16, 16, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:12:51,296 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Forceful destruction successful, exit code 0 [2025-03-16 18:12:51,490 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable20,20 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:12:51,490 INFO L396 AbstractCegarLoop]: === Iteration 22 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:12:51,491 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:12:51,491 INFO L85 PathProgramCache]: Analyzing trace with hash -932847920, now seen corresponding path program 7 times [2025-03-16 18:12:51,491 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:12:51,491 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1441019186] [2025-03-16 18:12:51,491 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-03-16 18:12:51,491 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:12:51,496 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 122 statements into 1 equivalence classes. [2025-03-16 18:12:51,512 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 122 of 122 statements. [2025-03-16 18:12:51,512 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:12:51,512 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:12:51,513 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [743145826] [2025-03-16 18:12:51,513 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-03-16 18:12:51,513 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:12:51,514 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:12:51,515 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:12:51,517 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Waiting until timeout for monitored process [2025-03-16 18:12:51,544 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 122 statements into 1 equivalence classes. [2025-03-16 18:12:51,574 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 122 of 122 statements. [2025-03-16 18:12:51,574 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:12:51,574 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:12:51,576 INFO L256 TraceCheckSpWp]: Trace formula consists of 294 conjuncts, 84 conjuncts are in the unsatisfiable core [2025-03-16 18:12:51,578 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:12:52,296 INFO L134 CoverageAnalysis]: Checked inductivity of 577 backedges. 76 proven. 51 refuted. 0 times theorem prover too weak. 450 trivial. 0 not checked. [2025-03-16 18:12:52,297 INFO L312 TraceCheckSpWp]: Computing backward predicates...