./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound5.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/egcd2-ll_unwindbound5.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 74e9855722264d342377b8ab219a69c32c582cc628f82167488f3dea5640534c --- Real Ultimate output --- This is Ultimate 0.3.0-?-8fc3dc6-m [2025-03-16 18:09:20,518 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-16 18:09:20,558 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2025-03-16 18:09:20,562 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-16 18:09:20,563 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-16 18:09:20,579 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-16 18:09:20,580 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-16 18:09:20,580 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-16 18:09:20,580 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-16 18:09:20,580 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-16 18:09:20,580 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-03-16 18:09:20,580 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-03-16 18:09:20,580 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-16 18:09:20,581 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-16 18:09:20,581 INFO L153 SettingsManager]: * Use SBE=true [2025-03-16 18:09:20,581 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-16 18:09:20,581 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-03-16 18:09:20,581 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-16 18:09:20,581 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-16 18:09:20,581 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-16 18:09:20,581 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-16 18:09:20,581 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-03-16 18:09:20,582 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-03-16 18:09:20,582 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-03-16 18:09:20,582 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-16 18:09:20,582 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-16 18:09:20,582 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-16 18:09:20,582 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-16 18:09:20,582 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-16 18:09:20,582 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-16 18:09:20,582 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-03-16 18:09:20,582 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-03-16 18:09:20,582 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-16 18:09:20,583 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-16 18:09:20,583 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-03-16 18:09:20,583 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-03-16 18:09:20,583 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-03-16 18:09:20,583 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-16 18:09:20,583 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-03-16 18:09:20,583 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-03-16 18:09:20,583 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-03-16 18:09:20,583 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-03-16 18:09:20,583 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-03-16 18:09:20,584 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 -> 74e9855722264d342377b8ab219a69c32c582cc628f82167488f3dea5640534c [2025-03-16 18:09:20,813 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-16 18:09:20,820 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-16 18:09:20,821 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-16 18:09:20,822 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-16 18:09:20,822 INFO L274 PluginConnector]: CDTParser initialized [2025-03-16 18:09:20,823 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound5.c [2025-03-16 18:09:21,922 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/8544d03ce/606eefe312814cfcbac140323efed304/FLAGff386593c [2025-03-16 18:09:22,138 INFO L384 CDTParser]: Found 1 translation units. [2025-03-16 18:09:22,145 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound5.c [2025-03-16 18:09:22,157 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/8544d03ce/606eefe312814cfcbac140323efed304/FLAGff386593c [2025-03-16 18:09:22,195 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/8544d03ce/606eefe312814cfcbac140323efed304 [2025-03-16 18:09:22,197 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-16 18:09:22,198 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-16 18:09:22,201 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-16 18:09:22,201 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-16 18:09:22,204 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-16 18:09:22,205 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.03 06:09:22" (1/1) ... [2025-03-16 18:09:22,206 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@766a0094 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:09:22, skipping insertion in model container [2025-03-16 18:09:22,206 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.03 06:09:22" (1/1) ... [2025-03-16 18:09:22,219 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-16 18:09:22,320 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound5.c[490,503] [2025-03-16 18:09:22,349 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-16 18:09:22,358 INFO L200 MainTranslator]: Completed pre-run [2025-03-16 18:09:22,366 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound5.c[490,503] [2025-03-16 18:09:22,374 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-16 18:09:22,385 INFO L204 MainTranslator]: Completed translation [2025-03-16 18:09:22,386 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:09:22 WrapperNode [2025-03-16 18:09:22,387 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-16 18:09:22,388 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-16 18:09:22,388 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-16 18:09:22,388 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-16 18:09:22,393 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:09:22" (1/1) ... [2025-03-16 18:09:22,397 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:09:22" (1/1) ... [2025-03-16 18:09:22,408 INFO L138 Inliner]: procedures = 14, calls = 17, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 84 [2025-03-16 18:09:22,410 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-16 18:09:22,410 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-16 18:09:22,410 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-16 18:09:22,410 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-16 18:09:22,415 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:09:22" (1/1) ... [2025-03-16 18:09:22,415 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:09:22" (1/1) ... [2025-03-16 18:09:22,416 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:09:22" (1/1) ... [2025-03-16 18:09:22,424 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:09:22,424 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:09:22" (1/1) ... [2025-03-16 18:09:22,424 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:09:22" (1/1) ... [2025-03-16 18:09:22,427 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:09:22" (1/1) ... [2025-03-16 18:09:22,428 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:09:22" (1/1) ... [2025-03-16 18:09:22,429 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:09:22" (1/1) ... [2025-03-16 18:09:22,429 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:09:22" (1/1) ... [2025-03-16 18:09:22,431 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-16 18:09:22,431 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-16 18:09:22,431 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-16 18:09:22,431 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-16 18:09:22,432 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:09:22" (1/1) ... [2025-03-16 18:09:22,439 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-16 18:09:22,448 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:09:22,460 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:09:22,462 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:09:22,479 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-16 18:09:22,479 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2025-03-16 18:09:22,479 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2025-03-16 18:09:22,479 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-03-16 18:09:22,479 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-16 18:09:22,479 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-16 18:09:22,479 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2025-03-16 18:09:22,479 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2025-03-16 18:09:22,523 INFO L256 CfgBuilder]: Building ICFG [2025-03-16 18:09:22,524 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-16 18:09:22,674 INFO L? ?]: Removed 10 outVars from TransFormulas that were not future-live. [2025-03-16 18:09:22,675 INFO L307 CfgBuilder]: Performing block encoding [2025-03-16 18:09:22,684 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-16 18:09:22,685 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-16 18:09:22,685 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 16.03 06:09:22 BoogieIcfgContainer [2025-03-16 18:09:22,685 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-16 18:09:22,687 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-03-16 18:09:22,687 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-03-16 18:09:22,691 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-03-16 18:09:22,691 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 16.03 06:09:22" (1/3) ... [2025-03-16 18:09:22,692 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@75813051 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.03 06:09:22, skipping insertion in model container [2025-03-16 18:09:22,693 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:09:22" (2/3) ... [2025-03-16 18:09:22,693 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@75813051 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.03 06:09:22, skipping insertion in model container [2025-03-16 18:09:22,693 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 16.03 06:09:22" (3/3) ... [2025-03-16 18:09:22,694 INFO L128 eAbstractionObserver]: Analyzing ICFG egcd2-ll_unwindbound5.c [2025-03-16 18:09:22,706 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-03-16 18:09:22,707 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG egcd2-ll_unwindbound5.c that has 3 procedures, 32 locations, 1 initial locations, 2 loop locations, and 1 error locations. [2025-03-16 18:09:22,752 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-03-16 18:09:22,764 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;@6f37fa42, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-03-16 18:09:22,765 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-03-16 18:09:22,768 INFO L276 IsEmpty]: Start isEmpty. Operand has 32 states, 18 states have (on average 1.5) internal successors, (27), 20 states have internal predecessors, (27), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2025-03-16 18:09:22,772 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2025-03-16 18:09:22,772 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:09:22,773 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:09:22,773 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:09:22,776 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:09:22,776 INFO L85 PathProgramCache]: Analyzing trace with hash 1447899124, now seen corresponding path program 1 times [2025-03-16 18:09:22,782 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:09:22,782 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1707227792] [2025-03-16 18:09:22,783 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:09:22,783 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:09:22,836 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 27 statements into 1 equivalence classes. [2025-03-16 18:09:22,852 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 27 of 27 statements. [2025-03-16 18:09:22,853 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:09:22,853 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:09:22,914 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:09:22,915 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:09:22,915 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1707227792] [2025-03-16 18:09:22,916 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1707227792] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 18:09:22,916 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 18:09:22,917 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2025-03-16 18:09:22,918 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1003250841] [2025-03-16 18:09:22,919 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:09:22,921 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2025-03-16 18:09:22,922 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:09:22,937 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2025-03-16 18:09:22,937 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-03-16 18:09:22,939 INFO L87 Difference]: Start difference. First operand has 32 states, 18 states have (on average 1.5) internal successors, (27), 20 states have internal predecessors, (27), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand has 2 states, 2 states have (on average 4.5) internal successors, (9), 2 states have internal predecessors, (9), 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:09:22,953 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:09:22,954 INFO L93 Difference]: Finished difference Result 62 states and 101 transitions. [2025-03-16 18:09:22,955 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2025-03-16 18:09:22,956 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 4.5) internal successors, (9), 2 states have internal predecessors, (9), 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 27 [2025-03-16 18:09:22,957 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:09:22,961 INFO L225 Difference]: With dead ends: 62 [2025-03-16 18:09:22,961 INFO L226 Difference]: Without dead ends: 29 [2025-03-16 18:09:22,963 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-03-16 18:09:22,968 INFO L435 NwaCegarLoop]: 43 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 43 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-16 18:09:22,970 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 43 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 18:09:22,978 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 29 states. [2025-03-16 18:09:22,987 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 29 to 29. [2025-03-16 18:09:22,988 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 29 states, 16 states have (on average 1.3125) internal successors, (21), 18 states have internal predecessors, (21), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2025-03-16 18:09:22,990 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 40 transitions. [2025-03-16 18:09:22,992 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 40 transitions. Word has length 27 [2025-03-16 18:09:22,992 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:09:22,992 INFO L471 AbstractCegarLoop]: Abstraction has 29 states and 40 transitions. [2025-03-16 18:09:22,993 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 4.5) internal successors, (9), 2 states have internal predecessors, (9), 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:09:22,993 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 40 transitions. [2025-03-16 18:09:22,994 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2025-03-16 18:09:22,994 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:09:22,994 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:09:22,994 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2025-03-16 18:09:22,994 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:09:22,995 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:09:22,995 INFO L85 PathProgramCache]: Analyzing trace with hash 1886374424, now seen corresponding path program 1 times [2025-03-16 18:09:22,995 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:09:22,995 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2124364394] [2025-03-16 18:09:22,995 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:09:22,995 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:09:23,002 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 28 statements into 1 equivalence classes. [2025-03-16 18:09:23,012 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 28 of 28 statements. [2025-03-16 18:09:23,012 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:09:23,012 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:09:23,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:09:23,121 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:09:23,121 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2124364394] [2025-03-16 18:09:23,121 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2124364394] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 18:09:23,121 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 18:09:23,121 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2025-03-16 18:09:23,121 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1638463793] [2025-03-16 18:09:23,121 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:09:23,122 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2025-03-16 18:09:23,122 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:09:23,122 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2025-03-16 18:09:23,122 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2025-03-16 18:09:23,123 INFO L87 Difference]: Start difference. First operand 29 states and 40 transitions. Second operand has 4 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 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:09:23,145 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:09:23,145 INFO L93 Difference]: Finished difference Result 39 states and 51 transitions. [2025-03-16 18:09:23,146 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2025-03-16 18:09:23,146 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 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 28 [2025-03-16 18:09:23,146 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:09:23,147 INFO L225 Difference]: With dead ends: 39 [2025-03-16 18:09:23,147 INFO L226 Difference]: Without dead ends: 31 [2025-03-16 18:09:23,147 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2025-03-16 18:09:23,147 INFO L435 NwaCegarLoop]: 38 mSDtfsCounter, 7 mSDsluCounter, 60 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 98 SdHoareTripleChecker+Invalid, 9 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-16 18:09:23,148 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 98 Invalid, 9 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 18:09:23,148 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2025-03-16 18:09:23,151 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 31. [2025-03-16 18:09:23,152 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 31 states, 18 states have (on average 1.2777777777777777) internal successors, (23), 19 states have internal predecessors, (23), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2025-03-16 18:09:23,152 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 42 transitions. [2025-03-16 18:09:23,153 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 42 transitions. Word has length 28 [2025-03-16 18:09:23,153 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:09:23,153 INFO L471 AbstractCegarLoop]: Abstraction has 31 states and 42 transitions. [2025-03-16 18:09:23,153 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 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:09:23,153 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 42 transitions. [2025-03-16 18:09:23,154 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2025-03-16 18:09:23,154 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:09:23,154 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:09:23,154 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2025-03-16 18:09:23,154 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:09:23,154 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:09:23,154 INFO L85 PathProgramCache]: Analyzing trace with hash -1704454544, now seen corresponding path program 1 times [2025-03-16 18:09:23,155 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:09:23,155 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1761799165] [2025-03-16 18:09:23,155 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:09:23,155 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:09:23,164 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 29 statements into 1 equivalence classes. [2025-03-16 18:09:23,186 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 29 of 29 statements. [2025-03-16 18:09:23,186 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:09:23,186 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:09:23,331 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2025-03-16 18:09:23,332 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:09:23,332 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1761799165] [2025-03-16 18:09:23,333 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1761799165] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:09:23,333 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1591922943] [2025-03-16 18:09:23,333 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:09:23,333 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:09:23,333 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:09:23,335 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:09:23,336 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:09:23,374 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 29 statements into 1 equivalence classes. [2025-03-16 18:09:23,389 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 29 of 29 statements. [2025-03-16 18:09:23,389 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:09:23,389 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:09:23,391 INFO L256 TraceCheckSpWp]: Trace formula consists of 99 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-03-16 18:09:23,394 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:09:23,526 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:09:23,526 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-16 18:09:23,526 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1591922943] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 18:09:23,526 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-16 18:09:23,526 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 10 [2025-03-16 18:09:23,527 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [122585753] [2025-03-16 18:09:23,527 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:09:23,527 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2025-03-16 18:09:23,527 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:09:23,527 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-03-16 18:09:23,527 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=72, Unknown=0, NotChecked=0, Total=90 [2025-03-16 18:09:23,527 INFO L87 Difference]: Start difference. First operand 31 states and 42 transitions. Second operand has 6 states, 5 states have (on average 2.2) internal successors, (11), 5 states have internal predecessors, (11), 3 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2025-03-16 18:09:23,605 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:09:23,606 INFO L93 Difference]: Finished difference Result 48 states and 66 transitions. [2025-03-16 18:09:23,606 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-16 18:09:23,606 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 2.2) internal successors, (11), 5 states have internal predecessors, (11), 3 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 29 [2025-03-16 18:09:23,606 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:09:23,607 INFO L225 Difference]: With dead ends: 48 [2025-03-16 18:09:23,607 INFO L226 Difference]: Without dead ends: 46 [2025-03-16 18:09:23,607 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 35 GetRequests, 26 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=22, Invalid=88, Unknown=0, NotChecked=0, Total=110 [2025-03-16 18:09:23,608 INFO L435 NwaCegarLoop]: 31 mSDtfsCounter, 9 mSDsluCounter, 110 mSDsCounter, 0 mSdLazyCounter, 56 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 141 SdHoareTripleChecker+Invalid, 57 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 56 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:09:23,608 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 141 Invalid, 57 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 56 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 18:09:23,608 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 46 states. [2025-03-16 18:09:23,614 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 46 to 44. [2025-03-16 18:09:23,615 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 44 states, 25 states have (on average 1.32) internal successors, (33), 27 states have internal predecessors, (33), 15 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (14), 13 states have call predecessors, (14), 14 states have call successors, (14) [2025-03-16 18:09:23,617 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 62 transitions. [2025-03-16 18:09:23,617 INFO L78 Accepts]: Start accepts. Automaton has 44 states and 62 transitions. Word has length 29 [2025-03-16 18:09:23,617 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:09:23,617 INFO L471 AbstractCegarLoop]: Abstraction has 44 states and 62 transitions. [2025-03-16 18:09:23,618 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 2.2) internal successors, (11), 5 states have internal predecessors, (11), 3 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2025-03-16 18:09:23,618 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 62 transitions. [2025-03-16 18:09:23,618 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2025-03-16 18:09:23,618 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:09:23,618 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:09:23,625 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2025-03-16 18:09:23,823 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:09:23,823 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:09:23,823 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:09:23,824 INFO L85 PathProgramCache]: Analyzing trace with hash -678028952, now seen corresponding path program 1 times [2025-03-16 18:09:23,824 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:09:23,824 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [872922658] [2025-03-16 18:09:23,824 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:09:23,824 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:09:23,828 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-03-16 18:09:23,842 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-03-16 18:09:23,842 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:09:23,842 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:09:23,848 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1702791619] [2025-03-16 18:09:23,848 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:09:23,848 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:09:23,848 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:09:23,850 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:09:23,852 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:09:23,874 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-03-16 18:09:23,886 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-03-16 18:09:23,886 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:09:23,886 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:09:23,887 INFO L256 TraceCheckSpWp]: Trace formula consists of 107 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-16 18:09:23,889 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:09:23,922 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:09:23,922 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-16 18:09:23,922 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:09:23,922 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [872922658] [2025-03-16 18:09:23,923 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:09:23,923 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1702791619] [2025-03-16 18:09:23,923 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1702791619] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 18:09:23,923 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 18:09:23,923 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-16 18:09:23,923 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1896582919] [2025-03-16 18:09:23,923 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:09:23,923 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-16 18:09:23,924 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:09:23,924 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-16 18:09:23,926 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-16 18:09:23,926 INFO L87 Difference]: Start difference. First operand 44 states and 62 transitions. Second operand has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 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:09:23,975 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:09:23,975 INFO L93 Difference]: Finished difference Result 65 states and 94 transitions. [2025-03-16 18:09:23,975 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-16 18:09:23,976 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 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 31 [2025-03-16 18:09:23,976 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:09:23,977 INFO L225 Difference]: With dead ends: 65 [2025-03-16 18:09:23,977 INFO L226 Difference]: Without dead ends: 63 [2025-03-16 18:09:23,978 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 31 GetRequests, 27 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:09:23,978 INFO L435 NwaCegarLoop]: 37 mSDtfsCounter, 5 mSDsluCounter, 98 mSDsCounter, 0 mSdLazyCounter, 32 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 135 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:09:23,978 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 135 Invalid, 32 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 18:09:23,979 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2025-03-16 18:09:23,986 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 54. [2025-03-16 18:09:23,986 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 32 states have (on average 1.3125) internal successors, (42), 36 states have internal predecessors, (42), 17 states have call successors, (17), 4 states have call predecessors, (17), 4 states have return successors, (16), 13 states have call predecessors, (16), 16 states have call successors, (16) [2025-03-16 18:09:23,987 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 75 transitions. [2025-03-16 18:09:23,987 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 75 transitions. Word has length 31 [2025-03-16 18:09:23,987 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:09:23,987 INFO L471 AbstractCegarLoop]: Abstraction has 54 states and 75 transitions. [2025-03-16 18:09:23,988 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 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:09:23,988 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 75 transitions. [2025-03-16 18:09:23,988 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2025-03-16 18:09:23,988 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:09:23,988 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:09:23,994 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:09:24,193 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,SelfDestructingSolverStorable3 [2025-03-16 18:09:24,193 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:09:24,194 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:09:24,194 INFO L85 PathProgramCache]: Analyzing trace with hash 781013430, now seen corresponding path program 1 times [2025-03-16 18:09:24,194 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:09:24,194 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1963527387] [2025-03-16 18:09:24,194 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:09:24,194 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:09:24,202 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 34 statements into 1 equivalence classes. [2025-03-16 18:09:24,208 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 34 of 34 statements. [2025-03-16 18:09:24,208 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:09:24,208 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:09:24,303 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 5 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2025-03-16 18:09:24,304 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:09:24,304 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1963527387] [2025-03-16 18:09:24,304 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1963527387] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:09:24,304 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [632168927] [2025-03-16 18:09:24,304 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:09:24,304 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:09:24,304 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:09:24,306 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:09:24,308 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:09:24,335 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 34 statements into 1 equivalence classes. [2025-03-16 18:09:24,347 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 34 of 34 statements. [2025-03-16 18:09:24,348 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:09:24,348 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:09:24,348 INFO L256 TraceCheckSpWp]: Trace formula consists of 108 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-03-16 18:09:24,350 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:09:24,424 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-03-16 18:09:24,424 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-16 18:09:24,424 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [632168927] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 18:09:24,428 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-16 18:09:24,428 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 9 [2025-03-16 18:09:24,428 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1780160108] [2025-03-16 18:09:24,428 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:09:24,428 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-16 18:09:24,428 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:09:24,429 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-16 18:09:24,429 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=56, Unknown=0, NotChecked=0, Total=72 [2025-03-16 18:09:24,443 INFO L87 Difference]: Start difference. First operand 54 states and 75 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (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:09:24,480 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:09:24,480 INFO L93 Difference]: Finished difference Result 62 states and 82 transitions. [2025-03-16 18:09:24,480 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-16 18:09:24,480 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (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 34 [2025-03-16 18:09:24,480 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:09:24,481 INFO L225 Difference]: With dead ends: 62 [2025-03-16 18:09:24,481 INFO L226 Difference]: Without dead ends: 58 [2025-03-16 18:09:24,481 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 40 GetRequests, 32 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=20, Invalid=70, Unknown=0, NotChecked=0, Total=90 [2025-03-16 18:09:24,482 INFO L435 NwaCegarLoop]: 38 mSDtfsCounter, 9 mSDsluCounter, 100 mSDsCounter, 0 mSdLazyCounter, 27 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 138 SdHoareTripleChecker+Invalid, 28 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 27 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-16 18:09:24,482 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 138 Invalid, 28 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 27 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 18:09:24,486 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states. [2025-03-16 18:09:24,491 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 57. [2025-03-16 18:09:24,491 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 57 states, 35 states have (on average 1.2571428571428571) internal successors, (44), 38 states have internal predecessors, (44), 16 states have call successors, (16), 5 states have call predecessors, (16), 5 states have return successors, (15), 13 states have call predecessors, (15), 15 states have call successors, (15) [2025-03-16 18:09:24,492 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 75 transitions. [2025-03-16 18:09:24,492 INFO L78 Accepts]: Start accepts. Automaton has 57 states and 75 transitions. Word has length 34 [2025-03-16 18:09:24,492 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:09:24,492 INFO L471 AbstractCegarLoop]: Abstraction has 57 states and 75 transitions. [2025-03-16 18:09:24,492 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (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:09:24,492 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 75 transitions. [2025-03-16 18:09:24,493 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2025-03-16 18:09:24,493 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:09:24,493 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:09:24,499 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:09:24,693 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:09:24,694 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:09:24,694 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:09:24,694 INFO L85 PathProgramCache]: Analyzing trace with hash 1661765959, now seen corresponding path program 1 times [2025-03-16 18:09:24,694 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:09:24,694 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [848803441] [2025-03-16 18:09:24,694 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:09:24,694 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:09:24,699 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 34 statements into 1 equivalence classes. [2025-03-16 18:09:24,703 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 34 of 34 statements. [2025-03-16 18:09:24,703 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:09:24,703 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:09:24,750 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-03-16 18:09:24,750 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:09:24,750 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [848803441] [2025-03-16 18:09:24,750 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [848803441] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 18:09:24,750 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 18:09:24,750 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-16 18:09:24,750 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [68459184] [2025-03-16 18:09:24,750 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:09:24,750 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-16 18:09:24,750 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:09:24,751 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-16 18:09:24,751 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2025-03-16 18:09:24,751 INFO L87 Difference]: Start difference. First operand 57 states and 75 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 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:09:24,775 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:09:24,775 INFO L93 Difference]: Finished difference Result 83 states and 110 transitions. [2025-03-16 18:09:24,777 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-16 18:09:24,777 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 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 34 [2025-03-16 18:09:24,777 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:09:24,778 INFO L225 Difference]: With dead ends: 83 [2025-03-16 18:09:24,778 INFO L226 Difference]: Without dead ends: 57 [2025-03-16 18:09:24,778 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2025-03-16 18:09:24,780 INFO L435 NwaCegarLoop]: 37 mSDtfsCounter, 10 mSDsluCounter, 61 mSDsCounter, 0 mSdLazyCounter, 12 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 98 SdHoareTripleChecker+Invalid, 16 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 12 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-16 18:09:24,780 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 98 Invalid, 16 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 12 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 18:09:24,780 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 57 states. [2025-03-16 18:09:24,786 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 57 to 57. [2025-03-16 18:09:24,787 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 57 states, 35 states have (on average 1.2285714285714286) internal successors, (43), 38 states have internal predecessors, (43), 16 states have call successors, (16), 5 states have call predecessors, (16), 5 states have return successors, (15), 13 states have call predecessors, (15), 15 states have call successors, (15) [2025-03-16 18:09:24,790 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 74 transitions. [2025-03-16 18:09:24,790 INFO L78 Accepts]: Start accepts. Automaton has 57 states and 74 transitions. Word has length 34 [2025-03-16 18:09:24,790 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:09:24,790 INFO L471 AbstractCegarLoop]: Abstraction has 57 states and 74 transitions. [2025-03-16 18:09:24,790 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 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:09:24,790 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 74 transitions. [2025-03-16 18:09:24,792 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2025-03-16 18:09:24,793 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:09:24,793 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:09:24,793 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5 [2025-03-16 18:09:24,793 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:09:24,793 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:09:24,793 INFO L85 PathProgramCache]: Analyzing trace with hash 536628030, now seen corresponding path program 1 times [2025-03-16 18:09:24,793 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:09:24,793 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [949645192] [2025-03-16 18:09:24,793 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:09:24,794 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:09:24,800 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 46 statements into 1 equivalence classes. [2025-03-16 18:09:24,808 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 46 of 46 statements. [2025-03-16 18:09:24,809 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:09:24,809 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:09:24,809 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1917048146] [2025-03-16 18:09:24,809 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:09:24,810 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:09:24,810 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:09:24,811 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:09:24,813 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:09:24,840 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 46 statements into 1 equivalence classes. [2025-03-16 18:09:24,853 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 46 of 46 statements. [2025-03-16 18:09:24,853 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:09:24,853 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:09:24,854 INFO L256 TraceCheckSpWp]: Trace formula consists of 134 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-03-16 18:09:24,857 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:09:24,996 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:09:24,996 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-16 18:09:24,996 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:09:24,996 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [949645192] [2025-03-16 18:09:24,997 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:09:24,997 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1917048146] [2025-03-16 18:09:24,997 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1917048146] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 18:09:24,997 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 18:09:24,997 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-16 18:09:24,997 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1037041593] [2025-03-16 18:09:24,997 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:09:24,997 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-16 18:09:24,997 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:09:24,998 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-16 18:09:24,998 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-16 18:09:24,998 INFO L87 Difference]: Start difference. First operand 57 states and 74 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 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:09:25,045 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:09:25,045 INFO L93 Difference]: Finished difference Result 64 states and 80 transitions. [2025-03-16 18:09:25,046 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-16 18:09:25,046 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 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 46 [2025-03-16 18:09:25,046 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:09:25,046 INFO L225 Difference]: With dead ends: 64 [2025-03-16 18:09:25,046 INFO L226 Difference]: Without dead ends: 62 [2025-03-16 18:09:25,047 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 46 GetRequests, 42 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:09:25,047 INFO L435 NwaCegarLoop]: 35 mSDtfsCounter, 6 mSDsluCounter, 91 mSDsCounter, 0 mSdLazyCounter, 39 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 126 SdHoareTripleChecker+Invalid, 40 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 39 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-16 18:09:25,047 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 126 Invalid, 40 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 18:09:25,048 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 62 states. [2025-03-16 18:09:25,056 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 62 to 61. [2025-03-16 18:09:25,057 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 61 states, 38 states have (on average 1.2105263157894737) internal successors, (46), 41 states have internal predecessors, (46), 16 states have call successors, (16), 6 states have call predecessors, (16), 6 states have return successors, (15), 13 states have call predecessors, (15), 15 states have call successors, (15) [2025-03-16 18:09:25,058 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 61 states to 61 states and 77 transitions. [2025-03-16 18:09:25,059 INFO L78 Accepts]: Start accepts. Automaton has 61 states and 77 transitions. Word has length 46 [2025-03-16 18:09:25,059 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:09:25,059 INFO L471 AbstractCegarLoop]: Abstraction has 61 states and 77 transitions. [2025-03-16 18:09:25,059 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 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:09:25,059 INFO L276 IsEmpty]: Start isEmpty. Operand 61 states and 77 transitions. [2025-03-16 18:09:25,060 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2025-03-16 18:09:25,060 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:09:25,061 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:09:25,067 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:09:25,261 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:09:25,261 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:09:25,262 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:09:25,262 INFO L85 PathProgramCache]: Analyzing trace with hash -740965909, now seen corresponding path program 1 times [2025-03-16 18:09:25,262 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:09:25,262 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1745458910] [2025-03-16 18:09:25,262 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:09:25,262 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:09:25,270 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 54 statements into 1 equivalence classes. [2025-03-16 18:09:25,282 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 54 of 54 statements. [2025-03-16 18:09:25,282 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:09:25,282 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:09:25,284 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1130086839] [2025-03-16 18:09:25,284 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:09:25,284 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:09:25,285 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:09:25,286 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:09:25,288 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:09:25,318 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 54 statements into 1 equivalence classes. [2025-03-16 18:09:25,336 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 54 of 54 statements. [2025-03-16 18:09:25,336 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:09:25,336 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:09:25,337 INFO L256 TraceCheckSpWp]: Trace formula consists of 153 conjuncts, 13 conjuncts are in the unsatisfiable core [2025-03-16 18:09:25,338 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:09:25,396 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 3 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2025-03-16 18:09:25,396 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:09:25,499 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 3 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2025-03-16 18:09:25,499 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:09:25,499 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1745458910] [2025-03-16 18:09:25,499 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:09:25,499 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1130086839] [2025-03-16 18:09:25,499 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1130086839] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:09:25,499 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:09:25,500 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 7 [2025-03-16 18:09:25,500 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [58078517] [2025-03-16 18:09:25,500 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:09:25,500 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2025-03-16 18:09:25,500 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:09:25,502 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2025-03-16 18:09:25,502 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2025-03-16 18:09:25,502 INFO L87 Difference]: Start difference. First operand 61 states and 77 transitions. Second operand has 7 states, 7 states have (on average 3.142857142857143) internal successors, (22), 6 states have internal predecessors, (22), 4 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2025-03-16 18:09:25,591 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:09:25,592 INFO L93 Difference]: Finished difference Result 91 states and 126 transitions. [2025-03-16 18:09:25,592 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2025-03-16 18:09:25,592 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 3.142857142857143) internal successors, (22), 6 states have internal predecessors, (22), 4 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) Word has length 54 [2025-03-16 18:09:25,593 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:09:25,593 INFO L225 Difference]: With dead ends: 91 [2025-03-16 18:09:25,593 INFO L226 Difference]: Without dead ends: 89 [2025-03-16 18:09:25,594 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 107 GetRequests, 98 SyntacticMatches, 3 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2025-03-16 18:09:25,594 INFO L435 NwaCegarLoop]: 44 mSDtfsCounter, 13 mSDsluCounter, 112 mSDsCounter, 0 mSdLazyCounter, 59 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 21 SdHoareTripleChecker+Valid, 156 SdHoareTripleChecker+Invalid, 65 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 59 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:09:25,594 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [21 Valid, 156 Invalid, 65 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 59 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 18:09:25,595 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 89 states. [2025-03-16 18:09:25,608 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 89 to 57. [2025-03-16 18:09:25,609 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 57 states, 36 states have (on average 1.1944444444444444) internal successors, (43), 37 states have internal predecessors, (43), 14 states have call successors, (14), 6 states have call predecessors, (14), 6 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2025-03-16 18:09:25,609 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 70 transitions. [2025-03-16 18:09:25,610 INFO L78 Accepts]: Start accepts. Automaton has 57 states and 70 transitions. Word has length 54 [2025-03-16 18:09:25,612 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:09:25,612 INFO L471 AbstractCegarLoop]: Abstraction has 57 states and 70 transitions. [2025-03-16 18:09:25,613 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 3.142857142857143) internal successors, (22), 6 states have internal predecessors, (22), 4 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2025-03-16 18:09:25,613 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 70 transitions. [2025-03-16 18:09:25,613 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2025-03-16 18:09:25,613 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:09:25,613 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:09:25,621 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2025-03-16 18:09:25,814 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:09:25,815 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:09:25,815 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:09:25,815 INFO L85 PathProgramCache]: Analyzing trace with hash -1599658939, now seen corresponding path program 1 times [2025-03-16 18:09:25,815 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:09:25,815 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1204831580] [2025-03-16 18:09:25,816 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:09:25,816 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:09:25,820 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 55 statements into 1 equivalence classes. [2025-03-16 18:09:25,824 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 55 of 55 statements. [2025-03-16 18:09:25,825 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:09:25,825 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:09:25,897 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:09:25,897 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:09:25,897 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1204831580] [2025-03-16 18:09:25,897 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1204831580] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:09:25,897 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [190500923] [2025-03-16 18:09:25,898 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:09:25,898 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:09:25,898 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:09:25,899 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:09:25,901 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:09:25,928 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 55 statements into 1 equivalence classes. [2025-03-16 18:09:25,944 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 55 of 55 statements. [2025-03-16 18:09:25,944 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:09:25,944 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:09:25,945 INFO L256 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-16 18:09:25,947 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:09:26,007 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:09:26,007 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:09:26,077 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:09:26,077 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [190500923] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:09:26,078 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 18:09:26,078 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 5, 6] total 9 [2025-03-16 18:09:26,078 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [747606754] [2025-03-16 18:09:26,078 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 18:09:26,078 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2025-03-16 18:09:26,078 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:09:26,078 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2025-03-16 18:09:26,079 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=46, Unknown=0, NotChecked=0, Total=72 [2025-03-16 18:09:26,079 INFO L87 Difference]: Start difference. First operand 57 states and 70 transitions. Second operand has 9 states, 9 states have (on average 4.111111111111111) internal successors, (37), 9 states have internal predecessors, (37), 4 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 3 states have call predecessors, (24), 3 states have call successors, (24) [2025-03-16 18:09:26,203 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:09:26,203 INFO L93 Difference]: Finished difference Result 168 states and 197 transitions. [2025-03-16 18:09:26,204 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2025-03-16 18:09:26,204 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 4.111111111111111) internal successors, (37), 9 states have internal predecessors, (37), 4 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 3 states have call predecessors, (24), 3 states have call successors, (24) Word has length 55 [2025-03-16 18:09:26,204 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:09:26,205 INFO L225 Difference]: With dead ends: 168 [2025-03-16 18:09:26,205 INFO L226 Difference]: Without dead ends: 160 [2025-03-16 18:09:26,206 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 117 GetRequests, 106 SyntacticMatches, 1 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=47, Invalid=85, Unknown=0, NotChecked=0, Total=132 [2025-03-16 18:09:26,206 INFO L435 NwaCegarLoop]: 37 mSDtfsCounter, 40 mSDsluCounter, 146 mSDsCounter, 0 mSdLazyCounter, 72 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 40 SdHoareTripleChecker+Valid, 183 SdHoareTripleChecker+Invalid, 74 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 72 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:09:26,206 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [40 Valid, 183 Invalid, 74 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 72 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 18:09:26,206 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 160 states. [2025-03-16 18:09:26,223 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 160 to 154. [2025-03-16 18:09:26,224 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 154 states, 99 states have (on average 1.1818181818181819) internal successors, (117), 102 states have internal predecessors, (117), 34 states have call successors, (34), 20 states have call predecessors, (34), 20 states have return successors, (31), 31 states have call predecessors, (31), 31 states have call successors, (31) [2025-03-16 18:09:26,224 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 154 states to 154 states and 182 transitions. [2025-03-16 18:09:26,225 INFO L78 Accepts]: Start accepts. Automaton has 154 states and 182 transitions. Word has length 55 [2025-03-16 18:09:26,225 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:09:26,225 INFO L471 AbstractCegarLoop]: Abstraction has 154 states and 182 transitions. [2025-03-16 18:09:26,225 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 4.111111111111111) internal successors, (37), 9 states have internal predecessors, (37), 4 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 3 states have call predecessors, (24), 3 states have call successors, (24) [2025-03-16 18:09:26,225 INFO L276 IsEmpty]: Start isEmpty. Operand 154 states and 182 transitions. [2025-03-16 18:09:26,226 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2025-03-16 18:09:26,226 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:09:26,226 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:09:26,232 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:09:26,426 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:09:26,427 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:09:26,427 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:09:26,427 INFO L85 PathProgramCache]: Analyzing trace with hash 1897660899, now seen corresponding path program 1 times [2025-03-16 18:09:26,427 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:09:26,427 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1870491519] [2025-03-16 18:09:26,427 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:09:26,427 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:09:26,431 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 56 statements into 1 equivalence classes. [2025-03-16 18:09:26,437 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 56 of 56 statements. [2025-03-16 18:09:26,437 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:09:26,437 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:09:26,541 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 12 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2025-03-16 18:09:26,541 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:09:26,541 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1870491519] [2025-03-16 18:09:26,541 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1870491519] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:09:26,541 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1501229823] [2025-03-16 18:09:26,541 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:09:26,541 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:09:26,541 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:09:26,543 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:09:26,544 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:09:26,570 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 56 statements into 1 equivalence classes. [2025-03-16 18:09:26,585 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 56 of 56 statements. [2025-03-16 18:09:26,585 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:09:26,585 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:09:26,586 INFO L256 TraceCheckSpWp]: Trace formula consists of 163 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-03-16 18:09:26,587 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:09:26,624 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 12 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2025-03-16 18:09:26,624 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:09:26,702 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 12 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2025-03-16 18:09:26,702 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1501229823] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:09:26,702 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 18:09:26,702 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 9 [2025-03-16 18:09:26,702 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [468176585] [2025-03-16 18:09:26,702 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 18:09:26,703 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2025-03-16 18:09:26,703 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:09:26,703 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2025-03-16 18:09:26,703 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2025-03-16 18:09:26,703 INFO L87 Difference]: Start difference. First operand 154 states and 182 transitions. Second operand has 9 states, 9 states have (on average 2.888888888888889) internal successors, (26), 8 states have internal predecessors, (26), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2025-03-16 18:09:26,855 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:09:26,855 INFO L93 Difference]: Finished difference Result 220 states and 287 transitions. [2025-03-16 18:09:26,856 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-03-16 18:09:26,856 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.888888888888889) internal successors, (26), 8 states have internal predecessors, (26), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) Word has length 56 [2025-03-16 18:09:26,856 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:09:26,857 INFO L225 Difference]: With dead ends: 220 [2025-03-16 18:09:26,857 INFO L226 Difference]: Without dead ends: 206 [2025-03-16 18:09:26,858 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 123 GetRequests, 107 SyntacticMatches, 4 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=48, Invalid=134, Unknown=0, NotChecked=0, Total=182 [2025-03-16 18:09:26,858 INFO L435 NwaCegarLoop]: 48 mSDtfsCounter, 57 mSDsluCounter, 200 mSDsCounter, 0 mSdLazyCounter, 72 mSolverCounterSat, 36 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 62 SdHoareTripleChecker+Valid, 248 SdHoareTripleChecker+Invalid, 108 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 36 IncrementalHoareTripleChecker+Valid, 72 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:09:26,858 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [62 Valid, 248 Invalid, 108 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [36 Valid, 72 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 18:09:26,859 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 206 states. [2025-03-16 18:09:26,878 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 206 to 184. [2025-03-16 18:09:26,878 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 184 states, 120 states have (on average 1.2166666666666666) internal successors, (146), 122 states have internal predecessors, (146), 44 states have call successors, (44), 19 states have call predecessors, (44), 19 states have return successors, (42), 42 states have call predecessors, (42), 42 states have call successors, (42) [2025-03-16 18:09:26,880 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 184 states to 184 states and 232 transitions. [2025-03-16 18:09:26,881 INFO L78 Accepts]: Start accepts. Automaton has 184 states and 232 transitions. Word has length 56 [2025-03-16 18:09:26,881 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:09:26,881 INFO L471 AbstractCegarLoop]: Abstraction has 184 states and 232 transitions. [2025-03-16 18:09:26,881 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.888888888888889) internal successors, (26), 8 states have internal predecessors, (26), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2025-03-16 18:09:26,881 INFO L276 IsEmpty]: Start isEmpty. Operand 184 states and 232 transitions. [2025-03-16 18:09:26,882 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2025-03-16 18:09:26,882 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:09:26,882 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:09:26,888 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:09:27,082 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:09:27,083 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:09:27,083 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:09:27,083 INFO L85 PathProgramCache]: Analyzing trace with hash 113568804, now seen corresponding path program 1 times [2025-03-16 18:09:27,083 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:09:27,083 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1964782529] [2025-03-16 18:09:27,083 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:09:27,083 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:09:27,087 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 58 statements into 1 equivalence classes. [2025-03-16 18:09:27,091 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 58 of 58 statements. [2025-03-16 18:09:27,091 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:09:27,091 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:09:27,143 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2025-03-16 18:09:27,144 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:09:27,144 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1964782529] [2025-03-16 18:09:27,144 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1964782529] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:09:27,144 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [563569245] [2025-03-16 18:09:27,144 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:09:27,144 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:09:27,144 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:09:27,146 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:09:27,148 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:09:27,172 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 58 statements into 1 equivalence classes. [2025-03-16 18:09:27,186 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 58 of 58 statements. [2025-03-16 18:09:27,186 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:09:27,187 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:09:27,187 INFO L256 TraceCheckSpWp]: Trace formula consists of 172 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-16 18:09:27,189 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:09:27,233 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2025-03-16 18:09:27,234 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:09:27,310 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2025-03-16 18:09:27,310 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [563569245] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:09:27,310 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 18:09:27,311 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 5, 6] total 9 [2025-03-16 18:09:27,311 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [481539838] [2025-03-16 18:09:27,311 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 18:09:27,311 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2025-03-16 18:09:27,311 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:09:27,312 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2025-03-16 18:09:27,312 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=46, Unknown=0, NotChecked=0, Total=72 [2025-03-16 18:09:27,312 INFO L87 Difference]: Start difference. First operand 184 states and 232 transitions. Second operand has 9 states, 9 states have (on average 4.333333333333333) internal successors, (39), 9 states have internal predecessors, (39), 4 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 3 states have call predecessors, (24), 3 states have call successors, (24) [2025-03-16 18:09:27,439 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:09:27,439 INFO L93 Difference]: Finished difference Result 264 states and 345 transitions. [2025-03-16 18:09:27,439 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2025-03-16 18:09:27,440 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 4.333333333333333) internal successors, (39), 9 states have internal predecessors, (39), 4 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 3 states have call predecessors, (24), 3 states have call successors, (24) Word has length 58 [2025-03-16 18:09:27,440 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:09:27,441 INFO L225 Difference]: With dead ends: 264 [2025-03-16 18:09:27,441 INFO L226 Difference]: Without dead ends: 192 [2025-03-16 18:09:27,442 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 123 GetRequests, 112 SyntacticMatches, 1 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=46, Invalid=86, Unknown=0, NotChecked=0, Total=132 [2025-03-16 18:09:27,442 INFO L435 NwaCegarLoop]: 37 mSDtfsCounter, 39 mSDsluCounter, 133 mSDsCounter, 0 mSdLazyCounter, 59 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 39 SdHoareTripleChecker+Valid, 170 SdHoareTripleChecker+Invalid, 65 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 59 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:09:27,442 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [39 Valid, 170 Invalid, 65 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 59 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 18:09:27,442 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 192 states. [2025-03-16 18:09:27,459 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 192 to 190. [2025-03-16 18:09:27,459 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 190 states, 126 states have (on average 1.1825396825396826) internal successors, (149), 128 states have internal predecessors, (149), 44 states have call successors, (44), 19 states have call predecessors, (44), 19 states have return successors, (42), 42 states have call predecessors, (42), 42 states have call successors, (42) [2025-03-16 18:09:27,460 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 190 states to 190 states and 235 transitions. [2025-03-16 18:09:27,460 INFO L78 Accepts]: Start accepts. Automaton has 190 states and 235 transitions. Word has length 58 [2025-03-16 18:09:27,460 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:09:27,461 INFO L471 AbstractCegarLoop]: Abstraction has 190 states and 235 transitions. [2025-03-16 18:09:27,461 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 4.333333333333333) internal successors, (39), 9 states have internal predecessors, (39), 4 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 3 states have call predecessors, (24), 3 states have call successors, (24) [2025-03-16 18:09:27,461 INFO L276 IsEmpty]: Start isEmpty. Operand 190 states and 235 transitions. [2025-03-16 18:09:27,461 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 64 [2025-03-16 18:09:27,461 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:09:27,461 INFO L218 NwaCegarLoop]: trace histogram [6, 5, 5, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:09:27,467 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2025-03-16 18:09:27,661 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,SelfDestructingSolverStorable10 [2025-03-16 18:09:27,662 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:09:27,662 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:09:27,662 INFO L85 PathProgramCache]: Analyzing trace with hash 935044587, now seen corresponding path program 1 times [2025-03-16 18:09:27,662 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:09:27,662 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1239919550] [2025-03-16 18:09:27,663 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:09:27,663 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:09:27,666 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 63 statements into 1 equivalence classes. [2025-03-16 18:09:27,674 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 63 of 63 statements. [2025-03-16 18:09:27,674 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:09:27,674 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:09:27,675 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1072677323] [2025-03-16 18:09:27,675 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:09:27,675 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:09:27,675 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:09:27,677 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:09:27,679 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:09:27,703 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 63 statements into 1 equivalence classes. [2025-03-16 18:09:27,721 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 63 of 63 statements. [2025-03-16 18:09:27,721 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:09:27,721 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:09:27,722 INFO L256 TraceCheckSpWp]: Trace formula consists of 180 conjuncts, 17 conjuncts are in the unsatisfiable core [2025-03-16 18:09:27,723 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:09:27,834 INFO L134 CoverageAnalysis]: Checked inductivity of 81 backedges. 10 proven. 7 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2025-03-16 18:09:27,834 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:09:27,860 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:09:27,861 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1239919550] [2025-03-16 18:09:27,861 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:09:27,861 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1072677323] [2025-03-16 18:09:27,861 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1072677323] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:09:27,861 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-16 18:09:27,861 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6] total 6 [2025-03-16 18:09:27,861 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2031105672] [2025-03-16 18:09:27,861 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-16 18:09:27,861 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2025-03-16 18:09:27,861 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:09:27,862 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-03-16 18:09:27,862 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2025-03-16 18:09:27,862 INFO L87 Difference]: Start difference. First operand 190 states and 235 transitions. Second operand has 6 states, 6 states have (on average 3.8333333333333335) internal successors, (23), 5 states have internal predecessors, (23), 3 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2025-03-16 18:09:27,950 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:09:27,950 INFO L93 Difference]: Finished difference Result 222 states and 281 transitions. [2025-03-16 18:09:27,951 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-16 18:09:27,951 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 3.8333333333333335) internal successors, (23), 5 states have internal predecessors, (23), 3 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) Word has length 63 [2025-03-16 18:09:27,951 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:09:27,953 INFO L225 Difference]: With dead ends: 222 [2025-03-16 18:09:27,953 INFO L226 Difference]: Without dead ends: 218 [2025-03-16 18:09:27,954 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 68 GetRequests, 60 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=16, Invalid=40, Unknown=0, NotChecked=0, Total=56 [2025-03-16 18:09:27,954 INFO L435 NwaCegarLoop]: 52 mSDtfsCounter, 10 mSDsluCounter, 156 mSDsCounter, 0 mSdLazyCounter, 67 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 208 SdHoareTripleChecker+Invalid, 69 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 67 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:09:27,954 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 208 Invalid, 69 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 67 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 18:09:27,954 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 218 states. [2025-03-16 18:09:27,981 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 218 to 216. [2025-03-16 18:09:27,982 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 216 states, 142 states have (on average 1.204225352112676) internal successors, (171), 145 states have internal predecessors, (171), 52 states have call successors, (52), 21 states have call predecessors, (52), 21 states have return successors, (49), 49 states have call predecessors, (49), 49 states have call successors, (49) [2025-03-16 18:09:27,984 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 216 states to 216 states and 272 transitions. [2025-03-16 18:09:27,985 INFO L78 Accepts]: Start accepts. Automaton has 216 states and 272 transitions. Word has length 63 [2025-03-16 18:09:27,985 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:09:27,985 INFO L471 AbstractCegarLoop]: Abstraction has 216 states and 272 transitions. [2025-03-16 18:09:27,985 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 3.8333333333333335) internal successors, (23), 5 states have internal predecessors, (23), 3 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2025-03-16 18:09:27,985 INFO L276 IsEmpty]: Start isEmpty. Operand 216 states and 272 transitions. [2025-03-16 18:09:27,986 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 69 [2025-03-16 18:09:27,986 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:09:27,986 INFO L218 NwaCegarLoop]: trace histogram [7, 6, 6, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:09:27,992 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:09:28,186 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:09:28,187 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:09:28,187 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:09:28,187 INFO L85 PathProgramCache]: Analyzing trace with hash -1000964517, now seen corresponding path program 2 times [2025-03-16 18:09:28,187 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:09:28,187 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1710811835] [2025-03-16 18:09:28,187 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:09:28,187 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:09:28,193 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 68 statements into 2 equivalence classes. [2025-03-16 18:09:28,213 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 68 of 68 statements. [2025-03-16 18:09:28,213 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:09:28,213 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:09:28,214 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [298033715] [2025-03-16 18:09:28,214 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:09:28,214 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:09:28,214 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:09:28,216 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:09:28,218 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:09:28,245 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 68 statements into 2 equivalence classes. [2025-03-16 18:09:28,264 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 68 of 68 statements. [2025-03-16 18:09:28,265 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:09:28,265 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:09:28,265 INFO L256 TraceCheckSpWp]: Trace formula consists of 189 conjuncts, 23 conjuncts are in the unsatisfiable core [2025-03-16 18:09:28,267 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:09:28,468 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 12 proven. 8 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2025-03-16 18:09:28,468 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:09:28,554 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:09:28,554 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1710811835] [2025-03-16 18:09:28,554 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:09:28,554 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [298033715] [2025-03-16 18:09:28,554 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [298033715] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:09:28,554 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-16 18:09:28,554 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2025-03-16 18:09:28,554 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1734287071] [2025-03-16 18:09:28,554 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-16 18:09:28,555 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2025-03-16 18:09:28,555 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:09:28,555 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2025-03-16 18:09:28,555 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2025-03-16 18:09:28,555 INFO L87 Difference]: Start difference. First operand 216 states and 272 transitions. Second operand has 7 states, 7 states have (on average 3.2857142857142856) internal successors, (23), 6 states have internal predecessors, (23), 4 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) [2025-03-16 18:09:28,674 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:09:28,674 INFO L93 Difference]: Finished difference Result 227 states and 282 transitions. [2025-03-16 18:09:28,675 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2025-03-16 18:09:28,675 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 3.2857142857142856) internal successors, (23), 6 states have internal predecessors, (23), 4 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) Word has length 68 [2025-03-16 18:09:28,675 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:09:28,676 INFO L225 Difference]: With dead ends: 227 [2025-03-16 18:09:28,676 INFO L226 Difference]: Without dead ends: 225 [2025-03-16 18:09:28,676 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 91 GetRequests, 80 SyntacticMatches, 2 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=26, Invalid=84, Unknown=0, NotChecked=0, Total=110 [2025-03-16 18:09:28,677 INFO L435 NwaCegarLoop]: 45 mSDtfsCounter, 16 mSDsluCounter, 177 mSDsCounter, 0 mSdLazyCounter, 96 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 222 SdHoareTripleChecker+Invalid, 103 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 96 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:09:28,677 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 222 Invalid, 103 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 96 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 18:09:28,677 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 225 states. [2025-03-16 18:09:28,704 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 225 to 224. [2025-03-16 18:09:28,704 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 224 states, 148 states have (on average 1.195945945945946) internal successors, (177), 151 states have internal predecessors, (177), 52 states have call successors, (52), 23 states have call predecessors, (52), 23 states have return successors, (49), 49 states have call predecessors, (49), 49 states have call successors, (49) [2025-03-16 18:09:28,705 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 224 states to 224 states and 278 transitions. [2025-03-16 18:09:28,706 INFO L78 Accepts]: Start accepts. Automaton has 224 states and 278 transitions. Word has length 68 [2025-03-16 18:09:28,706 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:09:28,706 INFO L471 AbstractCegarLoop]: Abstraction has 224 states and 278 transitions. [2025-03-16 18:09:28,706 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 3.2857142857142856) internal successors, (23), 6 states have internal predecessors, (23), 4 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) [2025-03-16 18:09:28,706 INFO L276 IsEmpty]: Start isEmpty. Operand 224 states and 278 transitions. [2025-03-16 18:09:28,707 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2025-03-16 18:09:28,707 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:09:28,707 INFO L218 NwaCegarLoop]: trace histogram [8, 7, 7, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:09:28,713 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2025-03-16 18:09:28,911 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,SelfDestructingSolverStorable12 [2025-03-16 18:09:28,911 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:09:28,911 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:09:28,911 INFO L85 PathProgramCache]: Analyzing trace with hash 1573147691, now seen corresponding path program 3 times [2025-03-16 18:09:28,911 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:09:28,912 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1864592611] [2025-03-16 18:09:28,912 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 18:09:28,912 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:09:28,917 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 73 statements into 5 equivalence classes. [2025-03-16 18:09:28,936 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) and asserted 73 of 73 statements. [2025-03-16 18:09:28,937 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2025-03-16 18:09:28,937 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:09:28,937 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [508915122] [2025-03-16 18:09:28,938 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 18:09:28,938 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:09:28,938 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:09:28,940 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:09:28,945 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:09:28,968 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 73 statements into 5 equivalence classes. [2025-03-16 18:09:28,987 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) and asserted 53 of 73 statements. [2025-03-16 18:09:28,987 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2025-03-16 18:09:28,987 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:09:28,988 INFO L256 TraceCheckSpWp]: Trace formula consists of 162 conjuncts, 42 conjuncts are in the unsatisfiable core [2025-03-16 18:09:28,991 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:09:29,345 INFO L134 CoverageAnalysis]: Checked inductivity of 131 backedges. 40 proven. 10 refuted. 0 times theorem prover too weak. 81 trivial. 0 not checked. [2025-03-16 18:09:29,345 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:09:29,546 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:09:29,546 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1864592611] [2025-03-16 18:09:29,546 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:09:29,546 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [508915122] [2025-03-16 18:09:29,546 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [508915122] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:09:29,547 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-16 18:09:29,547 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2025-03-16 18:09:29,547 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1826977481] [2025-03-16 18:09:29,547 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-16 18:09:29,547 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2025-03-16 18:09:29,547 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:09:29,547 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2025-03-16 18:09:29,548 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=41, Invalid=231, Unknown=0, NotChecked=0, Total=272 [2025-03-16 18:09:29,548 INFO L87 Difference]: Start difference. First operand 224 states and 278 transitions. Second operand has 12 states, 11 states have (on average 2.6363636363636362) internal successors, (29), 11 states have internal predecessors, (29), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 5 states have call predecessors, (11), 4 states have call successors, (11) [2025-03-16 18:09:29,751 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:09:29,752 INFO L93 Difference]: Finished difference Result 235 states and 288 transitions. [2025-03-16 18:09:29,752 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2025-03-16 18:09:29,752 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 2.6363636363636362) internal successors, (29), 11 states have internal predecessors, (29), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 5 states have call predecessors, (11), 4 states have call successors, (11) Word has length 73 [2025-03-16 18:09:29,752 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:09:29,753 INFO L225 Difference]: With dead ends: 235 [2025-03-16 18:09:29,753 INFO L226 Difference]: Without dead ends: 231 [2025-03-16 18:09:29,754 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 101 GetRequests, 84 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 30 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=55, Invalid=287, Unknown=0, NotChecked=0, Total=342 [2025-03-16 18:09:29,754 INFO L435 NwaCegarLoop]: 33 mSDtfsCounter, 26 mSDsluCounter, 238 mSDsCounter, 0 mSdLazyCounter, 271 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 31 SdHoareTripleChecker+Valid, 271 SdHoareTripleChecker+Invalid, 287 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 271 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-16 18:09:29,754 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [31 Valid, 271 Invalid, 287 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 271 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-16 18:09:29,755 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 231 states. [2025-03-16 18:09:29,770 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 231 to 230. [2025-03-16 18:09:29,770 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 230 states, 153 states have (on average 1.1830065359477124) internal successors, (181), 155 states have internal predecessors, (181), 52 states have call successors, (52), 25 states have call predecessors, (52), 24 states have return successors, (49), 49 states have call predecessors, (49), 49 states have call successors, (49) [2025-03-16 18:09:29,771 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 230 states to 230 states and 282 transitions. [2025-03-16 18:09:29,771 INFO L78 Accepts]: Start accepts. Automaton has 230 states and 282 transitions. Word has length 73 [2025-03-16 18:09:29,772 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:09:29,772 INFO L471 AbstractCegarLoop]: Abstraction has 230 states and 282 transitions. [2025-03-16 18:09:29,772 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 2.6363636363636362) internal successors, (29), 11 states have internal predecessors, (29), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 5 states have call predecessors, (11), 4 states have call successors, (11) [2025-03-16 18:09:29,772 INFO L276 IsEmpty]: Start isEmpty. Operand 230 states and 282 transitions. [2025-03-16 18:09:29,772 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 80 [2025-03-16 18:09:29,772 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:09:29,773 INFO L218 NwaCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:09:29,779 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2025-03-16 18:09:29,973 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,SelfDestructingSolverStorable13 [2025-03-16 18:09:29,973 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:09:29,974 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:09:29,974 INFO L85 PathProgramCache]: Analyzing trace with hash -92347712, now seen corresponding path program 1 times [2025-03-16 18:09:29,974 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:09:29,974 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [835137139] [2025-03-16 18:09:29,974 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:09:29,974 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:09:29,978 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 79 statements into 1 equivalence classes. [2025-03-16 18:09:29,987 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 79 of 79 statements. [2025-03-16 18:09:29,988 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:09:29,988 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:09:29,989 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [197154822] [2025-03-16 18:09:29,989 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:09:29,989 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:09:29,989 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:09:29,990 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:09:29,992 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:09:30,018 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 79 statements into 1 equivalence classes. [2025-03-16 18:09:30,037 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 79 of 79 statements. [2025-03-16 18:09:30,037 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:09:30,038 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:09:30,039 INFO L256 TraceCheckSpWp]: Trace formula consists of 209 conjuncts, 41 conjuncts are in the unsatisfiable core [2025-03-16 18:09:30,040 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:09:30,507 INFO L134 CoverageAnalysis]: Checked inductivity of 162 backedges. 16 proven. 19 refuted. 0 times theorem prover too weak. 127 trivial. 0 not checked. [2025-03-16 18:09:30,507 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:09:30,901 INFO L134 CoverageAnalysis]: Checked inductivity of 162 backedges. 16 proven. 10 refuted. 0 times theorem prover too weak. 136 trivial. 0 not checked. [2025-03-16 18:09:30,902 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:09:30,902 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [835137139] [2025-03-16 18:09:30,902 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:09:30,902 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [197154822] [2025-03-16 18:09:30,902 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [197154822] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:09:30,902 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:09:30,902 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 10] total 21 [2025-03-16 18:09:30,902 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1080276420] [2025-03-16 18:09:30,902 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:09:30,902 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2025-03-16 18:09:30,902 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:09:30,903 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2025-03-16 18:09:30,903 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=64, Invalid=356, Unknown=0, NotChecked=0, Total=420 [2025-03-16 18:09:30,903 INFO L87 Difference]: Start difference. First operand 230 states and 282 transitions. Second operand has 21 states, 19 states have (on average 2.263157894736842) internal successors, (43), 18 states have internal predecessors, (43), 10 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2025-03-16 18:09:33,011 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:09:33,011 INFO L93 Difference]: Finished difference Result 383 states and 537 transitions. [2025-03-16 18:09:33,011 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2025-03-16 18:09:33,012 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 19 states have (on average 2.263157894736842) internal successors, (43), 18 states have internal predecessors, (43), 10 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) Word has length 79 [2025-03-16 18:09:33,012 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:09:33,013 INFO L225 Difference]: With dead ends: 383 [2025-03-16 18:09:33,013 INFO L226 Difference]: Without dead ends: 377 [2025-03-16 18:09:33,014 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 175 GetRequests, 137 SyntacticMatches, 0 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 259 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=296, Invalid=1264, Unknown=0, NotChecked=0, Total=1560 [2025-03-16 18:09:33,014 INFO L435 NwaCegarLoop]: 59 mSDtfsCounter, 131 mSDsluCounter, 627 mSDsCounter, 0 mSdLazyCounter, 568 mSolverCounterSat, 108 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 136 SdHoareTripleChecker+Valid, 686 SdHoareTripleChecker+Invalid, 676 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 108 IncrementalHoareTripleChecker+Valid, 568 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.4s IncrementalHoareTripleChecker+Time [2025-03-16 18:09:33,014 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [136 Valid, 686 Invalid, 676 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [108 Valid, 568 Invalid, 0 Unknown, 0 Unchecked, 1.4s Time] [2025-03-16 18:09:33,015 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 377 states. [2025-03-16 18:09:33,062 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 377 to 338. [2025-03-16 18:09:33,063 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 338 states, 212 states have (on average 1.2830188679245282) internal successors, (272), 215 states have internal predecessors, (272), 100 states have call successors, (100), 25 states have call predecessors, (100), 25 states have return successors, (98), 97 states have call predecessors, (98), 98 states have call successors, (98) [2025-03-16 18:09:33,064 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 338 states to 338 states and 470 transitions. [2025-03-16 18:09:33,065 INFO L78 Accepts]: Start accepts. Automaton has 338 states and 470 transitions. Word has length 79 [2025-03-16 18:09:33,065 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:09:33,065 INFO L471 AbstractCegarLoop]: Abstraction has 338 states and 470 transitions. [2025-03-16 18:09:33,066 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 19 states have (on average 2.263157894736842) internal successors, (43), 18 states have internal predecessors, (43), 10 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2025-03-16 18:09:33,066 INFO L276 IsEmpty]: Start isEmpty. Operand 338 states and 470 transitions. [2025-03-16 18:09:33,066 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 89 [2025-03-16 18:09:33,067 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:09:33,067 INFO L218 NwaCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 4, 3, 3, 3, 3, 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:09:33,077 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2025-03-16 18:09:33,267 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,SelfDestructingSolverStorable14 [2025-03-16 18:09:33,268 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:09:33,268 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:09:33,268 INFO L85 PathProgramCache]: Analyzing trace with hash 1736584487, now seen corresponding path program 1 times [2025-03-16 18:09:33,268 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:09:33,268 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [741119169] [2025-03-16 18:09:33,268 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:09:33,268 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:09:33,273 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 88 statements into 1 equivalence classes. [2025-03-16 18:09:33,284 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 88 of 88 statements. [2025-03-16 18:09:33,284 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:09:33,284 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:09:33,353 INFO L134 CoverageAnalysis]: Checked inductivity of 181 backedges. 42 proven. 0 refuted. 0 times theorem prover too weak. 139 trivial. 0 not checked. [2025-03-16 18:09:33,353 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:09:33,354 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [741119169] [2025-03-16 18:09:33,354 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [741119169] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 18:09:33,354 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 18:09:33,354 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-16 18:09:33,354 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [145458637] [2025-03-16 18:09:33,354 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:09:33,354 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-16 18:09:33,354 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:09:33,354 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-16 18:09:33,354 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-16 18:09:33,354 INFO L87 Difference]: Start difference. First operand 338 states and 470 transitions. Second operand has 5 states, 5 states have (on average 6.2) internal successors, (31), 5 states have internal predecessors, (31), 3 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) [2025-03-16 18:09:33,471 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:09:33,471 INFO L93 Difference]: Finished difference Result 534 states and 788 transitions. [2025-03-16 18:09:33,473 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-16 18:09:33,473 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 6.2) internal successors, (31), 5 states have internal predecessors, (31), 3 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) Word has length 88 [2025-03-16 18:09:33,473 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:09:33,476 INFO L225 Difference]: With dead ends: 534 [2025-03-16 18:09:33,476 INFO L226 Difference]: Without dead ends: 415 [2025-03-16 18:09:33,476 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:09:33,477 INFO L435 NwaCegarLoop]: 51 mSDtfsCounter, 11 mSDsluCounter, 118 mSDsCounter, 0 mSdLazyCounter, 46 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 169 SdHoareTripleChecker+Invalid, 50 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 46 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-16 18:09:33,477 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 169 Invalid, 50 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 46 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 18:09:33,477 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 415 states. [2025-03-16 18:09:33,535 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 415 to 363. [2025-03-16 18:09:33,535 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 363 states, 229 states have (on average 1.2838427947598254) internal successors, (294), 232 states have internal predecessors, (294), 108 states have call successors, (108), 25 states have call predecessors, (108), 25 states have return successors, (106), 105 states have call predecessors, (106), 106 states have call successors, (106) [2025-03-16 18:09:33,537 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 363 states to 363 states and 508 transitions. [2025-03-16 18:09:33,538 INFO L78 Accepts]: Start accepts. Automaton has 363 states and 508 transitions. Word has length 88 [2025-03-16 18:09:33,538 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:09:33,538 INFO L471 AbstractCegarLoop]: Abstraction has 363 states and 508 transitions. [2025-03-16 18:09:33,538 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 6.2) internal successors, (31), 5 states have internal predecessors, (31), 3 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) [2025-03-16 18:09:33,538 INFO L276 IsEmpty]: Start isEmpty. Operand 363 states and 508 transitions. [2025-03-16 18:09:33,539 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 97 [2025-03-16 18:09:33,539 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:09:33,539 INFO L218 NwaCegarLoop]: trace histogram [12, 11, 11, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:09:33,539 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable15 [2025-03-16 18:09:33,539 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:09:33,539 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:09:33,539 INFO L85 PathProgramCache]: Analyzing trace with hash -596793106, now seen corresponding path program 1 times [2025-03-16 18:09:33,539 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:09:33,540 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [993462334] [2025-03-16 18:09:33,540 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:09:33,540 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:09:33,544 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 96 statements into 1 equivalence classes. [2025-03-16 18:09:33,554 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 96 of 96 statements. [2025-03-16 18:09:33,554 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:09:33,554 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:09:33,555 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [739146666] [2025-03-16 18:09:33,555 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:09:33,556 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:09:33,556 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:09:33,558 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:09:33,563 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:09:33,592 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 96 statements into 1 equivalence classes. [2025-03-16 18:09:33,617 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 96 of 96 statements. [2025-03-16 18:09:33,617 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:09:33,617 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:09:33,619 INFO L256 TraceCheckSpWp]: Trace formula consists of 244 conjuncts, 53 conjuncts are in the unsatisfiable core [2025-03-16 18:09:33,621 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:09:34,400 INFO L134 CoverageAnalysis]: Checked inductivity of 288 backedges. 68 proven. 39 refuted. 0 times theorem prover too weak. 181 trivial. 0 not checked. [2025-03-16 18:09:34,400 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:10:11,571 INFO L134 CoverageAnalysis]: Checked inductivity of 288 backedges. 68 proven. 30 refuted. 0 times theorem prover too weak. 190 trivial. 0 not checked. [2025-03-16 18:10:11,571 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:10:11,571 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [993462334] [2025-03-16 18:10:11,571 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:10:11,571 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [739146666] [2025-03-16 18:10:11,571 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [739146666] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:10:11,571 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:10:11,571 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 13] total 26 [2025-03-16 18:10:11,571 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [325889430] [2025-03-16 18:10:11,571 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:10:11,572 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2025-03-16 18:10:11,572 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:10:11,572 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2025-03-16 18:10:11,572 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=111, Invalid=538, Unknown=1, NotChecked=0, Total=650 [2025-03-16 18:10:11,572 INFO L87 Difference]: Start difference. First operand 363 states and 508 transitions. Second operand has 26 states, 25 states have (on average 2.08) internal successors, (52), 21 states have internal predecessors, (52), 11 states have call successors, (31), 3 states have call predecessors, (31), 3 states have return successors, (30), 13 states have call predecessors, (30), 10 states have call successors, (30) [2025-03-16 18:10:16,158 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2025-03-16 18:10:30,419 WARN L286 SmtUtils]: Spent 5.43s on a formula simplification. DAG size of input: 60 DAG size of output: 59 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2025-03-16 18:10:44,160 WARN L286 SmtUtils]: Spent 12.54s on a formula simplification. DAG size of input: 69 DAG size of output: 68 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2025-03-16 18:10:57,496 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2025-03-16 18:11:01,508 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2025-03-16 18:11:06,542 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers []