./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound20.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_valuebound20.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 39b854852f8258ff198098e27d83a5b0e296df48090ebea0d59d234417af0752 --- Real Ultimate output --- This is Ultimate 0.3.0-?-8fc3dc6-m [2025-03-16 18:11:13,162 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-16 18:11:13,214 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:13,219 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-16 18:11:13,219 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-16 18:11:13,242 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-16 18:11:13,243 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-16 18:11:13,243 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-16 18:11:13,244 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-16 18:11:13,244 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-16 18:11:13,244 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-03-16 18:11:13,244 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-03-16 18:11:13,245 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-16 18:11:13,245 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-16 18:11:13,245 INFO L153 SettingsManager]: * Use SBE=true [2025-03-16 18:11:13,245 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-16 18:11:13,246 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-03-16 18:11:13,246 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-16 18:11:13,246 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-16 18:11:13,246 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-16 18:11:13,246 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-16 18:11:13,246 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-03-16 18:11:13,246 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-03-16 18:11:13,246 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-03-16 18:11:13,246 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-16 18:11:13,246 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-16 18:11:13,246 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-16 18:11:13,246 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-16 18:11:13,247 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-16 18:11:13,247 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-16 18:11:13,247 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-03-16 18:11:13,247 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-03-16 18:11:13,247 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-16 18:11:13,247 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-16 18:11:13,247 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-03-16 18:11:13,247 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-03-16 18:11:13,247 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-03-16 18:11:13,247 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-16 18:11:13,247 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-03-16 18:11:13,247 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-03-16 18:11:13,248 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-03-16 18:11:13,248 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-03-16 18:11:13,248 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-03-16 18:11:13,248 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 -> 39b854852f8258ff198098e27d83a5b0e296df48090ebea0d59d234417af0752 [2025-03-16 18:11:13,463 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-16 18:11:13,471 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-16 18:11:13,472 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-16 18:11:13,473 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-16 18:11:13,473 INFO L274 PluginConnector]: CDTParser initialized [2025-03-16 18:11:13,474 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound20.c [2025-03-16 18:11:14,648 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/193815aa1/79302c3002334aafa893f4bc901e7cc9/FLAGb2224dad2 [2025-03-16 18:11:14,851 INFO L384 CDTParser]: Found 1 translation units. [2025-03-16 18:11:14,852 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound20.c [2025-03-16 18:11:14,857 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/193815aa1/79302c3002334aafa893f4bc901e7cc9/FLAGb2224dad2 [2025-03-16 18:11:14,867 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/193815aa1/79302c3002334aafa893f4bc901e7cc9 [2025-03-16 18:11:14,869 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-16 18:11:14,870 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-16 18:11:14,871 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-16 18:11:14,871 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-16 18:11:14,874 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-16 18:11:14,875 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.03 06:11:14" (1/1) ... [2025-03-16 18:11:14,877 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@67196f7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:14, skipping insertion in model container [2025-03-16 18:11:14,877 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.03 06:11:14" (1/1) ... [2025-03-16 18:11:14,888 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-16 18:11:14,982 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_valuebound20.c[490,503] [2025-03-16 18:11:15,003 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-16 18:11:15,013 INFO L200 MainTranslator]: Completed pre-run [2025-03-16 18:11:15,020 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_valuebound20.c[490,503] [2025-03-16 18:11:15,031 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-16 18:11:15,041 INFO L204 MainTranslator]: Completed translation [2025-03-16 18:11:15,042 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:15 WrapperNode [2025-03-16 18:11:15,043 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-16 18:11:15,044 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-16 18:11:15,044 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-16 18:11:15,045 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-16 18:11:15,049 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:15" (1/1) ... [2025-03-16 18:11:15,053 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:15" (1/1) ... [2025-03-16 18:11:15,065 INFO L138 Inliner]: procedures = 14, calls = 16, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 74 [2025-03-16 18:11:15,066 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-16 18:11:15,067 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-16 18:11:15,067 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-16 18:11:15,067 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-16 18:11:15,073 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:15" (1/1) ... [2025-03-16 18:11:15,073 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:15" (1/1) ... [2025-03-16 18:11:15,075 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:15" (1/1) ... [2025-03-16 18:11:15,087 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:15,089 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:15" (1/1) ... [2025-03-16 18:11:15,089 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:15" (1/1) ... [2025-03-16 18:11:15,091 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:15" (1/1) ... [2025-03-16 18:11:15,095 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:15" (1/1) ... [2025-03-16 18:11:15,095 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:15" (1/1) ... [2025-03-16 18:11:15,096 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:15" (1/1) ... [2025-03-16 18:11:15,097 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-16 18:11:15,099 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-16 18:11:15,099 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-16 18:11:15,099 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-16 18:11:15,100 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:15" (1/1) ... [2025-03-16 18:11:15,103 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-16 18:11:15,114 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:15,127 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:15,131 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:15,149 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-16 18:11:15,149 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2025-03-16 18:11:15,149 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2025-03-16 18:11:15,149 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-03-16 18:11:15,149 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-16 18:11:15,149 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-16 18:11:15,149 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2025-03-16 18:11:15,149 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2025-03-16 18:11:15,196 INFO L256 CfgBuilder]: Building ICFG [2025-03-16 18:11:15,198 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-16 18:11:15,317 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2025-03-16 18:11:15,317 INFO L307 CfgBuilder]: Performing block encoding [2025-03-16 18:11:15,323 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-16 18:11:15,323 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-16 18:11:15,324 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 16.03 06:11:15 BoogieIcfgContainer [2025-03-16 18:11:15,324 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-16 18:11:15,325 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-03-16 18:11:15,325 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-03-16 18:11:15,328 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-03-16 18:11:15,328 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 16.03 06:11:14" (1/3) ... [2025-03-16 18:11:15,328 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@17953708 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.03 06:11:15, skipping insertion in model container [2025-03-16 18:11:15,329 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:15" (2/3) ... [2025-03-16 18:11:15,329 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@17953708 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.03 06:11:15, skipping insertion in model container [2025-03-16 18:11:15,329 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 16.03 06:11:15" (3/3) ... [2025-03-16 18:11:15,330 INFO L128 eAbstractionObserver]: Analyzing ICFG egcd3-ll_valuebound20.c [2025-03-16 18:11:15,340 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-03-16 18:11:15,342 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG egcd3-ll_valuebound20.c that has 3 procedures, 30 locations, 1 initial locations, 3 loop locations, and 1 error locations. [2025-03-16 18:11:15,378 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-03-16 18:11:15,388 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;@4b5bfd65, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-03-16 18:11:15,389 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-03-16 18:11:15,391 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:15,395 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2025-03-16 18:11:15,396 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:15,396 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:15,396 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:15,400 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:15,401 INFO L85 PathProgramCache]: Analyzing trace with hash -1461292294, now seen corresponding path program 1 times [2025-03-16 18:11:15,406 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:15,406 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [146498676] [2025-03-16 18:11:15,406 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:15,406 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:15,463 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 28 statements into 1 equivalence classes. [2025-03-16 18:11:15,494 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 28 of 28 statements. [2025-03-16 18:11:15,495 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:15,495 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:15,706 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:15,706 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:15,707 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [146498676] [2025-03-16 18:11:15,707 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [146498676] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 18:11:15,708 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 18:11:15,708 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2025-03-16 18:11:15,709 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [537361289] [2025-03-16 18:11:15,709 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:11:15,712 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2025-03-16 18:11:15,712 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:15,727 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-03-16 18:11:15,728 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2025-03-16 18:11:15,730 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:15,868 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:15,869 INFO L93 Difference]: Finished difference Result 67 states and 117 transitions. [2025-03-16 18:11:15,870 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-16 18:11:15,871 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:15,871 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:15,875 INFO L225 Difference]: With dead ends: 67 [2025-03-16 18:11:15,876 INFO L226 Difference]: Without dead ends: 36 [2025-03-16 18:11:15,879 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:15,882 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:15,882 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:15,895 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36 states. [2025-03-16 18:11:15,911 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36 to 28. [2025-03-16 18:11:15,913 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:15,916 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28 states to 28 states and 37 transitions. [2025-03-16 18:11:15,917 INFO L78 Accepts]: Start accepts. Automaton has 28 states and 37 transitions. Word has length 28 [2025-03-16 18:11:15,917 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:15,918 INFO L471 AbstractCegarLoop]: Abstraction has 28 states and 37 transitions. [2025-03-16 18:11:15,918 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:15,918 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 37 transitions. [2025-03-16 18:11:15,919 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2025-03-16 18:11:15,919 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:15,919 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:15,919 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2025-03-16 18:11:15,919 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:15,920 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:15,920 INFO L85 PathProgramCache]: Analyzing trace with hash 1979049318, now seen corresponding path program 1 times [2025-03-16 18:11:15,920 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:15,920 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [480717852] [2025-03-16 18:11:15,920 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:15,920 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:15,933 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 29 statements into 1 equivalence classes. [2025-03-16 18:11:15,951 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 29 of 29 statements. [2025-03-16 18:11:15,951 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:15,951 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:15,953 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [275490148] [2025-03-16 18:11:15,955 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:15,955 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:15,955 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:15,957 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:15,959 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:15,992 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 29 statements into 1 equivalence classes. [2025-03-16 18:11:16,011 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 29 of 29 statements. [2025-03-16 18:11:16,012 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:16,012 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:16,014 INFO L256 TraceCheckSpWp]: Trace formula consists of 92 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-03-16 18:11:16,018 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:16,121 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:16,122 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-16 18:11:16,122 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:16,122 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [480717852] [2025-03-16 18:11:16,124 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:16,124 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [275490148] [2025-03-16 18:11:16,124 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [275490148] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 18:11:16,124 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 18:11:16,124 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-16 18:11:16,125 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [515875433] [2025-03-16 18:11:16,125 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:11:16,125 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-16 18:11:16,125 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:16,126 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-16 18:11:16,126 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-16 18:11:16,126 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:16,163 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:16,163 INFO L93 Difference]: Finished difference Result 42 states and 56 transitions. [2025-03-16 18:11:16,164 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-16 18:11:16,164 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:16,164 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:16,165 INFO L225 Difference]: With dead ends: 42 [2025-03-16 18:11:16,165 INFO L226 Difference]: Without dead ends: 40 [2025-03-16 18:11:16,165 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:16,165 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:16,165 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:16,166 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40 states. [2025-03-16 18:11:16,174 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40 to 39. [2025-03-16 18:11:16,175 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:16,178 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 53 transitions. [2025-03-16 18:11:16,178 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 53 transitions. Word has length 29 [2025-03-16 18:11:16,178 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:16,178 INFO L471 AbstractCegarLoop]: Abstraction has 39 states and 53 transitions. [2025-03-16 18:11:16,179 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:16,179 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 53 transitions. [2025-03-16 18:11:16,180 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2025-03-16 18:11:16,180 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:16,180 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:16,187 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:16,384 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:16,384 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:16,384 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:16,385 INFO L85 PathProgramCache]: Analyzing trace with hash 351925117, now seen corresponding path program 1 times [2025-03-16 18:11:16,385 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:16,385 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [951824789] [2025-03-16 18:11:16,385 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:16,385 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:16,390 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-03-16 18:11:16,400 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-03-16 18:11:16,400 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:16,400 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:16,543 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:16,543 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:16,544 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [951824789] [2025-03-16 18:11:16,544 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [951824789] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:11:16,544 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [597968326] [2025-03-16 18:11:16,544 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:16,544 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:16,544 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:16,546 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:16,547 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:16,569 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-03-16 18:11:16,581 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-03-16 18:11:16,582 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:16,582 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:16,582 INFO L256 TraceCheckSpWp]: Trace formula consists of 102 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-03-16 18:11:16,584 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:16,606 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:16,607 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:16,695 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 6 proven. 4 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2025-03-16 18:11:16,696 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [597968326] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:11:16,696 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 18:11:16,696 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 9 [2025-03-16 18:11:16,696 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2065357842] [2025-03-16 18:11:16,696 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:16,696 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2025-03-16 18:11:16,696 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:16,697 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2025-03-16 18:11:16,697 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2025-03-16 18:11:16,697 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:16,852 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:16,853 INFO L93 Difference]: Finished difference Result 81 states and 121 transitions. [2025-03-16 18:11:16,853 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-03-16 18:11:16,854 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:16,854 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:16,855 INFO L225 Difference]: With dead ends: 81 [2025-03-16 18:11:16,855 INFO L226 Difference]: Without dead ends: 74 [2025-03-16 18:11:16,855 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:16,856 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:16,857 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:16,858 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 74 states. [2025-03-16 18:11:16,871 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 74 to 53. [2025-03-16 18:11:16,873 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:16,874 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 77 transitions. [2025-03-16 18:11:16,875 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 77 transitions. Word has length 31 [2025-03-16 18:11:16,875 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:16,876 INFO L471 AbstractCegarLoop]: Abstraction has 53 states and 77 transitions. [2025-03-16 18:11:16,876 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:16,876 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 77 transitions. [2025-03-16 18:11:16,876 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2025-03-16 18:11:16,877 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:16,877 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:16,883 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:17,078 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:17,078 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:17,078 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:17,078 INFO L85 PathProgramCache]: Analyzing trace with hash -1940753085, now seen corresponding path program 1 times [2025-03-16 18:11:17,078 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:17,078 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [294966661] [2025-03-16 18:11:17,078 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:17,079 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:17,083 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 32 statements into 1 equivalence classes. [2025-03-16 18:11:17,090 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 32 of 32 statements. [2025-03-16 18:11:17,090 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:17,090 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:17,091 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [465517359] [2025-03-16 18:11:17,091 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:17,091 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:17,091 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:17,093 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:17,094 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:17,116 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 32 statements into 1 equivalence classes. [2025-03-16 18:11:17,127 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 32 of 32 statements. [2025-03-16 18:11:17,128 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:17,128 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:17,128 INFO L256 TraceCheckSpWp]: Trace formula consists of 110 conjuncts, 15 conjuncts are in the unsatisfiable core [2025-03-16 18:11:17,130 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:17,201 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:17,201 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:17,310 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:17,311 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:17,311 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [294966661] [2025-03-16 18:11:17,311 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:17,311 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [465517359] [2025-03-16 18:11:17,311 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [465517359] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:11:17,311 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:11:17,311 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 8 [2025-03-16 18:11:17,311 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1779852179] [2025-03-16 18:11:17,311 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:17,312 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2025-03-16 18:11:17,312 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:17,312 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-03-16 18:11:17,312 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2025-03-16 18:11:17,312 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:17,418 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:17,418 INFO L93 Difference]: Finished difference Result 82 states and 119 transitions. [2025-03-16 18:11:17,421 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-16 18:11:17,422 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:17,422 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:17,422 INFO L225 Difference]: With dead ends: 82 [2025-03-16 18:11:17,423 INFO L226 Difference]: Without dead ends: 80 [2025-03-16 18:11:17,423 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:17,423 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:17,423 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:17,424 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 80 states. [2025-03-16 18:11:17,440 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 80 to 76. [2025-03-16 18:11:17,440 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:17,443 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 76 states to 76 states and 113 transitions. [2025-03-16 18:11:17,443 INFO L78 Accepts]: Start accepts. Automaton has 76 states and 113 transitions. Word has length 32 [2025-03-16 18:11:17,444 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:17,444 INFO L471 AbstractCegarLoop]: Abstraction has 76 states and 113 transitions. [2025-03-16 18:11:17,444 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:17,444 INFO L276 IsEmpty]: Start isEmpty. Operand 76 states and 113 transitions. [2025-03-16 18:11:17,444 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2025-03-16 18:11:17,444 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:17,444 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:17,450 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2025-03-16 18:11:17,648 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:17,649 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:17,649 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:17,649 INFO L85 PathProgramCache]: Analyzing trace with hash -908329914, now seen corresponding path program 2 times [2025-03-16 18:11:17,649 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:17,649 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2095941580] [2025-03-16 18:11:17,649 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:11:17,650 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:17,656 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 35 statements into 2 equivalence classes. [2025-03-16 18:11:17,663 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:17,666 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:11:17,666 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:17,742 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:17,743 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:17,745 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2095941580] [2025-03-16 18:11:17,745 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2095941580] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 18:11:17,745 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 18:11:17,745 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-16 18:11:17,746 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [18562532] [2025-03-16 18:11:17,746 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:11:17,746 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-16 18:11:17,746 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:17,746 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-16 18:11:17,746 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-16 18:11:17,746 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:17,834 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:17,835 INFO L93 Difference]: Finished difference Result 115 states and 177 transitions. [2025-03-16 18:11:17,838 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-16 18:11:17,839 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:17,839 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:17,841 INFO L225 Difference]: With dead ends: 115 [2025-03-16 18:11:17,841 INFO L226 Difference]: Without dead ends: 86 [2025-03-16 18:11:17,841 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:17,843 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:17,843 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:17,843 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 86 states. [2025-03-16 18:11:17,857 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 86 to 57. [2025-03-16 18:11:17,857 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:17,859 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 78 transitions. [2025-03-16 18:11:17,859 INFO L78 Accepts]: Start accepts. Automaton has 57 states and 78 transitions. Word has length 35 [2025-03-16 18:11:17,859 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:17,859 INFO L471 AbstractCegarLoop]: Abstraction has 57 states and 78 transitions. [2025-03-16 18:11:17,859 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:17,859 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 78 transitions. [2025-03-16 18:11:17,860 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2025-03-16 18:11:17,860 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:17,860 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:17,860 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4 [2025-03-16 18:11:17,860 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:17,860 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:17,861 INFO L85 PathProgramCache]: Analyzing trace with hash -1361869309, now seen corresponding path program 1 times [2025-03-16 18:11:17,861 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:17,861 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1751221870] [2025-03-16 18:11:17,861 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:17,861 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:17,864 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 37 statements into 1 equivalence classes. [2025-03-16 18:11:17,871 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 37 of 37 statements. [2025-03-16 18:11:17,871 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:17,871 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:17,872 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1706860550] [2025-03-16 18:11:17,872 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:17,872 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:17,872 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:17,879 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:17,880 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:17,905 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 37 statements into 1 equivalence classes. [2025-03-16 18:11:17,917 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 37 of 37 statements. [2025-03-16 18:11:17,917 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:17,917 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:17,918 INFO L256 TraceCheckSpWp]: Trace formula consists of 119 conjuncts, 21 conjuncts are in the unsatisfiable core [2025-03-16 18:11:17,919 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:18,004 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:18,005 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:18,048 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:18,048 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1751221870] [2025-03-16 18:11:18,049 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:18,049 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1706860550] [2025-03-16 18:11:18,049 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1706860550] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:11:18,049 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-16 18:11:18,049 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2025-03-16 18:11:18,049 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1784935903] [2025-03-16 18:11:18,049 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:18,049 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2025-03-16 18:11:18,049 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:18,050 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2025-03-16 18:11:18,050 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2025-03-16 18:11:18,050 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:18,164 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:18,164 INFO L93 Difference]: Finished difference Result 78 states and 109 transitions. [2025-03-16 18:11:18,164 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2025-03-16 18:11:18,164 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:18,165 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:18,165 INFO L225 Difference]: With dead ends: 78 [2025-03-16 18:11:18,165 INFO L226 Difference]: Without dead ends: 76 [2025-03-16 18:11:18,166 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:18,166 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:18,166 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:18,166 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 76 states. [2025-03-16 18:11:18,175 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 76 to 74. [2025-03-16 18:11:18,176 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:18,176 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 74 states to 74 states and 105 transitions. [2025-03-16 18:11:18,176 INFO L78 Accepts]: Start accepts. Automaton has 74 states and 105 transitions. Word has length 37 [2025-03-16 18:11:18,177 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:18,178 INFO L471 AbstractCegarLoop]: Abstraction has 74 states and 105 transitions. [2025-03-16 18:11:18,178 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:18,178 INFO L276 IsEmpty]: Start isEmpty. Operand 74 states and 105 transitions. [2025-03-16 18:11:18,179 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2025-03-16 18:11:18,179 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:18,180 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:18,186 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:18,384 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:18,384 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:18,384 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:18,384 INFO L85 PathProgramCache]: Analyzing trace with hash -1979591293, now seen corresponding path program 1 times [2025-03-16 18:11:18,385 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:18,385 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [565144918] [2025-03-16 18:11:18,385 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:18,385 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:18,388 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 42 statements into 1 equivalence classes. [2025-03-16 18:11:18,394 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 42 of 42 statements. [2025-03-16 18:11:18,394 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:18,394 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:18,395 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [719872228] [2025-03-16 18:11:18,395 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:18,395 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:18,395 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:18,397 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:18,398 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:18,423 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 42 statements into 1 equivalence classes. [2025-03-16 18:11:18,436 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 42 of 42 statements. [2025-03-16 18:11:18,436 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:18,436 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:18,437 INFO L256 TraceCheckSpWp]: Trace formula consists of 128 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-16 18:11:18,438 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:18,464 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:18,464 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-16 18:11:18,464 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:18,464 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [565144918] [2025-03-16 18:11:18,464 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:18,464 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [719872228] [2025-03-16 18:11:18,464 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [719872228] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 18:11:18,465 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 18:11:18,465 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-16 18:11:18,465 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1627985777] [2025-03-16 18:11:18,465 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:11:18,465 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-16 18:11:18,465 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:18,465 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-16 18:11:18,466 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-16 18:11:18,466 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:18,520 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:18,521 INFO L93 Difference]: Finished difference Result 103 states and 147 transitions. [2025-03-16 18:11:18,521 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-16 18:11:18,522 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:18,522 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:18,523 INFO L225 Difference]: With dead ends: 103 [2025-03-16 18:11:18,523 INFO L226 Difference]: Without dead ends: 101 [2025-03-16 18:11:18,523 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:18,524 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:18,524 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:18,525 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 101 states. [2025-03-16 18:11:18,542 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 101 to 97. [2025-03-16 18:11:18,543 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:18,545 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 97 states to 97 states and 141 transitions. [2025-03-16 18:11:18,545 INFO L78 Accepts]: Start accepts. Automaton has 97 states and 141 transitions. Word has length 42 [2025-03-16 18:11:18,545 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:18,545 INFO L471 AbstractCegarLoop]: Abstraction has 97 states and 141 transitions. [2025-03-16 18:11:18,546 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:18,546 INFO L276 IsEmpty]: Start isEmpty. Operand 97 states and 141 transitions. [2025-03-16 18:11:18,547 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2025-03-16 18:11:18,547 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:18,547 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:18,553 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:18,747 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:18,748 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:18,749 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:18,749 INFO L85 PathProgramCache]: Analyzing trace with hash 146539456, now seen corresponding path program 1 times [2025-03-16 18:11:18,749 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:18,749 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1228729234] [2025-03-16 18:11:18,749 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:18,749 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:18,754 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 44 statements into 1 equivalence classes. [2025-03-16 18:11:18,764 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 44 of 44 statements. [2025-03-16 18:11:18,764 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:18,764 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:18,764 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [949123034] [2025-03-16 18:11:18,764 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:18,764 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:18,764 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:18,768 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:18,769 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:18,789 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 44 statements into 1 equivalence classes. [2025-03-16 18:11:18,803 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 44 of 44 statements. [2025-03-16 18:11:18,803 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:18,803 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:18,804 INFO L256 TraceCheckSpWp]: Trace formula consists of 119 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-16 18:11:18,805 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:18,829 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:18,829 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-16 18:11:18,829 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:18,829 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1228729234] [2025-03-16 18:11:18,829 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:18,829 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [949123034] [2025-03-16 18:11:18,830 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [949123034] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 18:11:18,830 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 18:11:18,830 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-16 18:11:18,830 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [405118116] [2025-03-16 18:11:18,830 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:11:18,830 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-16 18:11:18,830 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:18,830 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-16 18:11:18,830 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-16 18:11:18,831 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:18,889 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:18,890 INFO L93 Difference]: Finished difference Result 147 states and 230 transitions. [2025-03-16 18:11:18,891 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-16 18:11:18,891 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:18,891 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:18,892 INFO L225 Difference]: With dead ends: 147 [2025-03-16 18:11:18,892 INFO L226 Difference]: Without dead ends: 145 [2025-03-16 18:11:18,892 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:18,892 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:18,893 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:18,893 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 145 states. [2025-03-16 18:11:18,914 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 145 to 133. [2025-03-16 18:11:18,915 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:18,916 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 133 states to 133 states and 208 transitions. [2025-03-16 18:11:18,916 INFO L78 Accepts]: Start accepts. Automaton has 133 states and 208 transitions. Word has length 44 [2025-03-16 18:11:18,916 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:18,916 INFO L471 AbstractCegarLoop]: Abstraction has 133 states and 208 transitions. [2025-03-16 18:11:18,916 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:18,916 INFO L276 IsEmpty]: Start isEmpty. Operand 133 states and 208 transitions. [2025-03-16 18:11:18,917 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2025-03-16 18:11:18,917 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:18,917 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:18,923 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:19,118 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:19,119 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:19,119 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:19,120 INFO L85 PathProgramCache]: Analyzing trace with hash 89640629, now seen corresponding path program 1 times [2025-03-16 18:11:19,120 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:19,120 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2003570930] [2025-03-16 18:11:19,120 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:19,120 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:19,124 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 54 statements into 1 equivalence classes. [2025-03-16 18:11:19,140 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 54 of 54 statements. [2025-03-16 18:11:19,140 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:19,140 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:19,141 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1950356955] [2025-03-16 18:11:19,141 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:19,141 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:19,141 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:19,144 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:19,145 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:19,168 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 54 statements into 1 equivalence classes. [2025-03-16 18:11:19,183 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 54 of 54 statements. [2025-03-16 18:11:19,183 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:19,183 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:19,184 INFO L256 TraceCheckSpWp]: Trace formula consists of 148 conjuncts, 51 conjuncts are in the unsatisfiable core [2025-03-16 18:11:19,186 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:19,590 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:19,591 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:19,927 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:19,927 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:19,927 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2003570930] [2025-03-16 18:11:19,927 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:19,927 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1950356955] [2025-03-16 18:11:19,927 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1950356955] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:11:19,927 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:11:19,927 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 11] total 23 [2025-03-16 18:11:19,927 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [710796870] [2025-03-16 18:11:19,928 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:19,928 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2025-03-16 18:11:19,928 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:19,928 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2025-03-16 18:11:19,929 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=77, Invalid=429, Unknown=0, NotChecked=0, Total=506 [2025-03-16 18:11:19,929 INFO L87 Difference]: Start difference. First operand 133 states and 208 transitions. Second operand has 23 states, 21 states have (on average 1.5238095238095237) internal successors, (32), 20 states have internal predecessors, (32), 6 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2025-03-16 18:11:21,715 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:21,715 INFO L93 Difference]: Finished difference Result 357 states and 579 transitions. [2025-03-16 18:11:21,718 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 32 states. [2025-03-16 18:11:21,718 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:21,718 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:21,722 INFO L225 Difference]: With dead ends: 357 [2025-03-16 18:11:21,722 INFO L226 Difference]: Without dead ends: 275 [2025-03-16 18:11:21,723 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 129 GetRequests, 85 SyntacticMatches, 0 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 434 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=398, Invalid=1672, Unknown=0, NotChecked=0, Total=2070 [2025-03-16 18:11:21,724 INFO L435 NwaCegarLoop]: 22 mSDtfsCounter, 126 mSDsluCounter, 233 mSDsCounter, 0 mSdLazyCounter, 640 mSolverCounterSat, 126 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 134 SdHoareTripleChecker+Valid, 255 SdHoareTripleChecker+Invalid, 766 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 126 IncrementalHoareTripleChecker+Valid, 640 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:21,724 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.8s Time] [2025-03-16 18:11:21,724 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 275 states. [2025-03-16 18:11:21,814 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 275 to 203. [2025-03-16 18:11:21,815 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:21,817 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 203 states to 203 states and 314 transitions. [2025-03-16 18:11:21,818 INFO L78 Accepts]: Start accepts. Automaton has 203 states and 314 transitions. Word has length 54 [2025-03-16 18:11:21,818 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:21,818 INFO L471 AbstractCegarLoop]: Abstraction has 203 states and 314 transitions. [2025-03-16 18:11:21,818 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:21,818 INFO L276 IsEmpty]: Start isEmpty. Operand 203 states and 314 transitions. [2025-03-16 18:11:21,820 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2025-03-16 18:11:21,820 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:21,820 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:21,827 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2025-03-16 18:11:22,025 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:22,025 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:22,025 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:22,025 INFO L85 PathProgramCache]: Analyzing trace with hash 107169448, now seen corresponding path program 1 times [2025-03-16 18:11:22,025 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:22,026 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [785389156] [2025-03-16 18:11:22,026 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:22,026 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:22,029 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 58 statements into 1 equivalence classes. [2025-03-16 18:11:22,046 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 58 of 58 statements. [2025-03-16 18:11:22,047 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:22,047 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:22,048 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [643348688] [2025-03-16 18:11:22,048 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:22,049 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:22,049 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:22,050 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:11:22,052 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2025-03-16 18:11:22,073 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 58 statements into 1 equivalence classes. [2025-03-16 18:11:22,093 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 58 of 58 statements. [2025-03-16 18:11:22,093 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:22,093 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:22,095 INFO L256 TraceCheckSpWp]: Trace formula consists of 174 conjuncts, 49 conjuncts are in the unsatisfiable core [2025-03-16 18:11:22,097 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:22,460 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:22,460 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:22,570 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:22,570 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:22,570 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [785389156] [2025-03-16 18:11:22,570 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:22,570 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [643348688] [2025-03-16 18:11:22,570 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [643348688] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:11:22,570 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:11:22,570 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 8] total 22 [2025-03-16 18:11:22,571 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [352554621] [2025-03-16 18:11:22,571 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:22,571 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2025-03-16 18:11:22,571 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:22,571 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2025-03-16 18:11:22,571 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=67, Invalid=395, Unknown=0, NotChecked=0, Total=462 [2025-03-16 18:11:22,572 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:23,586 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:23,586 INFO L93 Difference]: Finished difference Result 254 states and 393 transitions. [2025-03-16 18:11:23,586 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2025-03-16 18:11:23,586 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:23,587 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:23,589 INFO L225 Difference]: With dead ends: 254 [2025-03-16 18:11:23,589 INFO L226 Difference]: Without dead ends: 252 [2025-03-16 18:11:23,590 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:23,590 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:23,591 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:23,592 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 252 states. [2025-03-16 18:11:23,658 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 252 to 211. [2025-03-16 18:11:23,659 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:23,660 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 211 states to 211 states and 320 transitions. [2025-03-16 18:11:23,660 INFO L78 Accepts]: Start accepts. Automaton has 211 states and 320 transitions. Word has length 58 [2025-03-16 18:11:23,661 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:23,661 INFO L471 AbstractCegarLoop]: Abstraction has 211 states and 320 transitions. [2025-03-16 18:11:23,661 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:23,661 INFO L276 IsEmpty]: Start isEmpty. Operand 211 states and 320 transitions. [2025-03-16 18:11:23,661 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 66 [2025-03-16 18:11:23,661 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:23,662 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:23,668 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:23,866 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:23,866 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:23,866 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:23,866 INFO L85 PathProgramCache]: Analyzing trace with hash 2061499091, now seen corresponding path program 1 times [2025-03-16 18:11:23,866 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:23,866 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1741347911] [2025-03-16 18:11:23,867 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:23,867 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:23,869 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 65 statements into 1 equivalence classes. [2025-03-16 18:11:23,877 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 65 of 65 statements. [2025-03-16 18:11:23,879 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:23,879 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:23,880 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [630579489] [2025-03-16 18:11:23,880 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:23,880 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:23,880 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:23,882 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:23,884 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:23,904 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 65 statements into 1 equivalence classes. [2025-03-16 18:11:23,917 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 65 of 65 statements. [2025-03-16 18:11:23,917 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:23,917 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:23,918 INFO L256 TraceCheckSpWp]: Trace formula consists of 160 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-03-16 18:11:23,919 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:23,970 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:23,970 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:24,024 INFO L134 CoverageAnalysis]: Checked inductivity of 126 backedges. 14 proven. 0 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2025-03-16 18:11:24,025 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:24,025 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1741347911] [2025-03-16 18:11:24,025 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:24,025 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [630579489] [2025-03-16 18:11:24,025 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [630579489] provided 1 perfect and 1 imperfect interpolant sequences [2025-03-16 18:11:24,025 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-16 18:11:24,025 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2025-03-16 18:11:24,025 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1031184251] [2025-03-16 18:11:24,025 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:11:24,025 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-16 18:11:24,025 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:24,026 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-16 18:11:24,026 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2025-03-16 18:11:24,026 INFO L87 Difference]: Start difference. First operand 211 states and 320 transitions. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2025-03-16 18:11:24,110 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:24,110 INFO L93 Difference]: Finished difference Result 217 states and 325 transitions. [2025-03-16 18:11:24,110 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-16 18:11:24,111 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) Word has length 65 [2025-03-16 18:11:24,111 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:24,114 INFO L225 Difference]: With dead ends: 217 [2025-03-16 18:11:24,114 INFO L226 Difference]: Without dead ends: 215 [2025-03-16 18:11:24,114 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 129 GetRequests, 121 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2025-03-16 18:11:24,115 INFO L435 NwaCegarLoop]: 33 mSDtfsCounter, 4 mSDsluCounter, 79 mSDsCounter, 0 mSdLazyCounter, 32 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 112 SdHoareTripleChecker+Invalid, 32 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 32 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:24,115 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 112 Invalid, 32 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 18:11:24,116 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 215 states. [2025-03-16 18:11:24,176 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 215 to 215. [2025-03-16 18:11:24,176 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:24,177 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 215 states to 215 states and 323 transitions. [2025-03-16 18:11:24,178 INFO L78 Accepts]: Start accepts. Automaton has 215 states and 323 transitions. Word has length 65 [2025-03-16 18:11:24,178 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:24,178 INFO L471 AbstractCegarLoop]: Abstraction has 215 states and 323 transitions. [2025-03-16 18:11:24,178 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:24,178 INFO L276 IsEmpty]: Start isEmpty. Operand 215 states and 323 transitions. [2025-03-16 18:11:24,178 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 64 [2025-03-16 18:11:24,178 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:24,178 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:24,184 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2025-03-16 18:11:24,379 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:24,379 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:24,379 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:24,379 INFO L85 PathProgramCache]: Analyzing trace with hash 1341574078, now seen corresponding path program 2 times [2025-03-16 18:11:24,379 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:24,379 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [373996857] [2025-03-16 18:11:24,380 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:11:24,380 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:24,383 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 63 statements into 2 equivalence classes. [2025-03-16 18:11:24,402 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:24,402 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:11:24,402 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:24,404 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1377619870] [2025-03-16 18:11:24,405 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:11:24,405 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:24,405 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:24,406 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:24,408 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:24,430 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 63 statements into 2 equivalence classes. [2025-03-16 18:11:24,451 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:24,451 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:11:24,452 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:24,453 INFO L256 TraceCheckSpWp]: Trace formula consists of 183 conjuncts, 65 conjuncts are in the unsatisfiable core [2025-03-16 18:11:24,455 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:24,909 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:24,909 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:25,457 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:25,457 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:25,457 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [373996857] [2025-03-16 18:11:25,457 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:25,457 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1377619870] [2025-03-16 18:11:25,457 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1377619870] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:11:25,457 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:11:25,457 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 15] total 31 [2025-03-16 18:11:25,457 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1279831668] [2025-03-16 18:11:25,457 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:25,458 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 31 states [2025-03-16 18:11:25,458 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:25,458 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2025-03-16 18:11:25,458 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=139, Invalid=791, Unknown=0, NotChecked=0, Total=930 [2025-03-16 18:11:25,458 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:28,153 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:28,153 INFO L93 Difference]: Finished difference Result 399 states and 591 transitions. [2025-03-16 18:11:28,154 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 39 states. [2025-03-16 18:11:28,154 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:28,154 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:28,156 INFO L225 Difference]: With dead ends: 399 [2025-03-16 18:11:28,156 INFO L226 Difference]: Without dead ends: 334 [2025-03-16 18:11:28,157 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 153 GetRequests, 95 SyntacticMatches, 0 SemanticMatches, 58 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 780 ImplicationChecksByTransitivity, 1.9s TimeCoverageRelationStatistics Valid=678, Invalid=2862, Unknown=0, NotChecked=0, Total=3540 [2025-03-16 18:11:28,157 INFO L435 NwaCegarLoop]: 27 mSDtfsCounter, 144 mSDsluCounter, 359 mSDsCounter, 0 mSdLazyCounter, 939 mSolverCounterSat, 177 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.1s 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.2s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:28,157 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.2s Time] [2025-03-16 18:11:28,157 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 334 states. [2025-03-16 18:11:28,255 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 334 to 287. [2025-03-16 18:11:28,256 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:28,257 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 287 states to 287 states and 424 transitions. [2025-03-16 18:11:28,257 INFO L78 Accepts]: Start accepts. Automaton has 287 states and 424 transitions. Word has length 63 [2025-03-16 18:11:28,257 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:28,258 INFO L471 AbstractCegarLoop]: Abstraction has 287 states and 424 transitions. [2025-03-16 18:11:28,258 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:28,258 INFO L276 IsEmpty]: Start isEmpty. Operand 287 states and 424 transitions. [2025-03-16 18:11:28,258 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 79 [2025-03-16 18:11:28,258 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:28,258 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:28,264 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2025-03-16 18:11:28,459 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:28,459 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:28,459 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:28,459 INFO L85 PathProgramCache]: Analyzing trace with hash 408526629, now seen corresponding path program 1 times [2025-03-16 18:11:28,460 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:28,460 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [110195322] [2025-03-16 18:11:28,460 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:28,460 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:28,465 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 78 statements into 1 equivalence classes. [2025-03-16 18:11:28,476 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 78 of 78 statements. [2025-03-16 18:11:28,477 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:28,477 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:28,478 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1184095553] [2025-03-16 18:11:28,481 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:28,481 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:28,481 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:28,483 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:28,483 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:28,507 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 78 statements into 1 equivalence classes. [2025-03-16 18:11:28,530 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 78 of 78 statements. [2025-03-16 18:11:28,530 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:28,530 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:28,531 INFO L256 TraceCheckSpWp]: Trace formula consists of 207 conjuncts, 70 conjuncts are in the unsatisfiable core [2025-03-16 18:11:28,533 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:29,104 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:29,104 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:29,813 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:29,813 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:29,813 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [110195322] [2025-03-16 18:11:29,813 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:29,813 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1184095553] [2025-03-16 18:11:29,813 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1184095553] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:11:29,813 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:11:29,813 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 17] total 35 [2025-03-16 18:11:29,813 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1370461730] [2025-03-16 18:11:29,813 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:29,814 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 35 states [2025-03-16 18:11:29,814 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:29,814 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 35 interpolants. [2025-03-16 18:11:29,814 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=154, Invalid=1036, Unknown=0, NotChecked=0, Total=1190 [2025-03-16 18:11:29,815 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:45,042 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:45,042 INFO L93 Difference]: Finished difference Result 519 states and 820 transitions. [2025-03-16 18:11:45,043 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 93 states. [2025-03-16 18:11:45,043 INFO L78 Accepts]: Start accepts. Automaton has has 35 states, 31 states have (on average 1.4516129032258065) internal successors, (45), 33 states have internal predecessors, (45), 10 states have call successors, (23), 3 states have call predecessors, (23), 3 states have return successors, (22), 8 states have call predecessors, (22), 8 states have call successors, (22) Word has length 78 [2025-03-16 18:11:45,043 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:45,046 INFO L225 Difference]: With dead ends: 519 [2025-03-16 18:11:45,046 INFO L226 Difference]: Without dead ends: 511 [2025-03-16 18:11:45,048 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 237 GetRequests, 121 SyntacticMatches, 0 SemanticMatches, 116 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4138 ImplicationChecksByTransitivity, 12.5s TimeCoverageRelationStatistics Valid=2405, Invalid=11401, Unknown=0, NotChecked=0, Total=13806 [2025-03-16 18:11:45,049 INFO L435 NwaCegarLoop]: 50 mSDtfsCounter, 199 mSDsluCounter, 699 mSDsCounter, 0 mSdLazyCounter, 1955 mSolverCounterSat, 289 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 199 SdHoareTripleChecker+Valid, 749 SdHoareTripleChecker+Invalid, 2244 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 289 IncrementalHoareTripleChecker+Valid, 1955 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.0s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:45,049 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [199 Valid, 749 Invalid, 2244 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [289 Valid, 1955 Invalid, 0 Unknown, 0 Unchecked, 3.0s Time] [2025-03-16 18:11:45,050 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 511 states. [2025-03-16 18:11:45,284 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 511 to 394. [2025-03-16 18:11:45,285 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 394 states, 192 states have (on average 1.3125) internal successors, (252), 206 states have internal predecessors, (252), 177 states have call successors, (177), 24 states have call predecessors, (177), 24 states have return successors, (176), 163 states have call predecessors, (176), 176 states have call successors, (176) [2025-03-16 18:11:45,287 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 394 states to 394 states and 605 transitions. [2025-03-16 18:11:45,287 INFO L78 Accepts]: Start accepts. Automaton has 394 states and 605 transitions. Word has length 78 [2025-03-16 18:11:45,287 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:45,287 INFO L471 AbstractCegarLoop]: Abstraction has 394 states and 605 transitions. [2025-03-16 18:11:45,287 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 35 states, 31 states have (on average 1.4516129032258065) internal successors, (45), 33 states have internal predecessors, (45), 10 states have call successors, (23), 3 states have call predecessors, (23), 3 states have return successors, (22), 8 states have call predecessors, (22), 8 states have call successors, (22) [2025-03-16 18:11:45,287 INFO L276 IsEmpty]: Start isEmpty. Operand 394 states and 605 transitions. [2025-03-16 18:11:45,288 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 84 [2025-03-16 18:11:45,288 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:45,288 INFO L218 NwaCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:11:45,294 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2025-03-16 18:11:45,489 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2025-03-16 18:11:45,489 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:45,489 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:45,489 INFO L85 PathProgramCache]: Analyzing trace with hash -1408173133, now seen corresponding path program 2 times [2025-03-16 18:11:45,490 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:45,490 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1795246204] [2025-03-16 18:11:45,490 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:11:45,490 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:45,493 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 83 statements into 2 equivalence classes. [2025-03-16 18:11:45,502 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 83 of 83 statements. [2025-03-16 18:11:45,502 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:11:45,503 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:45,665 INFO L134 CoverageAnalysis]: Checked inductivity of 177 backedges. 28 proven. 11 refuted. 0 times theorem prover too weak. 138 trivial. 0 not checked. [2025-03-16 18:11:45,665 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:45,665 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1795246204] [2025-03-16 18:11:45,665 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1795246204] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:11:45,665 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1616948302] [2025-03-16 18:11:45,665 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:11:45,666 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:45,666 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:45,668 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:11:45,670 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2025-03-16 18:11:45,696 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 83 statements into 2 equivalence classes. [2025-03-16 18:11:45,728 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 83 of 83 statements. [2025-03-16 18:11:45,728 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:11:45,728 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:45,729 INFO L256 TraceCheckSpWp]: Trace formula consists of 230 conjuncts, 10 conjuncts are in the unsatisfiable core [2025-03-16 18:11:45,730 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:45,784 INFO L134 CoverageAnalysis]: Checked inductivity of 177 backedges. 28 proven. 11 refuted. 0 times theorem prover too weak. 138 trivial. 0 not checked. [2025-03-16 18:11:45,784 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:45,874 INFO L134 CoverageAnalysis]: Checked inductivity of 177 backedges. 28 proven. 11 refuted. 0 times theorem prover too weak. 138 trivial. 0 not checked. [2025-03-16 18:11:45,874 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1616948302] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:11:45,874 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 18:11:45,874 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10, 10] total 13 [2025-03-16 18:11:45,874 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [711829774] [2025-03-16 18:11:45,874 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:45,875 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2025-03-16 18:11:45,875 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:45,875 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2025-03-16 18:11:45,875 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=129, Unknown=0, NotChecked=0, Total=156 [2025-03-16 18:11:45,875 INFO L87 Difference]: Start difference. First operand 394 states and 605 transitions. Second operand has 13 states, 13 states have (on average 2.5384615384615383) internal successors, (33), 13 states have internal predecessors, (33), 4 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) [2025-03-16 18:11:46,389 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:46,390 INFO L93 Difference]: Finished difference Result 651 states and 988 transitions. [2025-03-16 18:11:46,390 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2025-03-16 18:11:46,390 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 2.5384615384615383) internal successors, (33), 13 states have internal predecessors, (33), 4 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) Word has length 83 [2025-03-16 18:11:46,390 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:46,392 INFO L225 Difference]: With dead ends: 651 [2025-03-16 18:11:46,392 INFO L226 Difference]: Without dead ends: 411 [2025-03-16 18:11:46,393 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 199 GetRequests, 162 SyntacticMatches, 8 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 164 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=214, Invalid=716, Unknown=0, NotChecked=0, Total=930 [2025-03-16 18:11:46,394 INFO L435 NwaCegarLoop]: 45 mSDtfsCounter, 65 mSDsluCounter, 276 mSDsCounter, 0 mSdLazyCounter, 290 mSolverCounterSat, 91 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 69 SdHoareTripleChecker+Valid, 321 SdHoareTripleChecker+Invalid, 381 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 91 IncrementalHoareTripleChecker+Valid, 290 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:46,394 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [69 Valid, 321 Invalid, 381 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [91 Valid, 290 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-16 18:11:46,394 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 411 states. [2025-03-16 18:11:46,576 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 411 to 306. [2025-03-16 18:11:46,577 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 306 states, 163 states have (on average 1.2822085889570551) internal successors, (209), 165 states have internal predecessors, (209), 119 states have call successors, (119), 23 states have call predecessors, (119), 23 states have return successors, (118), 117 states have call predecessors, (118), 118 states have call successors, (118) [2025-03-16 18:11:46,581 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 306 states to 306 states and 446 transitions. [2025-03-16 18:11:46,581 INFO L78 Accepts]: Start accepts. Automaton has 306 states and 446 transitions. Word has length 83 [2025-03-16 18:11:46,581 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:46,581 INFO L471 AbstractCegarLoop]: Abstraction has 306 states and 446 transitions. [2025-03-16 18:11:46,581 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 2.5384615384615383) internal successors, (33), 13 states have internal predecessors, (33), 4 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) [2025-03-16 18:11:46,582 INFO L276 IsEmpty]: Start isEmpty. Operand 306 states and 446 transitions. [2025-03-16 18:11:46,582 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 97 [2025-03-16 18:11:46,582 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:46,583 INFO L218 NwaCegarLoop]: trace histogram [13, 12, 12, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:11:46,590 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:11:46,783 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2025-03-16 18:11:46,783 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:46,783 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:46,784 INFO L85 PathProgramCache]: Analyzing trace with hash -807522155, now seen corresponding path program 2 times [2025-03-16 18:11:46,784 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:46,784 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [443230404] [2025-03-16 18:11:46,784 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:11:46,784 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:46,788 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 96 statements into 2 equivalence classes. [2025-03-16 18:11:46,802 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 96 of 96 statements. [2025-03-16 18:11:46,802 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:11:46,802 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:46,804 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1378015379] [2025-03-16 18:11:46,804 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:11:46,804 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:46,804 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:46,806 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:11:46,807 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2025-03-16 18:11:46,831 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 96 statements into 2 equivalence classes. [2025-03-16 18:11:46,853 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 96 of 96 statements. [2025-03-16 18:11:46,853 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:11:46,853 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:46,854 INFO L256 TraceCheckSpWp]: Trace formula consists of 230 conjuncts, 47 conjuncts are in the unsatisfiable core [2025-03-16 18:11:46,856 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:47,266 INFO L134 CoverageAnalysis]: Checked inductivity of 329 backedges. 24 proven. 17 refuted. 0 times theorem prover too weak. 288 trivial. 0 not checked. [2025-03-16 18:11:47,266 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:47,720 INFO L134 CoverageAnalysis]: Checked inductivity of 329 backedges. 24 proven. 17 refuted. 0 times theorem prover too weak. 288 trivial. 0 not checked. [2025-03-16 18:11:47,721 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:47,721 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [443230404] [2025-03-16 18:11:47,721 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:47,721 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1378015379] [2025-03-16 18:11:47,721 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1378015379] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:11:47,721 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:11:47,721 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 22 [2025-03-16 18:11:47,721 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [186501229] [2025-03-16 18:11:47,721 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:47,721 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2025-03-16 18:11:47,721 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:47,722 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2025-03-16 18:11:47,722 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=66, Invalid=396, Unknown=0, NotChecked=0, Total=462 [2025-03-16 18:11:47,722 INFO L87 Difference]: Start difference. First operand 306 states and 446 transitions. Second operand has 22 states, 20 states have (on average 1.55) internal successors, (31), 21 states have internal predecessors, (31), 9 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (28), 7 states have call predecessors, (28), 7 states have call successors, (28) [2025-03-16 18:11:52,377 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:52,377 INFO L93 Difference]: Finished difference Result 510 states and 789 transitions. [2025-03-16 18:11:52,378 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 60 states. [2025-03-16 18:11:52,378 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 20 states have (on average 1.55) internal successors, (31), 21 states have internal predecessors, (31), 9 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (28), 7 states have call predecessors, (28), 7 states have call successors, (28) Word has length 96 [2025-03-16 18:11:52,378 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:52,380 INFO L225 Difference]: With dead ends: 510 [2025-03-16 18:11:52,380 INFO L226 Difference]: Without dead ends: 502 [2025-03-16 18:11:52,382 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 239 GetRequests, 168 SyntacticMatches, 2 SemanticMatches, 69 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1406 ImplicationChecksByTransitivity, 3.0s TimeCoverageRelationStatistics Valid=867, Invalid=4103, Unknown=0, NotChecked=0, Total=4970 [2025-03-16 18:11:52,382 INFO L435 NwaCegarLoop]: 72 mSDtfsCounter, 123 mSDsluCounter, 731 mSDsCounter, 0 mSdLazyCounter, 1176 mSolverCounterSat, 186 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.6s 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.6s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:52,382 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.6s Time] [2025-03-16 18:11:52,383 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 502 states. [2025-03-16 18:11:52,580 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 502 to 342. [2025-03-16 18:11:52,581 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 342 states, 174 states have (on average 1.3045977011494252) internal successors, (227), 176 states have internal predecessors, (227), 143 states have call successors, (143), 24 states have call predecessors, (143), 24 states have return successors, (142), 141 states have call predecessors, (142), 142 states have call successors, (142) [2025-03-16 18:11:52,582 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 342 states to 342 states and 512 transitions. [2025-03-16 18:11:52,582 INFO L78 Accepts]: Start accepts. Automaton has 342 states and 512 transitions. Word has length 96 [2025-03-16 18:11:52,583 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:52,583 INFO L471 AbstractCegarLoop]: Abstraction has 342 states and 512 transitions. [2025-03-16 18:11:52,583 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 20 states have (on average 1.55) internal successors, (31), 21 states have internal predecessors, (31), 9 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (28), 7 states have call predecessors, (28), 7 states have call successors, (28) [2025-03-16 18:11:52,583 INFO L276 IsEmpty]: Start isEmpty. Operand 342 states and 512 transitions. [2025-03-16 18:11:52,584 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 99 [2025-03-16 18:11:52,584 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:52,584 INFO L218 NwaCegarLoop]: trace histogram [13, 12, 12, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:11:52,591 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:11:52,784 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2025-03-16 18:11:52,784 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:52,784 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:52,784 INFO L85 PathProgramCache]: Analyzing trace with hash 1069370314, now seen corresponding path program 3 times [2025-03-16 18:11:52,785 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:52,785 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1277746751] [2025-03-16 18:11:52,785 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 18:11:52,785 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:52,788 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 98 statements into 11 equivalence classes. [2025-03-16 18:11:52,815 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 11 check-sat command(s) and asserted 98 of 98 statements. [2025-03-16 18:11:52,816 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 11 check-sat command(s) [2025-03-16 18:11:52,816 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:52,817 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1657110345] [2025-03-16 18:11:52,817 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 18:11:52,817 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:52,817 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:52,819 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:11:52,820 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2025-03-16 18:11:52,842 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 98 statements into 11 equivalence classes. [2025-03-16 18:11:52,858 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) and asserted 62 of 98 statements. [2025-03-16 18:11:52,859 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2025-03-16 18:11:52,859 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:52,860 INFO L256 TraceCheckSpWp]: Trace formula consists of 167 conjuncts, 61 conjuncts are in the unsatisfiable core [2025-03-16 18:11:52,861 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:53,503 INFO L134 CoverageAnalysis]: Checked inductivity of 332 backedges. 55 proven. 27 refuted. 0 times theorem prover too weak. 250 trivial. 0 not checked. [2025-03-16 18:11:53,503 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:54,015 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:54,016 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1277746751] [2025-03-16 18:11:54,016 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:54,016 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1657110345] [2025-03-16 18:11:54,016 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1657110345] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:11:54,016 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-16 18:11:54,016 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19] total 19 [2025-03-16 18:11:54,016 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1010342505] [2025-03-16 18:11:54,016 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:54,016 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2025-03-16 18:11:54,016 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:54,016 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2025-03-16 18:11:54,017 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=126, Invalid=686, Unknown=0, NotChecked=0, Total=812 [2025-03-16 18:11:54,017 INFO L87 Difference]: Start difference. First operand 342 states and 512 transitions. Second operand has 19 states, 18 states have (on average 1.6111111111111112) internal successors, (29), 16 states have internal predecessors, (29), 4 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (13), 5 states have call predecessors, (13), 3 states have call successors, (13) [2025-03-16 18:11:54,777 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:54,777 INFO L93 Difference]: Finished difference Result 428 states and 632 transitions. [2025-03-16 18:11:54,778 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2025-03-16 18:11:54,778 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 18 states have (on average 1.6111111111111112) internal successors, (29), 16 states have internal predecessors, (29), 4 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (13), 5 states have call predecessors, (13), 3 states have call successors, (13) Word has length 98 [2025-03-16 18:11:54,778 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:54,780 INFO L225 Difference]: With dead ends: 428 [2025-03-16 18:11:54,780 INFO L226 Difference]: Without dead ends: 421 [2025-03-16 18:11:54,780 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:11:54,781 INFO L435 NwaCegarLoop]: 26 mSDtfsCounter, 45 mSDsluCounter, 178 mSDsCounter, 0 mSdLazyCounter, 615 mSolverCounterSat, 36 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 57 SdHoareTripleChecker+Valid, 204 SdHoareTripleChecker+Invalid, 651 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 36 IncrementalHoareTripleChecker+Valid, 615 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:54,781 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [57 Valid, 204 Invalid, 651 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [36 Valid, 615 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-03-16 18:11:54,781 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 421 states. [2025-03-16 18:11:55,037 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 421 to 410. [2025-03-16 18:11:55,038 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 410 states, 209 states have (on average 1.30622009569378) internal successors, (273), 211 states have internal predecessors, (273), 171 states have call successors, (171), 29 states have call predecessors, (171), 29 states have return successors, (170), 169 states have call predecessors, (170), 170 states have call successors, (170) [2025-03-16 18:11:55,040 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 410 states to 410 states and 614 transitions. [2025-03-16 18:11:55,040 INFO L78 Accepts]: Start accepts. Automaton has 410 states and 614 transitions. Word has length 98 [2025-03-16 18:11:55,041 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:55,041 INFO L471 AbstractCegarLoop]: Abstraction has 410 states and 614 transitions. [2025-03-16 18:11:55,041 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 18 states have (on average 1.6111111111111112) internal successors, (29), 16 states have internal predecessors, (29), 4 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (13), 5 states have call predecessors, (13), 3 states have call successors, (13) [2025-03-16 18:11:55,041 INFO L276 IsEmpty]: Start isEmpty. Operand 410 states and 614 transitions. [2025-03-16 18:11:55,042 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 102 [2025-03-16 18:11:55,042 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:55,042 INFO L218 NwaCegarLoop]: trace histogram [13, 12, 12, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:11:55,048 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Ended with exit code 0 [2025-03-16 18:11:55,242 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable15,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:55,243 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:55,243 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:55,243 INFO L85 PathProgramCache]: Analyzing trace with hash 311264781, now seen corresponding path program 4 times [2025-03-16 18:11:55,243 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:55,243 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1930737690] [2025-03-16 18:11:55,243 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-16 18:11:55,243 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:55,247 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 101 statements into 2 equivalence classes. [2025-03-16 18:11:55,265 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 101 of 101 statements. [2025-03-16 18:11:55,265 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-03-16 18:11:55,265 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:55,266 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [651118414] [2025-03-16 18:11:55,266 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-16 18:11:55,266 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:55,266 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:55,268 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:11:55,269 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2025-03-16 18:11:55,292 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 101 statements into 2 equivalence classes. [2025-03-16 18:11:55,316 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:11:55,316 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-03-16 18:11:55,316 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:55,318 INFO L256 TraceCheckSpWp]: Trace formula consists of 222 conjuncts, 75 conjuncts are in the unsatisfiable core [2025-03-16 18:11:55,320 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:55,933 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:11:55,933 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:56,450 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:11:56,450 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:56,450 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1930737690] [2025-03-16 18:11:56,450 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:56,450 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [651118414] [2025-03-16 18:11:56,450 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [651118414] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:11:56,450 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:11:56,450 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 16] total 33 [2025-03-16 18:11:56,450 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [102704021] [2025-03-16 18:11:56,450 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:56,451 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 33 states [2025-03-16 18:11:56,451 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:56,451 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2025-03-16 18:11:56,451 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=137, Invalid=919, Unknown=0, NotChecked=0, Total=1056 [2025-03-16 18:11:56,451 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:06,399 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:12:06,399 INFO L93 Difference]: Finished difference Result 676 states and 1057 transitions. [2025-03-16 18:12:06,399 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 93 states. [2025-03-16 18:12:06,399 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:06,399 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:12:06,402 INFO L225 Difference]: With dead ends: 676 [2025-03-16 18:12:06,402 INFO L226 Difference]: Without dead ends: 668 [2025-03-16 18:12:06,405 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 284 GetRequests, 169 SyntacticMatches, 0 SemanticMatches, 115 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4029 ImplicationChecksByTransitivity, 7.4s TimeCoverageRelationStatistics Valid=2038, Invalid=11534, Unknown=0, NotChecked=0, Total=13572 [2025-03-16 18:12:06,405 INFO L435 NwaCegarLoop]: 37 mSDtfsCounter, 293 mSDsluCounter, 614 mSDsCounter, 0 mSdLazyCounter, 1471 mSolverCounterSat, 434 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.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, 2.4s IncrementalHoareTripleChecker+Time [2025-03-16 18:12:06,405 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [293 Valid, 651 Invalid, 1905 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [434 Valid, 1471 Invalid, 0 Unknown, 0 Unchecked, 2.4s Time] [2025-03-16 18:12:06,405 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 668 states. [2025-03-16 18:12:06,842 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 668 to 515. [2025-03-16 18:12:06,843 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:06,845 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 515 states to 515 states and 791 transitions. [2025-03-16 18:12:06,846 INFO L78 Accepts]: Start accepts. Automaton has 515 states and 791 transitions. Word has length 101 [2025-03-16 18:12:06,846 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:12:06,846 INFO L471 AbstractCegarLoop]: Abstraction has 515 states and 791 transitions. [2025-03-16 18:12:06,846 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:06,846 INFO L276 IsEmpty]: Start isEmpty. Operand 515 states and 791 transitions. [2025-03-16 18:12:06,847 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 105 [2025-03-16 18:12:06,847 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:12:06,848 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:06,854 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2025-03-16 18:12:07,052 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:07,052 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:12:07,052 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:12:07,052 INFO L85 PathProgramCache]: Analyzing trace with hash -1999255606, now seen corresponding path program 5 times [2025-03-16 18:12:07,052 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:12:07,052 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1747008353] [2025-03-16 18:12:07,052 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-03-16 18:12:07,053 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:12:07,057 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 104 statements into 8 equivalence classes. [2025-03-16 18:12:07,076 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:07,077 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 8 check-sat command(s) [2025-03-16 18:12:07,077 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:12:07,078 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [711371071] [2025-03-16 18:12:07,078 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-03-16 18:12:07,078 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:12:07,078 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:12:07,080 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:07,082 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:07,108 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 104 statements into 8 equivalence classes. [2025-03-16 18:12:07,148 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:07,148 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 8 check-sat command(s) [2025-03-16 18:12:07,148 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:12:07,153 INFO L256 TraceCheckSpWp]: Trace formula consists of 271 conjuncts, 77 conjuncts are in the unsatisfiable core [2025-03-16 18:12:07,155 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:12:08,530 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:08,530 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:12:09,483 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:12:09,483 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1747008353] [2025-03-16 18:12:09,483 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:12:09,483 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [711371071] [2025-03-16 18:12:09,483 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [711371071] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:12:09,483 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-16 18:12:09,483 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [23] total 23 [2025-03-16 18:12:09,483 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [610888873] [2025-03-16 18:12:09,483 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-16 18:12:09,484 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2025-03-16 18:12:09,484 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:12:09,484 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2025-03-16 18:12:09,484 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=93, Invalid=777, Unknown=0, NotChecked=0, Total=870 [2025-03-16 18:12:09,484 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:11,833 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:12:11,833 INFO L93 Difference]: Finished difference Result 605 states and 919 transitions. [2025-03-16 18:12:11,834 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2025-03-16 18:12:11,834 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:11,834 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:12:11,836 INFO L225 Difference]: With dead ends: 605 [2025-03-16 18:12:11,837 INFO L226 Difference]: Without dead ends: 598 [2025-03-16 18:12:11,837 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 154 GetRequests, 116 SyntacticMatches, 0 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 237 ImplicationChecksByTransitivity, 1.9s TimeCoverageRelationStatistics Valid=167, Invalid=1393, Unknown=0, NotChecked=0, Total=1560 [2025-03-16 18:12:11,837 INFO L435 NwaCegarLoop]: 46 mSDtfsCounter, 64 mSDsluCounter, 635 mSDsCounter, 0 mSdLazyCounter, 1164 mSolverCounterSat, 50 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.3s 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.4s IncrementalHoareTripleChecker+Time [2025-03-16 18:12:11,837 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.4s Time] [2025-03-16 18:12:11,838 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 598 states. [2025-03-16 18:12:12,356 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 598 to 566. [2025-03-16 18:12:12,356 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:12,358 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 566 states to 566 states and 869 transitions. [2025-03-16 18:12:12,359 INFO L78 Accepts]: Start accepts. Automaton has 566 states and 869 transitions. Word has length 104 [2025-03-16 18:12:12,359 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:12:12,359 INFO L471 AbstractCegarLoop]: Abstraction has 566 states and 869 transitions. [2025-03-16 18:12:12,359 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:12,359 INFO L276 IsEmpty]: Start isEmpty. Operand 566 states and 869 transitions. [2025-03-16 18:12:12,360 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 108 [2025-03-16 18:12:12,360 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:12:12,360 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:12,367 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Ended with exit code 0 [2025-03-16 18:12:12,561 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:12,561 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:12:12,561 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:12:12,561 INFO L85 PathProgramCache]: Analyzing trace with hash 985041779, now seen corresponding path program 1 times [2025-03-16 18:12:12,561 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:12:12,561 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [267536273] [2025-03-16 18:12:12,561 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:12:12,561 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:12:12,565 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 107 statements into 1 equivalence classes. [2025-03-16 18:12:12,577 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 107 of 107 statements. [2025-03-16 18:12:12,577 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:12:12,577 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:12:12,578 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [730772525] [2025-03-16 18:12:12,578 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:12:12,578 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:12:12,578 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:12:12,581 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:12,581 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:12,613 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 107 statements into 1 equivalence classes. [2025-03-16 18:12:12,642 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 107 of 107 statements. [2025-03-16 18:12:12,642 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:12:12,642 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:12:12,644 INFO L256 TraceCheckSpWp]: Trace formula consists of 270 conjuncts, 73 conjuncts are in the unsatisfiable core [2025-03-16 18:12:12,646 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:12:13,321 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:13,322 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:12:14,496 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:14,496 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:12:14,496 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [267536273] [2025-03-16 18:12:14,496 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:12:14,496 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [730772525] [2025-03-16 18:12:14,496 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [730772525] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:12:14,496 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:12:14,496 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 17] total 35 [2025-03-16 18:12:14,496 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [666603345] [2025-03-16 18:12:14,496 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:12:14,497 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 35 states [2025-03-16 18:12:14,497 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:12:14,497 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 35 interpolants. [2025-03-16 18:12:14,497 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=177, Invalid=1013, Unknown=0, NotChecked=0, Total=1190 [2025-03-16 18:12:14,498 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:37,475 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:12:37,476 INFO L93 Difference]: Finished difference Result 840 states and 1308 transitions. [2025-03-16 18:12:37,476 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 80 states. [2025-03-16 18:12:37,476 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:37,477 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:12:37,480 INFO L225 Difference]: With dead ends: 840 [2025-03-16 18:12:37,480 INFO L226 Difference]: Without dead ends: 838 [2025-03-16 18:12:37,482 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 284 GetRequests, 179 SyntacticMatches, 0 SemanticMatches, 105 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3212 ImplicationChecksByTransitivity, 18.5s TimeCoverageRelationStatistics Valid=2276, Invalid=9066, Unknown=0, NotChecked=0, Total=11342 [2025-03-16 18:12:37,482 INFO L435 NwaCegarLoop]: 43 mSDtfsCounter, 237 mSDsluCounter, 572 mSDsCounter, 0 mSdLazyCounter, 1557 mSolverCounterSat, 314 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.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, 4.4s IncrementalHoareTripleChecker+Time [2025-03-16 18:12:37,483 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [237 Valid, 615 Invalid, 1871 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [314 Valid, 1557 Invalid, 0 Unknown, 0 Unchecked, 4.4s Time] [2025-03-16 18:12:37,483 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 838 states. [2025-03-16 18:12:38,264 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 838 to 731. [2025-03-16 18:12:38,265 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:38,268 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 731 states to 731 states and 1140 transitions. [2025-03-16 18:12:38,269 INFO L78 Accepts]: Start accepts. Automaton has 731 states and 1140 transitions. Word has length 107 [2025-03-16 18:12:38,269 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:12:38,269 INFO L471 AbstractCegarLoop]: Abstraction has 731 states and 1140 transitions. [2025-03-16 18:12:38,269 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:38,269 INFO L276 IsEmpty]: Start isEmpty. Operand 731 states and 1140 transitions. [2025-03-16 18:12:38,270 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 113 [2025-03-16 18:12:38,270 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:12:38,270 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:38,279 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Ended with exit code 0 [2025-03-16 18:12:38,470 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:12:38,471 INFO L396 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:12:38,471 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:12:38,471 INFO L85 PathProgramCache]: Analyzing trace with hash 448458035, now seen corresponding path program 2 times [2025-03-16 18:12:38,471 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:12:38,471 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [266787913] [2025-03-16 18:12:38,471 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:12:38,471 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:12:38,475 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 112 statements into 2 equivalence classes. [2025-03-16 18:12:38,484 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 112 of 112 statements. [2025-03-16 18:12:38,485 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:12:38,485 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:12:38,485 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1976761251] [2025-03-16 18:12:38,485 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:12:38,485 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:12:38,486 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:12:38,487 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:12:38,489 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2025-03-16 18:12:38,517 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 112 statements into 2 equivalence classes. [2025-03-16 18:12:38,541 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 112 of 112 statements. [2025-03-16 18:12:38,541 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:12:38,541 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:12:38,542 INFO L256 TraceCheckSpWp]: Trace formula consists of 279 conjuncts, 44 conjuncts are in the unsatisfiable core [2025-03-16 18:12:38,544 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:12:38,780 INFO L134 CoverageAnalysis]: Checked inductivity of 455 backedges. 40 proven. 36 refuted. 0 times theorem prover too weak. 379 trivial. 0 not checked. [2025-03-16 18:12:38,780 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:12:38,959 INFO L134 CoverageAnalysis]: Checked inductivity of 455 backedges. 48 proven. 12 refuted. 0 times theorem prover too weak. 395 trivial. 0 not checked. [2025-03-16 18:12:38,959 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:12:38,959 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [266787913] [2025-03-16 18:12:38,959 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:12:38,959 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1976761251] [2025-03-16 18:12:38,959 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1976761251] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:12:38,959 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:12:38,959 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 9] total 25 [2025-03-16 18:12:38,959 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1118362995] [2025-03-16 18:12:38,959 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:12:38,959 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2025-03-16 18:12:38,960 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:12:38,960 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2025-03-16 18:12:38,960 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=82, Invalid=518, Unknown=0, NotChecked=0, Total=600 [2025-03-16 18:12:38,960 INFO L87 Difference]: Start difference. First operand 731 states and 1140 transitions. Second operand has 25 states, 23 states have (on average 1.9130434782608696) internal successors, (44), 22 states have internal predecessors, (44), 9 states have call successors, (35), 3 states have call predecessors, (35), 2 states have return successors, (34), 9 states have call predecessors, (34), 9 states have call successors, (34) [2025-03-16 18:12:41,329 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:12:41,329 INFO L93 Difference]: Finished difference Result 1131 states and 1830 transitions. [2025-03-16 18:12:41,329 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 42 states. [2025-03-16 18:12:41,329 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 23 states have (on average 1.9130434782608696) internal successors, (44), 22 states have internal predecessors, (44), 9 states have call successors, (35), 3 states have call predecessors, (35), 2 states have return successors, (34), 9 states have call predecessors, (34), 9 states have call successors, (34) Word has length 112 [2025-03-16 18:12:41,329 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:12:41,334 INFO L225 Difference]: With dead ends: 1131 [2025-03-16 18:12:41,334 INFO L226 Difference]: Without dead ends: 1129 [2025-03-16 18:12:41,335 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 270 GetRequests, 211 SyntacticMatches, 0 SemanticMatches, 59 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 816 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=685, Invalid=2975, Unknown=0, NotChecked=0, Total=3660 [2025-03-16 18:12:41,336 INFO L435 NwaCegarLoop]: 49 mSDtfsCounter, 114 mSDsluCounter, 499 mSDsCounter, 0 mSdLazyCounter, 763 mSolverCounterSat, 133 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 118 SdHoareTripleChecker+Valid, 548 SdHoareTripleChecker+Invalid, 896 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 133 IncrementalHoareTripleChecker+Valid, 763 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2025-03-16 18:12:41,336 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [118 Valid, 548 Invalid, 896 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [133 Valid, 763 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2025-03-16 18:12:41,336 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1129 states. [2025-03-16 18:12:42,591 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1129 to 1006. [2025-03-16 18:12:42,592 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1006 states, 450 states have (on average 1.3955555555555557) internal successors, (628), 452 states have internal predecessors, (628), 507 states have call successors, (507), 48 states have call predecessors, (507), 48 states have return successors, (506), 505 states have call predecessors, (506), 506 states have call successors, (506) [2025-03-16 18:12:42,596 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1006 states to 1006 states and 1641 transitions. [2025-03-16 18:12:42,597 INFO L78 Accepts]: Start accepts. Automaton has 1006 states and 1641 transitions. Word has length 112 [2025-03-16 18:12:42,597 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:12:42,597 INFO L471 AbstractCegarLoop]: Abstraction has 1006 states and 1641 transitions. [2025-03-16 18:12:42,597 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 25 states, 23 states have (on average 1.9130434782608696) internal successors, (44), 22 states have internal predecessors, (44), 9 states have call successors, (35), 3 states have call predecessors, (35), 2 states have return successors, (34), 9 states have call predecessors, (34), 9 states have call successors, (34) [2025-03-16 18:12:42,597 INFO L276 IsEmpty]: Start isEmpty. Operand 1006 states and 1641 transitions. [2025-03-16 18:12:42,599 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 120 [2025-03-16 18:12:42,599 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:12:42,599 INFO L218 NwaCegarLoop]: trace histogram [17, 16, 16, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:12:42,605 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Ended with exit code 0 [2025-03-16 18:12:42,799 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,19 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:12:42,800 INFO L396 AbstractCegarLoop]: === Iteration 21 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:12:42,800 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:12:42,800 INFO L85 PathProgramCache]: Analyzing trace with hash 419380243, now seen corresponding path program 6 times [2025-03-16 18:12:42,800 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:12:42,800 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [259013708] [2025-03-16 18:12:42,800 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-03-16 18:12:42,800 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:12:42,804 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 119 statements into 12 equivalence classes. [2025-03-16 18:12:42,820 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 8 check-sat command(s) and asserted 89 of 119 statements. [2025-03-16 18:12:42,821 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 8 check-sat command(s) [2025-03-16 18:12:42,821 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:12:42,935 INFO L134 CoverageAnalysis]: Checked inductivity of 571 backedges. 35 proven. 32 refuted. 0 times theorem prover too weak. 504 trivial. 0 not checked. [2025-03-16 18:12:42,935 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:12:42,935 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [259013708] [2025-03-16 18:12:42,935 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [259013708] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:12:42,935 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2146588384] [2025-03-16 18:12:42,935 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-03-16 18:12:42,935 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:12:42,935 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:12:42,937 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:12:42,938 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Waiting until timeout for monitored process [2025-03-16 18:12:42,964 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 119 statements into 12 equivalence classes. [2025-03-16 18:12:42,986 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 8 check-sat command(s) and asserted 89 of 119 statements. [2025-03-16 18:12:42,986 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 8 check-sat command(s) [2025-03-16 18:12:42,986 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:12:42,987 INFO L256 TraceCheckSpWp]: Trace formula consists of 222 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-03-16 18:12:42,988 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:12:43,066 INFO L134 CoverageAnalysis]: Checked inductivity of 571 backedges. 35 proven. 32 refuted. 0 times theorem prover too weak. 504 trivial. 0 not checked. [2025-03-16 18:12:43,066 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:12:43,176 INFO L134 CoverageAnalysis]: Checked inductivity of 571 backedges. 35 proven. 32 refuted. 0 times theorem prover too weak. 504 trivial. 0 not checked. [2025-03-16 18:12:43,176 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2146588384] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:12:43,176 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 18:12:43,176 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10, 10] total 14 [2025-03-16 18:12:43,176 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [669947524] [2025-03-16 18:12:43,176 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 18:12:43,177 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2025-03-16 18:12:43,177 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:12:43,177 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2025-03-16 18:12:43,177 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=31, Invalid=151, Unknown=0, NotChecked=0, Total=182 [2025-03-16 18:12:43,177 INFO L87 Difference]: Start difference. First operand 1006 states and 1641 transitions. Second operand has 14 states, 14 states have (on average 2.357142857142857) internal successors, (33), 14 states have internal predecessors, (33), 7 states have call successors, (25), 2 states have call predecessors, (25), 1 states have return successors, (24), 6 states have call predecessors, (24), 6 states have call successors, (24) [2025-03-16 18:12:44,746 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:12:44,746 INFO L93 Difference]: Finished difference Result 1795 states and 2967 transitions. [2025-03-16 18:12:44,746 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-03-16 18:12:44,747 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 2.357142857142857) internal successors, (33), 14 states have internal predecessors, (33), 7 states have call successors, (25), 2 states have call predecessors, (25), 1 states have return successors, (24), 6 states have call predecessors, (24), 6 states have call successors, (24) Word has length 119 [2025-03-16 18:12:44,747 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:12:44,752 INFO L225 Difference]: With dead ends: 1795 [2025-03-16 18:12:44,752 INFO L226 Difference]: Without dead ends: 1147 [2025-03-16 18:12:44,754 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 253 GetRequests, 226 SyntacticMatches, 8 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 54 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=81, Invalid=339, Unknown=0, NotChecked=0, Total=420 [2025-03-16 18:12:44,755 INFO L435 NwaCegarLoop]: 46 mSDtfsCounter, 15 mSDsluCounter, 254 mSDsCounter, 0 mSdLazyCounter, 191 mSolverCounterSat, 32 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 300 SdHoareTripleChecker+Invalid, 223 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 32 IncrementalHoareTripleChecker+Valid, 191 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:12:44,755 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 300 Invalid, 223 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [32 Valid, 191 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 18:12:44,756 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1147 states. [2025-03-16 18:12:46,124 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1147 to 1052. [2025-03-16 18:12:46,126 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1052 states, 470 states have (on average 1.3829787234042554) internal successors, (650), 493 states have internal predecessors, (650), 533 states have call successors, (533), 48 states have call predecessors, (533), 48 states have return successors, (532), 510 states have call predecessors, (532), 532 states have call successors, (532) [2025-03-16 18:12:46,129 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1052 states to 1052 states and 1715 transitions. [2025-03-16 18:12:46,131 INFO L78 Accepts]: Start accepts. Automaton has 1052 states and 1715 transitions. Word has length 119 [2025-03-16 18:12:46,131 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:12:46,131 INFO L471 AbstractCegarLoop]: Abstraction has 1052 states and 1715 transitions. [2025-03-16 18:12:46,131 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 2.357142857142857) internal successors, (33), 14 states have internal predecessors, (33), 7 states have call successors, (25), 2 states have call predecessors, (25), 1 states have return successors, (24), 6 states have call predecessors, (24), 6 states have call successors, (24) [2025-03-16 18:12:46,132 INFO L276 IsEmpty]: Start isEmpty. Operand 1052 states and 1715 transitions. [2025-03-16 18:12:46,133 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 123 [2025-03-16 18:12:46,133 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:12:46,133 INFO L218 NwaCegarLoop]: trace histogram [17, 16, 16, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:12:46,139 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Forceful destruction successful, exit code 0 [2025-03-16 18:12:46,333 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable20,20 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:12:46,334 INFO L396 AbstractCegarLoop]: === Iteration 22 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:12:46,334 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:12:46,334 INFO L85 PathProgramCache]: Analyzing trace with hash -932847920, now seen corresponding path program 7 times [2025-03-16 18:12:46,334 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:12:46,334 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2088660854] [2025-03-16 18:12:46,334 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-03-16 18:12:46,334 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:12:46,338 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 122 statements into 1 equivalence classes. [2025-03-16 18:12:46,353 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 122 of 122 statements. [2025-03-16 18:12:46,353 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:12:46,353 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:12:46,354 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1034449601] [2025-03-16 18:12:46,354 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-03-16 18:12:46,354 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:12:46,354 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:12:46,359 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:12:46,360 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Waiting until timeout for monitored process [2025-03-16 18:12:46,387 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 122 statements into 1 equivalence classes. [2025-03-16 18:12:46,417 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 122 of 122 statements. [2025-03-16 18:12:46,417 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:12:46,417 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:12:46,425 INFO L256 TraceCheckSpWp]: Trace formula consists of 294 conjuncts, 84 conjuncts are in the unsatisfiable core [2025-03-16 18:12:46,429 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:12:47,191 INFO L134 CoverageAnalysis]: Checked inductivity of 577 backedges. 76 proven. 51 refuted. 0 times theorem prover too weak. 450 trivial. 0 not checked. [2025-03-16 18:12:47,191 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:12:48,897 INFO L134 CoverageAnalysis]: Checked inductivity of 577 backedges. 70 proven. 48 refuted. 0 times theorem prover too weak. 459 trivial. 0 not checked. [2025-03-16 18:12:48,897 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:12:48,897 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2088660854] [2025-03-16 18:12:48,897 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:12:48,897 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1034449601] [2025-03-16 18:12:48,897 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1034449601] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:12:48,897 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:12:48,898 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 19] total 38 [2025-03-16 18:12:48,898 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [51260492] [2025-03-16 18:12:48,898 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:12:48,898 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 38 states [2025-03-16 18:12:48,898 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:12:48,898 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 38 interpolants. [2025-03-16 18:12:48,899 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=183, Invalid=1223, Unknown=0, NotChecked=0, Total=1406 [2025-03-16 18:12:48,899 INFO L87 Difference]: Start difference. First operand 1052 states and 1715 transitions. Second operand has 38 states, 35 states have (on average 1.5142857142857142) internal successors, (53), 36 states have internal predecessors, (53), 13 states have call successors, (39), 3 states have call predecessors, (39), 3 states have return successors, (38), 11 states have call predecessors, (38), 11 states have call successors, (38)