./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound50.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_valuebound50.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 05dbf98a57cbdf117305bcdd9c3dde8d1b2284b890adec5d1f5924f0e5e4bbbb --- Real Ultimate output --- This is Ultimate 0.3.0-?-8fc3dc6-m [2025-03-16 18:11:22,255 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-16 18:11:22,300 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:22,303 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-16 18:11:22,304 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-16 18:11:22,324 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-16 18:11:22,324 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-16 18:11:22,324 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-16 18:11:22,325 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-16 18:11:22,326 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-16 18:11:22,326 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-03-16 18:11:22,326 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-03-16 18:11:22,327 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-16 18:11:22,327 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-16 18:11:22,327 INFO L153 SettingsManager]: * Use SBE=true [2025-03-16 18:11:22,327 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-16 18:11:22,327 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-03-16 18:11:22,327 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-16 18:11:22,328 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-16 18:11:22,328 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-16 18:11:22,328 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-16 18:11:22,328 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-03-16 18:11:22,328 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-03-16 18:11:22,328 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-03-16 18:11:22,328 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-16 18:11:22,328 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-16 18:11:22,328 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-16 18:11:22,328 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-16 18:11:22,328 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-16 18:11:22,328 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-16 18:11:22,329 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-03-16 18:11:22,329 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-03-16 18:11:22,329 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-16 18:11:22,329 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-16 18:11:22,329 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-03-16 18:11:22,329 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-03-16 18:11:22,329 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-03-16 18:11:22,329 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-16 18:11:22,329 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-03-16 18:11:22,329 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-03-16 18:11:22,330 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-03-16 18:11:22,330 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-03-16 18:11:22,330 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-03-16 18:11:22,330 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 -> 05dbf98a57cbdf117305bcdd9c3dde8d1b2284b890adec5d1f5924f0e5e4bbbb [2025-03-16 18:11:22,569 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-16 18:11:22,577 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-16 18:11:22,578 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-16 18:11:22,579 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-16 18:11:22,579 INFO L274 PluginConnector]: CDTParser initialized [2025-03-16 18:11:22,580 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound50.c [2025-03-16 18:11:23,697 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/055599ddb/a7e97af5dbdf4f73bd53e8eaf9f38b16/FLAGcbef6a4da [2025-03-16 18:11:23,936 INFO L384 CDTParser]: Found 1 translation units. [2025-03-16 18:11:23,937 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound50.c [2025-03-16 18:11:23,944 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/055599ddb/a7e97af5dbdf4f73bd53e8eaf9f38b16/FLAGcbef6a4da [2025-03-16 18:11:23,957 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/055599ddb/a7e97af5dbdf4f73bd53e8eaf9f38b16 [2025-03-16 18:11:23,959 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-16 18:11:23,960 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-16 18:11:23,962 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-16 18:11:23,962 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-16 18:11:23,965 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-16 18:11:23,966 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.03 06:11:23" (1/1) ... [2025-03-16 18:11:23,966 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@1a9577a4 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:23, skipping insertion in model container [2025-03-16 18:11:23,968 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.03 06:11:23" (1/1) ... [2025-03-16 18:11:23,979 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-16 18:11:24,083 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_valuebound50.c[490,503] [2025-03-16 18:11:24,095 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-16 18:11:24,100 INFO L200 MainTranslator]: Completed pre-run [2025-03-16 18:11:24,107 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_valuebound50.c[490,503] [2025-03-16 18:11:24,113 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-16 18:11:24,124 INFO L204 MainTranslator]: Completed translation [2025-03-16 18:11:24,125 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:24 WrapperNode [2025-03-16 18:11:24,126 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-16 18:11:24,127 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-16 18:11:24,127 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-16 18:11:24,127 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-16 18:11:24,131 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:24" (1/1) ... [2025-03-16 18:11:24,135 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:24" (1/1) ... [2025-03-16 18:11:24,144 INFO L138 Inliner]: procedures = 14, calls = 16, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 74 [2025-03-16 18:11:24,145 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-16 18:11:24,145 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-16 18:11:24,145 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-16 18:11:24,145 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-16 18:11:24,150 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:24" (1/1) ... [2025-03-16 18:11:24,150 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:24" (1/1) ... [2025-03-16 18:11:24,151 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:24" (1/1) ... [2025-03-16 18:11:24,158 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:24,158 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:24" (1/1) ... [2025-03-16 18:11:24,158 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:24" (1/1) ... [2025-03-16 18:11:24,160 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:24" (1/1) ... [2025-03-16 18:11:24,160 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:24" (1/1) ... [2025-03-16 18:11:24,161 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:24" (1/1) ... [2025-03-16 18:11:24,161 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:24" (1/1) ... [2025-03-16 18:11:24,163 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-16 18:11:24,163 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-16 18:11:24,163 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-16 18:11:24,163 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-16 18:11:24,164 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:24" (1/1) ... [2025-03-16 18:11:24,168 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-16 18:11:24,175 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:24,186 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:24,188 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:24,202 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-16 18:11:24,202 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2025-03-16 18:11:24,202 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2025-03-16 18:11:24,202 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-03-16 18:11:24,202 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-16 18:11:24,202 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-16 18:11:24,203 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2025-03-16 18:11:24,203 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2025-03-16 18:11:24,240 INFO L256 CfgBuilder]: Building ICFG [2025-03-16 18:11:24,242 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-16 18:11:24,357 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2025-03-16 18:11:24,357 INFO L307 CfgBuilder]: Performing block encoding [2025-03-16 18:11:24,366 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-16 18:11:24,367 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-16 18:11:24,367 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 16.03 06:11:24 BoogieIcfgContainer [2025-03-16 18:11:24,367 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-16 18:11:24,369 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-03-16 18:11:24,369 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-03-16 18:11:24,372 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-03-16 18:11:24,373 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 16.03 06:11:23" (1/3) ... [2025-03-16 18:11:24,373 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@61998fdf and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.03 06:11:24, skipping insertion in model container [2025-03-16 18:11:24,374 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:24" (2/3) ... [2025-03-16 18:11:24,374 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@61998fdf and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.03 06:11:24, skipping insertion in model container [2025-03-16 18:11:24,374 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 16.03 06:11:24" (3/3) ... [2025-03-16 18:11:24,375 INFO L128 eAbstractionObserver]: Analyzing ICFG egcd3-ll_valuebound50.c [2025-03-16 18:11:24,385 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-03-16 18:11:24,386 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG egcd3-ll_valuebound50.c that has 3 procedures, 30 locations, 1 initial locations, 3 loop locations, and 1 error locations. [2025-03-16 18:11:24,424 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-03-16 18:11:24,434 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;@c412fc6, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-03-16 18:11:24,435 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-03-16 18:11:24,438 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:24,442 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2025-03-16 18:11:24,442 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:24,443 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:24,443 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:24,447 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:24,447 INFO L85 PathProgramCache]: Analyzing trace with hash -1461292294, now seen corresponding path program 1 times [2025-03-16 18:11:24,452 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:24,453 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1906216569] [2025-03-16 18:11:24,453 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:24,455 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:24,511 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 28 statements into 1 equivalence classes. [2025-03-16 18:11:24,547 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 28 of 28 statements. [2025-03-16 18:11:24,548 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:24,548 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:24,755 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:24,756 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:24,756 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1906216569] [2025-03-16 18:11:24,756 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1906216569] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 18:11:24,756 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 18:11:24,757 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2025-03-16 18:11:24,757 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [118143699] [2025-03-16 18:11:24,758 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:11:24,760 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2025-03-16 18:11:24,761 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:24,774 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-03-16 18:11:24,775 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2025-03-16 18:11:24,776 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:24,891 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:24,891 INFO L93 Difference]: Finished difference Result 67 states and 117 transitions. [2025-03-16 18:11:24,892 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-16 18:11:24,893 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:24,894 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:24,897 INFO L225 Difference]: With dead ends: 67 [2025-03-16 18:11:24,897 INFO L226 Difference]: Without dead ends: 36 [2025-03-16 18:11:24,899 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:24,900 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:24,901 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:24,911 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36 states. [2025-03-16 18:11:24,925 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36 to 28. [2025-03-16 18:11:24,926 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:24,928 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28 states to 28 states and 37 transitions. [2025-03-16 18:11:24,930 INFO L78 Accepts]: Start accepts. Automaton has 28 states and 37 transitions. Word has length 28 [2025-03-16 18:11:24,930 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:24,930 INFO L471 AbstractCegarLoop]: Abstraction has 28 states and 37 transitions. [2025-03-16 18:11:24,930 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:24,930 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 37 transitions. [2025-03-16 18:11:24,931 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2025-03-16 18:11:24,931 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:24,932 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:24,932 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2025-03-16 18:11:24,932 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:24,932 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:24,932 INFO L85 PathProgramCache]: Analyzing trace with hash 1979049318, now seen corresponding path program 1 times [2025-03-16 18:11:24,932 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:24,933 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1529554422] [2025-03-16 18:11:24,933 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:24,933 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:24,939 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 29 statements into 1 equivalence classes. [2025-03-16 18:11:24,947 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 29 of 29 statements. [2025-03-16 18:11:24,947 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:24,947 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:24,950 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2005754734] [2025-03-16 18:11:24,950 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:24,950 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:24,950 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:24,952 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:24,954 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:24,984 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 29 statements into 1 equivalence classes. [2025-03-16 18:11:25,001 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 29 of 29 statements. [2025-03-16 18:11:25,001 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:25,001 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:25,003 INFO L256 TraceCheckSpWp]: Trace formula consists of 92 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-03-16 18:11:25,006 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:25,095 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:25,096 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-16 18:11:25,096 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:25,097 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1529554422] [2025-03-16 18:11:25,097 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:25,097 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2005754734] [2025-03-16 18:11:25,097 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2005754734] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 18:11:25,097 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 18:11:25,097 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-16 18:11:25,098 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1733616817] [2025-03-16 18:11:25,098 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:11:25,098 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-16 18:11:25,098 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:25,099 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-16 18:11:25,099 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-16 18:11:25,099 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:25,137 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:25,137 INFO L93 Difference]: Finished difference Result 42 states and 56 transitions. [2025-03-16 18:11:25,138 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-16 18:11:25,138 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:25,138 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:25,139 INFO L225 Difference]: With dead ends: 42 [2025-03-16 18:11:25,139 INFO L226 Difference]: Without dead ends: 40 [2025-03-16 18:11:25,139 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:25,139 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:25,140 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:25,140 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40 states. [2025-03-16 18:11:25,145 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40 to 39. [2025-03-16 18:11:25,145 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:25,147 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 53 transitions. [2025-03-16 18:11:25,147 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 53 transitions. Word has length 29 [2025-03-16 18:11:25,147 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:25,147 INFO L471 AbstractCegarLoop]: Abstraction has 39 states and 53 transitions. [2025-03-16 18:11:25,147 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:25,148 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 53 transitions. [2025-03-16 18:11:25,148 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2025-03-16 18:11:25,148 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:25,148 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:25,154 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2025-03-16 18:11:25,349 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:25,349 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:25,349 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:25,349 INFO L85 PathProgramCache]: Analyzing trace with hash 351925117, now seen corresponding path program 1 times [2025-03-16 18:11:25,349 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:25,350 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1497133708] [2025-03-16 18:11:25,350 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:25,350 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:25,355 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-03-16 18:11:25,367 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-03-16 18:11:25,367 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:25,368 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:25,489 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:25,489 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:25,490 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1497133708] [2025-03-16 18:11:25,490 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1497133708] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:11:25,490 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [938692885] [2025-03-16 18:11:25,490 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:25,490 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:25,490 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:25,492 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:25,493 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:25,514 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-03-16 18:11:25,525 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-03-16 18:11:25,525 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:25,525 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:25,526 INFO L256 TraceCheckSpWp]: Trace formula consists of 102 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-03-16 18:11:25,527 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:25,544 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:25,544 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:25,618 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:25,619 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [938692885] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:11:25,619 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 18:11:25,619 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 9 [2025-03-16 18:11:25,619 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [36897853] [2025-03-16 18:11:25,619 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:25,619 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2025-03-16 18:11:25,620 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:25,620 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2025-03-16 18:11:25,620 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2025-03-16 18:11:25,620 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:25,756 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:25,756 INFO L93 Difference]: Finished difference Result 81 states and 121 transitions. [2025-03-16 18:11:25,757 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-03-16 18:11:25,757 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:25,757 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:25,758 INFO L225 Difference]: With dead ends: 81 [2025-03-16 18:11:25,758 INFO L226 Difference]: Without dead ends: 74 [2025-03-16 18:11:25,758 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:25,759 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:25,759 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:25,759 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 74 states. [2025-03-16 18:11:25,772 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 74 to 53. [2025-03-16 18:11:25,772 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:25,774 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 77 transitions. [2025-03-16 18:11:25,775 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 77 transitions. Word has length 31 [2025-03-16 18:11:25,775 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:25,775 INFO L471 AbstractCegarLoop]: Abstraction has 53 states and 77 transitions. [2025-03-16 18:11:25,775 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:25,775 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 77 transitions. [2025-03-16 18:11:25,776 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2025-03-16 18:11:25,776 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:25,777 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:25,782 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:25,977 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:25,977 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:25,978 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:25,978 INFO L85 PathProgramCache]: Analyzing trace with hash -1940753085, now seen corresponding path program 1 times [2025-03-16 18:11:25,978 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:25,978 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2028426275] [2025-03-16 18:11:25,978 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:25,978 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:25,984 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 32 statements into 1 equivalence classes. [2025-03-16 18:11:25,995 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 32 of 32 statements. [2025-03-16 18:11:25,995 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:25,995 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:25,996 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1726158626] [2025-03-16 18:11:25,996 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:25,996 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:25,996 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:25,998 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:25,999 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:26,025 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 32 statements into 1 equivalence classes. [2025-03-16 18:11:26,039 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 32 of 32 statements. [2025-03-16 18:11:26,039 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:26,039 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:26,040 INFO L256 TraceCheckSpWp]: Trace formula consists of 110 conjuncts, 15 conjuncts are in the unsatisfiable core [2025-03-16 18:11:26,041 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:26,110 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:26,110 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:26,234 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:26,234 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:26,234 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2028426275] [2025-03-16 18:11:26,234 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:26,234 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1726158626] [2025-03-16 18:11:26,234 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1726158626] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:11:26,234 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:11:26,235 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 8 [2025-03-16 18:11:26,235 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1398308700] [2025-03-16 18:11:26,235 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:26,235 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2025-03-16 18:11:26,235 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:26,236 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-03-16 18:11:26,236 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2025-03-16 18:11:26,236 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:26,367 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:26,369 INFO L93 Difference]: Finished difference Result 82 states and 119 transitions. [2025-03-16 18:11:26,370 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-16 18:11:26,370 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:26,370 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:26,371 INFO L225 Difference]: With dead ends: 82 [2025-03-16 18:11:26,371 INFO L226 Difference]: Without dead ends: 80 [2025-03-16 18:11:26,371 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:26,372 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:26,372 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:26,372 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 80 states. [2025-03-16 18:11:26,389 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 80 to 76. [2025-03-16 18:11:26,390 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:26,392 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 76 states to 76 states and 113 transitions. [2025-03-16 18:11:26,394 INFO L78 Accepts]: Start accepts. Automaton has 76 states and 113 transitions. Word has length 32 [2025-03-16 18:11:26,394 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:26,394 INFO L471 AbstractCegarLoop]: Abstraction has 76 states and 113 transitions. [2025-03-16 18:11:26,394 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:26,395 INFO L276 IsEmpty]: Start isEmpty. Operand 76 states and 113 transitions. [2025-03-16 18:11:26,395 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2025-03-16 18:11:26,395 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:26,395 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:26,402 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2025-03-16 18:11:26,596 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:26,596 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:26,596 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:26,596 INFO L85 PathProgramCache]: Analyzing trace with hash -908329914, now seen corresponding path program 2 times [2025-03-16 18:11:26,596 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:26,596 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1458426061] [2025-03-16 18:11:26,597 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:11:26,597 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:26,601 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 35 statements into 2 equivalence classes. [2025-03-16 18:11:26,608 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:26,608 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:11:26,608 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:26,674 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:26,675 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:26,675 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1458426061] [2025-03-16 18:11:26,675 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1458426061] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 18:11:26,675 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 18:11:26,675 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-16 18:11:26,675 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1632549452] [2025-03-16 18:11:26,675 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:11:26,677 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-16 18:11:26,677 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:26,678 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-16 18:11:26,678 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-16 18:11:26,678 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:26,758 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:26,759 INFO L93 Difference]: Finished difference Result 115 states and 177 transitions. [2025-03-16 18:11:26,759 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-16 18:11:26,759 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:26,760 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:26,760 INFO L225 Difference]: With dead ends: 115 [2025-03-16 18:11:26,760 INFO L226 Difference]: Without dead ends: 86 [2025-03-16 18:11:26,761 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:26,761 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:26,761 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:26,762 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 86 states. [2025-03-16 18:11:26,773 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 86 to 57. [2025-03-16 18:11:26,774 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:26,775 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 78 transitions. [2025-03-16 18:11:26,776 INFO L78 Accepts]: Start accepts. Automaton has 57 states and 78 transitions. Word has length 35 [2025-03-16 18:11:26,776 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:26,776 INFO L471 AbstractCegarLoop]: Abstraction has 57 states and 78 transitions. [2025-03-16 18:11:26,776 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:26,777 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 78 transitions. [2025-03-16 18:11:26,778 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2025-03-16 18:11:26,778 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:26,778 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:26,779 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4 [2025-03-16 18:11:26,779 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:26,779 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:26,779 INFO L85 PathProgramCache]: Analyzing trace with hash -1361869309, now seen corresponding path program 1 times [2025-03-16 18:11:26,779 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:26,779 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [636786262] [2025-03-16 18:11:26,780 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:26,780 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:26,785 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 37 statements into 1 equivalence classes. [2025-03-16 18:11:26,796 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 37 of 37 statements. [2025-03-16 18:11:26,798 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:26,798 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:26,799 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1914459376] [2025-03-16 18:11:26,800 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:26,800 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:26,800 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:26,802 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:26,803 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:26,827 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 37 statements into 1 equivalence classes. [2025-03-16 18:11:26,840 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 37 of 37 statements. [2025-03-16 18:11:26,840 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:26,841 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:26,841 INFO L256 TraceCheckSpWp]: Trace formula consists of 119 conjuncts, 21 conjuncts are in the unsatisfiable core [2025-03-16 18:11:26,843 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:26,950 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:26,950 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:26,998 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:26,999 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [636786262] [2025-03-16 18:11:26,999 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:26,999 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1914459376] [2025-03-16 18:11:26,999 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1914459376] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:11:26,999 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-16 18:11:26,999 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2025-03-16 18:11:26,999 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1385223782] [2025-03-16 18:11:26,999 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:26,999 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2025-03-16 18:11:26,999 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:26,999 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2025-03-16 18:11:26,999 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2025-03-16 18:11:27,000 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:27,118 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:27,118 INFO L93 Difference]: Finished difference Result 78 states and 109 transitions. [2025-03-16 18:11:27,119 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2025-03-16 18:11:27,119 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:27,119 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:27,120 INFO L225 Difference]: With dead ends: 78 [2025-03-16 18:11:27,120 INFO L226 Difference]: Without dead ends: 76 [2025-03-16 18:11:27,120 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:27,120 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:27,120 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:27,121 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 76 states. [2025-03-16 18:11:27,131 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 76 to 74. [2025-03-16 18:11:27,134 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:27,135 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 74 states to 74 states and 105 transitions. [2025-03-16 18:11:27,135 INFO L78 Accepts]: Start accepts. Automaton has 74 states and 105 transitions. Word has length 37 [2025-03-16 18:11:27,136 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:27,136 INFO L471 AbstractCegarLoop]: Abstraction has 74 states and 105 transitions. [2025-03-16 18:11:27,136 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:27,136 INFO L276 IsEmpty]: Start isEmpty. Operand 74 states and 105 transitions. [2025-03-16 18:11:27,136 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2025-03-16 18:11:27,136 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:27,136 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:27,143 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:27,337 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:27,337 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:27,337 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:27,338 INFO L85 PathProgramCache]: Analyzing trace with hash -1979591293, now seen corresponding path program 1 times [2025-03-16 18:11:27,338 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:27,338 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [804897281] [2025-03-16 18:11:27,338 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:27,338 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:27,341 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 42 statements into 1 equivalence classes. [2025-03-16 18:11:27,350 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 42 of 42 statements. [2025-03-16 18:11:27,351 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:27,356 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:27,357 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1989575926] [2025-03-16 18:11:27,357 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:27,357 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:27,358 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:27,359 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:27,361 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:27,387 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 42 statements into 1 equivalence classes. [2025-03-16 18:11:27,401 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 42 of 42 statements. [2025-03-16 18:11:27,401 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:27,401 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:27,404 INFO L256 TraceCheckSpWp]: Trace formula consists of 128 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-16 18:11:27,405 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:27,443 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:27,444 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-16 18:11:27,444 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:27,444 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [804897281] [2025-03-16 18:11:27,444 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:27,444 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1989575926] [2025-03-16 18:11:27,445 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1989575926] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 18:11:27,445 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 18:11:27,445 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-16 18:11:27,445 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [331355911] [2025-03-16 18:11:27,445 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:11:27,445 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-16 18:11:27,445 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:27,445 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-16 18:11:27,445 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-16 18:11:27,445 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:27,496 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:27,496 INFO L93 Difference]: Finished difference Result 103 states and 147 transitions. [2025-03-16 18:11:27,496 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-16 18:11:27,497 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:27,497 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:27,498 INFO L225 Difference]: With dead ends: 103 [2025-03-16 18:11:27,498 INFO L226 Difference]: Without dead ends: 101 [2025-03-16 18:11:27,498 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:27,498 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:27,499 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:27,499 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 101 states. [2025-03-16 18:11:27,518 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 101 to 97. [2025-03-16 18:11:27,520 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:27,521 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 97 states to 97 states and 141 transitions. [2025-03-16 18:11:27,522 INFO L78 Accepts]: Start accepts. Automaton has 97 states and 141 transitions. Word has length 42 [2025-03-16 18:11:27,522 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:27,522 INFO L471 AbstractCegarLoop]: Abstraction has 97 states and 141 transitions. [2025-03-16 18:11:27,522 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:27,522 INFO L276 IsEmpty]: Start isEmpty. Operand 97 states and 141 transitions. [2025-03-16 18:11:27,524 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2025-03-16 18:11:27,524 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:27,524 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:27,531 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2025-03-16 18:11:27,724 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:27,724 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:27,725 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:27,725 INFO L85 PathProgramCache]: Analyzing trace with hash 146539456, now seen corresponding path program 1 times [2025-03-16 18:11:27,725 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:27,725 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1671054611] [2025-03-16 18:11:27,725 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:27,725 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:27,728 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 44 statements into 1 equivalence classes. [2025-03-16 18:11:27,734 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 44 of 44 statements. [2025-03-16 18:11:27,734 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:27,734 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:27,734 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [116393835] [2025-03-16 18:11:27,734 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:27,735 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:27,735 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:27,740 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:27,742 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:27,762 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 44 statements into 1 equivalence classes. [2025-03-16 18:11:27,777 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 44 of 44 statements. [2025-03-16 18:11:27,778 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:27,778 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:27,778 INFO L256 TraceCheckSpWp]: Trace formula consists of 119 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-16 18:11:27,779 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:27,811 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:27,811 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-16 18:11:27,811 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:27,811 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1671054611] [2025-03-16 18:11:27,811 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:27,811 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [116393835] [2025-03-16 18:11:27,811 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [116393835] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 18:11:27,811 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 18:11:27,811 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-16 18:11:27,812 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1230040474] [2025-03-16 18:11:27,812 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:11:27,812 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-16 18:11:27,812 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:27,812 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-16 18:11:27,812 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-16 18:11:27,812 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:27,870 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:27,870 INFO L93 Difference]: Finished difference Result 147 states and 230 transitions. [2025-03-16 18:11:27,871 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-16 18:11:27,871 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:27,871 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:27,872 INFO L225 Difference]: With dead ends: 147 [2025-03-16 18:11:27,872 INFO L226 Difference]: Without dead ends: 145 [2025-03-16 18:11:27,873 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:27,873 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:27,873 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:27,874 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 145 states. [2025-03-16 18:11:27,893 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 145 to 133. [2025-03-16 18:11:27,894 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:27,895 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 133 states to 133 states and 208 transitions. [2025-03-16 18:11:27,895 INFO L78 Accepts]: Start accepts. Automaton has 133 states and 208 transitions. Word has length 44 [2025-03-16 18:11:27,895 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:27,896 INFO L471 AbstractCegarLoop]: Abstraction has 133 states and 208 transitions. [2025-03-16 18:11:27,896 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:27,896 INFO L276 IsEmpty]: Start isEmpty. Operand 133 states and 208 transitions. [2025-03-16 18:11:27,896 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2025-03-16 18:11:27,896 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:27,897 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:27,902 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2025-03-16 18:11:28,101 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:28,101 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:28,101 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:28,101 INFO L85 PathProgramCache]: Analyzing trace with hash 89640629, now seen corresponding path program 1 times [2025-03-16 18:11:28,101 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:28,101 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [351486932] [2025-03-16 18:11:28,101 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:28,102 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:28,106 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 54 statements into 1 equivalence classes. [2025-03-16 18:11:28,123 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 54 of 54 statements. [2025-03-16 18:11:28,123 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:28,124 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:28,126 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [829596549] [2025-03-16 18:11:28,126 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:28,126 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:28,126 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:28,128 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:28,130 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:28,156 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 54 statements into 1 equivalence classes. [2025-03-16 18:11:28,173 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 54 of 54 statements. [2025-03-16 18:11:28,173 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:28,174 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:28,175 INFO L256 TraceCheckSpWp]: Trace formula consists of 148 conjuncts, 51 conjuncts are in the unsatisfiable core [2025-03-16 18:11:28,177 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:28,605 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:28,605 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:28,956 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:28,957 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:28,957 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [351486932] [2025-03-16 18:11:28,957 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:28,957 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [829596549] [2025-03-16 18:11:28,957 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [829596549] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:11:28,957 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:11:28,957 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 11] total 23 [2025-03-16 18:11:28,957 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [944178084] [2025-03-16 18:11:28,957 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:28,958 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2025-03-16 18:11:28,958 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:28,959 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2025-03-16 18:11:28,959 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=77, Invalid=429, Unknown=0, NotChecked=0, Total=506 [2025-03-16 18:11:28,959 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:30,790 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:30,791 INFO L93 Difference]: Finished difference Result 357 states and 579 transitions. [2025-03-16 18:11:30,791 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 32 states. [2025-03-16 18:11:30,791 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:30,792 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:30,796 INFO L225 Difference]: With dead ends: 357 [2025-03-16 18:11:30,796 INFO L226 Difference]: Without dead ends: 275 [2025-03-16 18:11:30,798 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 129 GetRequests, 85 SyntacticMatches, 0 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 434 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=398, Invalid=1672, Unknown=0, NotChecked=0, Total=2070 [2025-03-16 18:11:30,798 INFO L435 NwaCegarLoop]: 22 mSDtfsCounter, 126 mSDsluCounter, 233 mSDsCounter, 0 mSdLazyCounter, 640 mSolverCounterSat, 126 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 134 SdHoareTripleChecker+Valid, 255 SdHoareTripleChecker+Invalid, 766 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 126 IncrementalHoareTripleChecker+Valid, 640 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:30,799 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [134 Valid, 255 Invalid, 766 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [126 Valid, 640 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2025-03-16 18:11:30,800 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 275 states. [2025-03-16 18:11:30,851 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 275 to 203. [2025-03-16 18:11:30,851 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:30,853 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 203 states to 203 states and 314 transitions. [2025-03-16 18:11:30,853 INFO L78 Accepts]: Start accepts. Automaton has 203 states and 314 transitions. Word has length 54 [2025-03-16 18:11:30,854 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:30,854 INFO L471 AbstractCegarLoop]: Abstraction has 203 states and 314 transitions. [2025-03-16 18:11:30,854 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:30,854 INFO L276 IsEmpty]: Start isEmpty. Operand 203 states and 314 transitions. [2025-03-16 18:11:30,854 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2025-03-16 18:11:30,855 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:30,855 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:30,861 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:31,055 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:31,056 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:31,056 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:31,056 INFO L85 PathProgramCache]: Analyzing trace with hash 107169448, now seen corresponding path program 1 times [2025-03-16 18:11:31,056 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:31,056 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [183419] [2025-03-16 18:11:31,056 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:31,056 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:31,059 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 58 statements into 1 equivalence classes. [2025-03-16 18:11:31,069 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 58 of 58 statements. [2025-03-16 18:11:31,069 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:31,069 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:31,071 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1683794103] [2025-03-16 18:11:31,071 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:31,071 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:31,071 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:31,073 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:31,074 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:31,095 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 58 statements into 1 equivalence classes. [2025-03-16 18:11:31,113 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 58 of 58 statements. [2025-03-16 18:11:31,114 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:31,114 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:31,115 INFO L256 TraceCheckSpWp]: Trace formula consists of 174 conjuncts, 49 conjuncts are in the unsatisfiable core [2025-03-16 18:11:31,117 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:31,456 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:31,456 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:31,585 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:31,586 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:31,586 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [183419] [2025-03-16 18:11:31,586 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:31,586 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1683794103] [2025-03-16 18:11:31,586 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1683794103] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:11:31,586 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:11:31,586 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 8] total 22 [2025-03-16 18:11:31,586 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2005689740] [2025-03-16 18:11:31,586 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:31,587 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2025-03-16 18:11:31,587 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:31,587 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2025-03-16 18:11:31,588 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=67, Invalid=395, Unknown=0, NotChecked=0, Total=462 [2025-03-16 18:11:31,588 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:32,640 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:32,640 INFO L93 Difference]: Finished difference Result 254 states and 393 transitions. [2025-03-16 18:11:32,640 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2025-03-16 18:11:32,640 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:32,641 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:32,642 INFO L225 Difference]: With dead ends: 254 [2025-03-16 18:11:32,642 INFO L226 Difference]: Without dead ends: 252 [2025-03-16 18:11:32,643 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:32,644 INFO L435 NwaCegarLoop]: 38 mSDtfsCounter, 95 mSDsluCounter, 287 mSDsCounter, 0 mSdLazyCounter, 563 mSolverCounterSat, 103 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 97 SdHoareTripleChecker+Valid, 325 SdHoareTripleChecker+Invalid, 666 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 103 IncrementalHoareTripleChecker+Valid, 563 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:32,644 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [97 Valid, 325 Invalid, 666 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [103 Valid, 563 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2025-03-16 18:11:32,645 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 252 states. [2025-03-16 18:11:32,704 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 252 to 211. [2025-03-16 18:11:32,705 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:32,707 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 211 states to 211 states and 320 transitions. [2025-03-16 18:11:32,708 INFO L78 Accepts]: Start accepts. Automaton has 211 states and 320 transitions. Word has length 58 [2025-03-16 18:11:32,708 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:32,708 INFO L471 AbstractCegarLoop]: Abstraction has 211 states and 320 transitions. [2025-03-16 18:11:32,708 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:32,708 INFO L276 IsEmpty]: Start isEmpty. Operand 211 states and 320 transitions. [2025-03-16 18:11:32,709 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 66 [2025-03-16 18:11:32,709 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:32,709 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:32,715 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:32,913 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:32,913 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:32,913 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:32,917 INFO L85 PathProgramCache]: Analyzing trace with hash 2061499091, now seen corresponding path program 1 times [2025-03-16 18:11:32,917 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:32,918 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [887029640] [2025-03-16 18:11:32,918 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:32,918 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:32,920 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 65 statements into 1 equivalence classes. [2025-03-16 18:11:32,929 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 65 of 65 statements. [2025-03-16 18:11:32,930 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:32,930 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:32,932 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [765469380] [2025-03-16 18:11:32,932 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:32,932 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:32,932 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:32,935 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:32,937 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:32,956 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 65 statements into 1 equivalence classes. [2025-03-16 18:11:32,970 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 65 of 65 statements. [2025-03-16 18:11:32,970 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:32,970 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:32,971 INFO L256 TraceCheckSpWp]: Trace formula consists of 160 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-03-16 18:11:32,972 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:33,015 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:33,015 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:33,064 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:33,064 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:33,064 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [887029640] [2025-03-16 18:11:33,064 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:33,064 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [765469380] [2025-03-16 18:11:33,064 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [765469380] provided 1 perfect and 1 imperfect interpolant sequences [2025-03-16 18:11:33,064 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-16 18:11:33,064 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2025-03-16 18:11:33,064 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1122623451] [2025-03-16 18:11:33,064 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:11:33,065 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-16 18:11:33,065 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:33,065 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-16 18:11:33,065 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2025-03-16 18:11:33,065 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:33,137 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:33,137 INFO L93 Difference]: Finished difference Result 217 states and 325 transitions. [2025-03-16 18:11:33,137 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-16 18:11:33,138 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:33,138 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:33,139 INFO L225 Difference]: With dead ends: 217 [2025-03-16 18:11:33,139 INFO L226 Difference]: Without dead ends: 215 [2025-03-16 18:11:33,139 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:33,139 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:33,139 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:33,140 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 215 states. [2025-03-16 18:11:33,187 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 215 to 215. [2025-03-16 18:11:33,188 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:33,189 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 215 states to 215 states and 323 transitions. [2025-03-16 18:11:33,189 INFO L78 Accepts]: Start accepts. Automaton has 215 states and 323 transitions. Word has length 65 [2025-03-16 18:11:33,189 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:33,190 INFO L471 AbstractCegarLoop]: Abstraction has 215 states and 323 transitions. [2025-03-16 18:11:33,190 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:33,190 INFO L276 IsEmpty]: Start isEmpty. Operand 215 states and 323 transitions. [2025-03-16 18:11:33,190 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 64 [2025-03-16 18:11:33,190 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:33,190 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:33,196 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2025-03-16 18:11:33,390 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:33,391 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:33,391 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:33,391 INFO L85 PathProgramCache]: Analyzing trace with hash 1341574078, now seen corresponding path program 2 times [2025-03-16 18:11:33,391 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:33,391 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2142396905] [2025-03-16 18:11:33,391 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:11:33,391 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:33,394 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 63 statements into 2 equivalence classes. [2025-03-16 18:11:33,414 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:33,414 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:11:33,414 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:33,415 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [939753583] [2025-03-16 18:11:33,415 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:11:33,415 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:33,415 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:33,419 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:33,420 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:33,444 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 63 statements into 2 equivalence classes. [2025-03-16 18:11:33,462 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:33,462 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:11:33,462 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:33,463 INFO L256 TraceCheckSpWp]: Trace formula consists of 183 conjuncts, 65 conjuncts are in the unsatisfiable core [2025-03-16 18:11:33,464 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:33,890 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:33,890 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:34,406 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:34,406 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:34,406 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2142396905] [2025-03-16 18:11:34,406 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:34,406 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [939753583] [2025-03-16 18:11:34,406 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [939753583] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:11:34,406 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:11:34,406 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 15] total 31 [2025-03-16 18:11:34,406 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [162961046] [2025-03-16 18:11:34,406 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:34,406 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 31 states [2025-03-16 18:11:34,406 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:34,407 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2025-03-16 18:11:34,407 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=139, Invalid=791, Unknown=0, NotChecked=0, Total=930 [2025-03-16 18:11:34,407 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:37,730 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:37,731 INFO L93 Difference]: Finished difference Result 399 states and 591 transitions. [2025-03-16 18:11:37,734 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 39 states. [2025-03-16 18:11:37,735 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:37,735 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:37,737 INFO L225 Difference]: With dead ends: 399 [2025-03-16 18:11:37,737 INFO L226 Difference]: Without dead ends: 334 [2025-03-16 18:11:37,738 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 153 GetRequests, 95 SyntacticMatches, 0 SemanticMatches, 58 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 780 ImplicationChecksByTransitivity, 2.1s TimeCoverageRelationStatistics Valid=678, Invalid=2862, Unknown=0, NotChecked=0, Total=3540 [2025-03-16 18:11:37,738 INFO L435 NwaCegarLoop]: 27 mSDtfsCounter, 144 mSDsluCounter, 359 mSDsCounter, 0 mSdLazyCounter, 939 mSolverCounterSat, 177 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.5s 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.6s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:37,738 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.6s Time] [2025-03-16 18:11:37,739 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 334 states. [2025-03-16 18:11:37,840 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 334 to 287. [2025-03-16 18:11:37,841 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:37,842 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 287 states to 287 states and 424 transitions. [2025-03-16 18:11:37,843 INFO L78 Accepts]: Start accepts. Automaton has 287 states and 424 transitions. Word has length 63 [2025-03-16 18:11:37,843 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:37,843 INFO L471 AbstractCegarLoop]: Abstraction has 287 states and 424 transitions. [2025-03-16 18:11:37,843 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:37,843 INFO L276 IsEmpty]: Start isEmpty. Operand 287 states and 424 transitions. [2025-03-16 18:11:37,844 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 79 [2025-03-16 18:11:37,844 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:37,844 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:37,850 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:38,044 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:38,045 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:38,045 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:38,045 INFO L85 PathProgramCache]: Analyzing trace with hash 408526629, now seen corresponding path program 1 times [2025-03-16 18:11:38,045 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:38,045 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1646866802] [2025-03-16 18:11:38,045 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:38,045 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:38,049 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 78 statements into 1 equivalence classes. [2025-03-16 18:11:38,058 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 78 of 78 statements. [2025-03-16 18:11:38,059 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:38,059 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:38,060 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [432712256] [2025-03-16 18:11:38,060 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:38,060 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:38,061 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:38,062 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:38,067 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:38,087 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 78 statements into 1 equivalence classes. [2025-03-16 18:11:38,109 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 78 of 78 statements. [2025-03-16 18:11:38,109 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:38,109 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:38,111 INFO L256 TraceCheckSpWp]: Trace formula consists of 207 conjuncts, 70 conjuncts are in the unsatisfiable core [2025-03-16 18:11:38,113 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:38,727 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:38,727 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:39,545 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:39,545 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:39,545 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1646866802] [2025-03-16 18:11:39,545 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:39,545 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [432712256] [2025-03-16 18:11:39,545 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [432712256] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:11:39,545 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:11:39,545 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 17] total 35 [2025-03-16 18:11:39,545 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1887842193] [2025-03-16 18:11:39,545 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:39,546 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 35 states [2025-03-16 18:11:39,546 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:39,546 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 35 interpolants. [2025-03-16 18:11:39,546 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=154, Invalid=1036, Unknown=0, NotChecked=0, Total=1190 [2025-03-16 18:11:39,547 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:46,894 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2025-03-16 18:12:00,580 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:12:00,580 INFO L93 Difference]: Finished difference Result 519 states and 820 transitions. [2025-03-16 18:12:00,581 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 93 states. [2025-03-16 18:12:00,581 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:12:00,581 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:12:00,584 INFO L225 Difference]: With dead ends: 519 [2025-03-16 18:12:00,584 INFO L226 Difference]: Without dead ends: 511 [2025-03-16 18:12:00,587 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 237 GetRequests, 121 SyntacticMatches, 0 SemanticMatches, 116 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4138 ImplicationChecksByTransitivity, 13.1s TimeCoverageRelationStatistics Valid=2405, Invalid=11401, Unknown=0, NotChecked=0, Total=13806 [2025-03-16 18:12:00,587 INFO L435 NwaCegarLoop]: 50 mSDtfsCounter, 199 mSDsluCounter, 699 mSDsCounter, 0 mSdLazyCounter, 1954 mSolverCounterSat, 289 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 8.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 199 SdHoareTripleChecker+Valid, 749 SdHoareTripleChecker+Invalid, 2244 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 289 IncrementalHoareTripleChecker+Valid, 1954 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 8.2s IncrementalHoareTripleChecker+Time [2025-03-16 18:12:00,587 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [199 Valid, 749 Invalid, 2244 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [289 Valid, 1954 Invalid, 1 Unknown, 0 Unchecked, 8.2s Time] [2025-03-16 18:12:00,588 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 511 states. [2025-03-16 18:12:00,822 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 511 to 394. [2025-03-16 18:12:00,823 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:12:00,825 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 394 states to 394 states and 605 transitions. [2025-03-16 18:12:00,825 INFO L78 Accepts]: Start accepts. Automaton has 394 states and 605 transitions. Word has length 78 [2025-03-16 18:12:00,825 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:12:00,825 INFO L471 AbstractCegarLoop]: Abstraction has 394 states and 605 transitions. [2025-03-16 18:12:00,826 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:12:00,826 INFO L276 IsEmpty]: Start isEmpty. Operand 394 states and 605 transitions. [2025-03-16 18:12:00,826 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 84 [2025-03-16 18:12:00,826 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:12:00,826 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:12:00,834 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:12:01,027 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:12:01,027 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:12:01,027 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:12:01,027 INFO L85 PathProgramCache]: Analyzing trace with hash -1408173133, now seen corresponding path program 2 times [2025-03-16 18:12:01,027 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:12:01,027 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1155960100] [2025-03-16 18:12:01,027 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:12:01,027 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:12:01,032 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 83 statements into 2 equivalence classes. [2025-03-16 18:12:01,049 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 83 of 83 statements. [2025-03-16 18:12:01,049 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:12:01,049 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:12:01,212 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:12:01,212 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:12:01,212 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1155960100] [2025-03-16 18:12:01,212 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1155960100] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:12:01,213 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1482351055] [2025-03-16 18:12:01,213 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:12:01,213 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:12:01,213 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:12:01,215 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:12:01,216 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:12:01,244 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 83 statements into 2 equivalence classes. [2025-03-16 18:12:01,276 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 83 of 83 statements. [2025-03-16 18:12:01,276 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:12:01,276 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:12:01,277 INFO L256 TraceCheckSpWp]: Trace formula consists of 230 conjuncts, 10 conjuncts are in the unsatisfiable core [2025-03-16 18:12:01,278 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:12:01,336 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:12:01,336 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:12:01,415 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:12:01,416 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1482351055] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:12:01,416 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 18:12:01,416 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10, 10] total 13 [2025-03-16 18:12:01,416 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [677005018] [2025-03-16 18:12:01,416 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 18:12:01,416 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2025-03-16 18:12:01,416 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:12:01,416 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2025-03-16 18:12:01,416 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=129, Unknown=0, NotChecked=0, Total=156 [2025-03-16 18:12:01,417 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:12:01,911 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:12:01,912 INFO L93 Difference]: Finished difference Result 651 states and 988 transitions. [2025-03-16 18:12:01,912 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2025-03-16 18:12:01,912 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:12:01,912 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:12:01,914 INFO L225 Difference]: With dead ends: 651 [2025-03-16 18:12:01,914 INFO L226 Difference]: Without dead ends: 411 [2025-03-16 18:12:01,915 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:12:01,916 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:12:01,916 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:12:01,916 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 411 states. [2025-03-16 18:12:02,080 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 411 to 306. [2025-03-16 18:12:02,081 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:12:02,082 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 306 states to 306 states and 446 transitions. [2025-03-16 18:12:02,083 INFO L78 Accepts]: Start accepts. Automaton has 306 states and 446 transitions. Word has length 83 [2025-03-16 18:12:02,083 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:12:02,083 INFO L471 AbstractCegarLoop]: Abstraction has 306 states and 446 transitions. [2025-03-16 18:12:02,083 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:12:02,083 INFO L276 IsEmpty]: Start isEmpty. Operand 306 states and 446 transitions. [2025-03-16 18:12:02,084 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 97 [2025-03-16 18:12:02,084 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:12:02,084 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:12:02,090 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2025-03-16 18:12:02,284 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:12:02,284 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:12:02,285 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:12:02,285 INFO L85 PathProgramCache]: Analyzing trace with hash -807522155, now seen corresponding path program 2 times [2025-03-16 18:12:02,285 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:12:02,285 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1735812964] [2025-03-16 18:12:02,285 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:12:02,285 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:12:02,288 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 96 statements into 2 equivalence classes. [2025-03-16 18:12:02,297 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 96 of 96 statements. [2025-03-16 18:12:02,297 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:12:02,297 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:12:02,298 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [528513619] [2025-03-16 18:12:02,298 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:12:02,298 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:12:02,298 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:12:02,299 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:12:02,301 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:12:02,326 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 96 statements into 2 equivalence classes. [2025-03-16 18:12:02,348 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 96 of 96 statements. [2025-03-16 18:12:02,348 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:12:02,348 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:12:02,349 INFO L256 TraceCheckSpWp]: Trace formula consists of 230 conjuncts, 47 conjuncts are in the unsatisfiable core [2025-03-16 18:12:02,351 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:12:02,760 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:12:02,760 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:12:03,134 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:12:03,134 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:12:03,134 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1735812964] [2025-03-16 18:12:03,135 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:12:03,135 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [528513619] [2025-03-16 18:12:03,135 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [528513619] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:12:03,135 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:12:03,135 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 22 [2025-03-16 18:12:03,135 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1062392447] [2025-03-16 18:12:03,135 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:12:03,135 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2025-03-16 18:12:03,135 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:12:03,135 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2025-03-16 18:12:03,135 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=66, Invalid=396, Unknown=0, NotChecked=0, Total=462 [2025-03-16 18:12:03,136 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:12:07,596 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:12:07,597 INFO L93 Difference]: Finished difference Result 510 states and 789 transitions. [2025-03-16 18:12:07,597 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 60 states. [2025-03-16 18:12:07,597 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:12:07,598 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:12:07,600 INFO L225 Difference]: With dead ends: 510 [2025-03-16 18:12:07,600 INFO L226 Difference]: Without dead ends: 502 [2025-03-16 18:12:07,603 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 239 GetRequests, 168 SyntacticMatches, 2 SemanticMatches, 69 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1406 ImplicationChecksByTransitivity, 3.2s TimeCoverageRelationStatistics Valid=867, Invalid=4103, Unknown=0, NotChecked=0, Total=4970 [2025-03-16 18:12:07,603 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:12:07,604 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:12:07,604 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 502 states. [2025-03-16 18:12:07,811 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 502 to 342. [2025-03-16 18:12:07,812 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:12:07,813 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 342 states to 342 states and 512 transitions. [2025-03-16 18:12:07,814 INFO L78 Accepts]: Start accepts. Automaton has 342 states and 512 transitions. Word has length 96 [2025-03-16 18:12:07,814 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:12:07,814 INFO L471 AbstractCegarLoop]: Abstraction has 342 states and 512 transitions. [2025-03-16 18:12:07,814 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:12:07,814 INFO L276 IsEmpty]: Start isEmpty. Operand 342 states and 512 transitions. [2025-03-16 18:12:07,815 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 99 [2025-03-16 18:12:07,815 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:12:07,815 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:12:07,822 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2025-03-16 18:12:08,016 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:12:08,016 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:12:08,017 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:12:08,017 INFO L85 PathProgramCache]: Analyzing trace with hash 1069370314, now seen corresponding path program 3 times [2025-03-16 18:12:08,017 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:12:08,017 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [402454544] [2025-03-16 18:12:08,017 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 18:12:08,017 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:12:08,021 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 98 statements into 11 equivalence classes. [2025-03-16 18:12:08,052 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 11 check-sat command(s) and asserted 98 of 98 statements. [2025-03-16 18:12:08,053 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 11 check-sat command(s) [2025-03-16 18:12:08,053 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:12:08,055 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1438470757] [2025-03-16 18:12:08,055 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 18:12:08,055 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:12:08,055 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:12:08,057 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:12:08,059 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:12:08,085 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 98 statements into 11 equivalence classes. [2025-03-16 18:12:08,104 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) and asserted 62 of 98 statements. [2025-03-16 18:12:08,104 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2025-03-16 18:12:08,104 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:12:08,106 INFO L256 TraceCheckSpWp]: Trace formula consists of 167 conjuncts, 61 conjuncts are in the unsatisfiable core [2025-03-16 18:12:08,107 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:12:08,771 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:12:08,771 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:12:09,354 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:12:09,354 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [402454544] [2025-03-16 18:12:09,354 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:12:09,354 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1438470757] [2025-03-16 18:12:09,354 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1438470757] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:12:09,354 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-16 18:12:09,354 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19] total 19 [2025-03-16 18:12:09,354 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2023900322] [2025-03-16 18:12:09,354 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-16 18:12:09,354 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2025-03-16 18:12:09,354 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:12:09,355 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2025-03-16 18:12:09,355 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=126, Invalid=686, Unknown=0, NotChecked=0, Total=812 [2025-03-16 18:12:09,355 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:10,168 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:12:10,168 INFO L93 Difference]: Finished difference Result 428 states and 632 transitions. [2025-03-16 18:12:10,169 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2025-03-16 18:12:10,169 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:10,169 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:12:10,171 INFO L225 Difference]: With dead ends: 428 [2025-03-16 18:12:10,171 INFO L226 Difference]: Without dead ends: 421 [2025-03-16 18:12:10,171 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:10,172 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:10,172 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:10,172 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 421 states. [2025-03-16 18:12:10,418 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 421 to 410. [2025-03-16 18:12:10,419 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:10,420 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 410 states to 410 states and 614 transitions. [2025-03-16 18:12:10,421 INFO L78 Accepts]: Start accepts. Automaton has 410 states and 614 transitions. Word has length 98 [2025-03-16 18:12:10,421 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:12:10,421 INFO L471 AbstractCegarLoop]: Abstraction has 410 states and 614 transitions. [2025-03-16 18:12:10,421 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:10,421 INFO L276 IsEmpty]: Start isEmpty. Operand 410 states and 614 transitions. [2025-03-16 18:12:10,422 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 102 [2025-03-16 18:12:10,422 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:12:10,422 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:10,429 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:10,623 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:10,623 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:12:10,623 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:12:10,623 INFO L85 PathProgramCache]: Analyzing trace with hash 311264781, now seen corresponding path program 4 times [2025-03-16 18:12:10,623 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:12:10,623 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [864314753] [2025-03-16 18:12:10,624 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-16 18:12:10,624 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:12:10,627 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 101 statements into 2 equivalence classes. [2025-03-16 18:12:10,642 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:10,643 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-03-16 18:12:10,643 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:12:10,643 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [186463007] [2025-03-16 18:12:10,644 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-16 18:12:10,644 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:12:10,644 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:12:10,645 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:10,647 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:10,669 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 101 statements into 2 equivalence classes. [2025-03-16 18:12:10,690 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:10,690 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-03-16 18:12:10,690 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:12:10,691 INFO L256 TraceCheckSpWp]: Trace formula consists of 222 conjuncts, 75 conjuncts are in the unsatisfiable core [2025-03-16 18:12:10,693 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:12:11,298 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:11,299 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:12:11,884 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:11,884 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:12:11,884 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [864314753] [2025-03-16 18:12:11,884 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:12:11,884 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [186463007] [2025-03-16 18:12:11,884 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [186463007] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:12:11,884 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:12:11,884 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 16] total 33 [2025-03-16 18:12:11,884 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [621522692] [2025-03-16 18:12:11,884 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:12:11,885 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 33 states [2025-03-16 18:12:11,886 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:12:11,886 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2025-03-16 18:12:11,886 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=137, Invalid=919, Unknown=0, NotChecked=0, Total=1056 [2025-03-16 18:12:11,886 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:23,147 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:12:23,147 INFO L93 Difference]: Finished difference Result 676 states and 1057 transitions. [2025-03-16 18:12:23,147 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 93 states. [2025-03-16 18:12:23,147 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:23,147 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:12:23,150 INFO L225 Difference]: With dead ends: 676 [2025-03-16 18:12:23,150 INFO L226 Difference]: Without dead ends: 668 [2025-03-16 18:12:23,153 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 284 GetRequests, 169 SyntacticMatches, 0 SemanticMatches, 115 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4029 ImplicationChecksByTransitivity, 7.7s TimeCoverageRelationStatistics Valid=2038, Invalid=11534, Unknown=0, NotChecked=0, Total=13572 [2025-03-16 18:12:23,153 INFO L435 NwaCegarLoop]: 37 mSDtfsCounter, 293 mSDsluCounter, 614 mSDsCounter, 0 mSdLazyCounter, 1471 mSolverCounterSat, 434 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.3s 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, 3.4s IncrementalHoareTripleChecker+Time [2025-03-16 18:12:23,154 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [293 Valid, 651 Invalid, 1905 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [434 Valid, 1471 Invalid, 0 Unknown, 0 Unchecked, 3.4s Time] [2025-03-16 18:12:23,154 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 668 states. [2025-03-16 18:12:23,572 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 668 to 515. [2025-03-16 18:12:23,573 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:23,574 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 515 states to 515 states and 791 transitions. [2025-03-16 18:12:23,575 INFO L78 Accepts]: Start accepts. Automaton has 515 states and 791 transitions. Word has length 101 [2025-03-16 18:12:23,575 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:12:23,576 INFO L471 AbstractCegarLoop]: Abstraction has 515 states and 791 transitions. [2025-03-16 18:12:23,576 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:23,576 INFO L276 IsEmpty]: Start isEmpty. Operand 515 states and 791 transitions. [2025-03-16 18:12:23,579 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 105 [2025-03-16 18:12:23,580 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:12:23,580 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:23,586 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Ended with exit code 0 [2025-03-16 18:12:23,780 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:23,780 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:12:23,780 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:12:23,781 INFO L85 PathProgramCache]: Analyzing trace with hash -1999255606, now seen corresponding path program 5 times [2025-03-16 18:12:23,781 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:12:23,781 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [261722555] [2025-03-16 18:12:23,781 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-03-16 18:12:23,781 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:12:23,785 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 104 statements into 8 equivalence classes. [2025-03-16 18:12:23,801 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:23,802 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 8 check-sat command(s) [2025-03-16 18:12:23,802 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:12:23,803 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1942139323] [2025-03-16 18:12:23,803 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-03-16 18:12:23,803 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:12:23,803 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:12:23,805 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:23,806 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:23,830 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 104 statements into 8 equivalence classes. [2025-03-16 18:12:23,866 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:23,866 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 8 check-sat command(s) [2025-03-16 18:12:23,866 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:12:23,868 INFO L256 TraceCheckSpWp]: Trace formula consists of 271 conjuncts, 77 conjuncts are in the unsatisfiable core [2025-03-16 18:12:23,869 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:12:25,248 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:25,248 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:12:26,288 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:12:26,288 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [261722555] [2025-03-16 18:12:26,288 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:12:26,288 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1942139323] [2025-03-16 18:12:26,288 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1942139323] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:12:26,288 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-16 18:12:26,288 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [23] total 23 [2025-03-16 18:12:26,289 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [498843521] [2025-03-16 18:12:26,289 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-16 18:12:26,289 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2025-03-16 18:12:26,289 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:12:26,289 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2025-03-16 18:12:26,289 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=93, Invalid=777, Unknown=0, NotChecked=0, Total=870 [2025-03-16 18:12:26,289 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:28,547 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:12:28,547 INFO L93 Difference]: Finished difference Result 605 states and 919 transitions. [2025-03-16 18:12:28,547 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2025-03-16 18:12:28,547 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:28,548 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:12:28,550 INFO L225 Difference]: With dead ends: 605 [2025-03-16 18:12:28,550 INFO L226 Difference]: Without dead ends: 598 [2025-03-16 18:12:28,551 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 154 GetRequests, 116 SyntacticMatches, 0 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 237 ImplicationChecksByTransitivity, 2.1s TimeCoverageRelationStatistics Valid=167, Invalid=1393, Unknown=0, NotChecked=0, Total=1560 [2025-03-16 18:12:28,551 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:28,551 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:28,552 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 598 states. [2025-03-16 18:12:29,094 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 598 to 566. [2025-03-16 18:12:29,095 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:29,097 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 566 states to 566 states and 869 transitions. [2025-03-16 18:12:29,098 INFO L78 Accepts]: Start accepts. Automaton has 566 states and 869 transitions. Word has length 104 [2025-03-16 18:12:29,098 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:12:29,098 INFO L471 AbstractCegarLoop]: Abstraction has 566 states and 869 transitions. [2025-03-16 18:12:29,098 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:29,098 INFO L276 IsEmpty]: Start isEmpty. Operand 566 states and 869 transitions. [2025-03-16 18:12:29,100 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 108 [2025-03-16 18:12:29,100 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:12:29,100 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:29,106 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2025-03-16 18:12:29,300 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:29,300 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:12:29,301 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:12:29,301 INFO L85 PathProgramCache]: Analyzing trace with hash 985041779, now seen corresponding path program 1 times [2025-03-16 18:12:29,301 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:12:29,301 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1680460165] [2025-03-16 18:12:29,301 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:12:29,301 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:12:29,305 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 107 statements into 1 equivalence classes. [2025-03-16 18:12:29,318 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 107 of 107 statements. [2025-03-16 18:12:29,318 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:12:29,318 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:12:29,319 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1439098991] [2025-03-16 18:12:29,319 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:12:29,319 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:12:29,319 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:12:29,321 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:29,322 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:29,347 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 107 statements into 1 equivalence classes. [2025-03-16 18:12:29,376 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 107 of 107 statements. [2025-03-16 18:12:29,377 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:12:29,377 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:12:29,383 INFO L256 TraceCheckSpWp]: Trace formula consists of 270 conjuncts, 73 conjuncts are in the unsatisfiable core [2025-03-16 18:12:29,388 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:12:30,071 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:30,071 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:12:31,077 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:31,077 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:12:31,077 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1680460165] [2025-03-16 18:12:31,077 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:12:31,077 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1439098991] [2025-03-16 18:12:31,078 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1439098991] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:12:31,078 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:12:31,078 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 17] total 35 [2025-03-16 18:12:31,078 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1368535120] [2025-03-16 18:12:31,078 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:12:31,078 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 35 states [2025-03-16 18:12:31,078 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:12:31,078 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 35 interpolants. [2025-03-16 18:12:31,079 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=177, Invalid=1013, Unknown=0, NotChecked=0, Total=1190 [2025-03-16 18:12:31,079 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:43,894 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.88s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2025-03-16 18:12:59,098 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:12:59,098 INFO L93 Difference]: Finished difference Result 840 states and 1308 transitions. [2025-03-16 18:12:59,099 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 80 states. [2025-03-16 18:12:59,099 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:59,099 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:12:59,103 INFO L225 Difference]: With dead ends: 840 [2025-03-16 18:12:59,103 INFO L226 Difference]: Without dead ends: 838 [2025-03-16 18:12:59,105 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 284 GetRequests, 179 SyntacticMatches, 0 SemanticMatches, 105 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3212 ImplicationChecksByTransitivity, 20.4s TimeCoverageRelationStatistics Valid=2276, Invalid=9066, Unknown=0, NotChecked=0, Total=11342 [2025-03-16 18:12:59,105 INFO L435 NwaCegarLoop]: 43 mSDtfsCounter, 237 mSDsluCounter, 572 mSDsCounter, 0 mSdLazyCounter, 1557 mSolverCounterSat, 314 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 7.3s 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, 7.4s IncrementalHoareTripleChecker+Time [2025-03-16 18:12:59,105 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [237 Valid, 615 Invalid, 1871 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [314 Valid, 1557 Invalid, 0 Unknown, 0 Unchecked, 7.4s Time] [2025-03-16 18:12:59,106 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 838 states. [2025-03-16 18:12:59,873 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 838 to 731. [2025-03-16 18:12:59,874 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:59,876 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 731 states to 731 states and 1140 transitions. [2025-03-16 18:12:59,877 INFO L78 Accepts]: Start accepts. Automaton has 731 states and 1140 transitions. Word has length 107 [2025-03-16 18:12:59,878 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:12:59,878 INFO L471 AbstractCegarLoop]: Abstraction has 731 states and 1140 transitions. [2025-03-16 18:12:59,878 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:59,878 INFO L276 IsEmpty]: Start isEmpty. Operand 731 states and 1140 transitions. [2025-03-16 18:12:59,879 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 113 [2025-03-16 18:12:59,879 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:12:59,879 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:59,885 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:13:00,080 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:13:00,080 INFO L396 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:13:00,080 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:13:00,080 INFO L85 PathProgramCache]: Analyzing trace with hash 448458035, now seen corresponding path program 2 times [2025-03-16 18:13:00,080 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:13:00,080 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [677159762] [2025-03-16 18:13:00,080 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:13:00,080 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:13:00,085 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 112 statements into 2 equivalence classes. [2025-03-16 18:13:00,097 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 112 of 112 statements. [2025-03-16 18:13:00,098 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:13:00,098 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:13:00,099 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [287093608] [2025-03-16 18:13:00,099 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:13:00,099 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:13:00,099 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:13:00,101 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:13:00,103 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:13:00,128 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 112 statements into 2 equivalence classes. [2025-03-16 18:13:00,153 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 112 of 112 statements. [2025-03-16 18:13:00,154 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:13:00,154 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:13:00,156 INFO L256 TraceCheckSpWp]: Trace formula consists of 279 conjuncts, 44 conjuncts are in the unsatisfiable core [2025-03-16 18:13:00,158 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:13:00,373 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:13:00,373 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:13:00,538 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:13:00,538 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:13:00,538 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [677159762] [2025-03-16 18:13:00,538 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:13:00,538 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [287093608] [2025-03-16 18:13:00,538 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [287093608] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:13:00,538 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:13:00,538 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 9] total 25 [2025-03-16 18:13:00,538 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1526345422] [2025-03-16 18:13:00,538 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:13:00,538 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2025-03-16 18:13:00,538 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:13:00,539 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2025-03-16 18:13:00,539 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=82, Invalid=518, Unknown=0, NotChecked=0, Total=600 [2025-03-16 18:13:00,539 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:13:02,997 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:13:02,997 INFO L93 Difference]: Finished difference Result 1131 states and 1830 transitions. [2025-03-16 18:13:02,997 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 42 states. [2025-03-16 18:13:02,997 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:13:02,998 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:13:03,002 INFO L225 Difference]: With dead ends: 1131 [2025-03-16 18:13:03,002 INFO L226 Difference]: Without dead ends: 1129 [2025-03-16 18:13:03,003 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:13:03,004 INFO L435 NwaCegarLoop]: 49 mSDtfsCounter, 114 mSDsluCounter, 499 mSDsCounter, 0 mSdLazyCounter, 763 mSolverCounterSat, 133 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s 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:13:03,004 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:13:03,005 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1129 states. [2025-03-16 18:13:04,231 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1129 to 1006. [2025-03-16 18:13:04,233 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:13:04,236 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1006 states to 1006 states and 1641 transitions. [2025-03-16 18:13:04,237 INFO L78 Accepts]: Start accepts. Automaton has 1006 states and 1641 transitions. Word has length 112 [2025-03-16 18:13:04,238 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:13:04,238 INFO L471 AbstractCegarLoop]: Abstraction has 1006 states and 1641 transitions. [2025-03-16 18:13:04,238 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:13:04,238 INFO L276 IsEmpty]: Start isEmpty. Operand 1006 states and 1641 transitions. [2025-03-16 18:13:04,239 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 120 [2025-03-16 18:13:04,240 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:13:04,240 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:13:04,246 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:13:04,443 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:13:04,443 INFO L396 AbstractCegarLoop]: === Iteration 21 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:13:04,444 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:13:04,444 INFO L85 PathProgramCache]: Analyzing trace with hash 419380243, now seen corresponding path program 6 times [2025-03-16 18:13:04,444 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:13:04,444 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1771809915] [2025-03-16 18:13:04,444 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-03-16 18:13:04,444 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:13:04,448 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 119 statements into 12 equivalence classes. [2025-03-16 18:13:04,458 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 8 check-sat command(s) and asserted 89 of 119 statements. [2025-03-16 18:13:04,458 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 8 check-sat command(s) [2025-03-16 18:13:04,458 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:13:04,562 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:13:04,562 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:13:04,562 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1771809915] [2025-03-16 18:13:04,562 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1771809915] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:13:04,562 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [849378687] [2025-03-16 18:13:04,562 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-03-16 18:13:04,562 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:13:04,562 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:13:04,564 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:13:04,565 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:13:04,592 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 119 statements into 12 equivalence classes. [2025-03-16 18:13:04,614 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 8 check-sat command(s) and asserted 89 of 119 statements. [2025-03-16 18:13:04,614 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 8 check-sat command(s) [2025-03-16 18:13:04,614 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:13:04,615 INFO L256 TraceCheckSpWp]: Trace formula consists of 222 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-03-16 18:13:04,617 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:13:04,697 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:13:04,698 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:13:04,819 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:13:04,819 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [849378687] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:13:04,819 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 18:13:04,819 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10, 10] total 14 [2025-03-16 18:13:04,819 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1308989341] [2025-03-16 18:13:04,819 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 18:13:04,820 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2025-03-16 18:13:04,820 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:13:04,820 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2025-03-16 18:13:04,820 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=31, Invalid=151, Unknown=0, NotChecked=0, Total=182 [2025-03-16 18:13:04,820 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)