./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 e2fb8bed 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-?-e2fb8be-m [2025-03-08 05:00:39,355 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-08 05:00:39,415 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2025-03-08 05:00:39,419 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-08 05:00:39,419 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-08 05:00:39,432 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-08 05:00:39,433 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-08 05:00:39,433 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-08 05:00:39,433 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-08 05:00:39,434 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-08 05:00:39,434 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-03-08 05:00:39,434 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-03-08 05:00:39,434 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-08 05:00:39,434 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-08 05:00:39,434 INFO L153 SettingsManager]: * Use SBE=true [2025-03-08 05:00:39,434 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-08 05:00:39,434 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-03-08 05:00:39,435 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-08 05:00:39,435 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-08 05:00:39,435 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-08 05:00:39,435 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-08 05:00:39,435 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-03-08 05:00:39,435 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-03-08 05:00:39,435 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-03-08 05:00:39,435 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-08 05:00:39,435 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-08 05:00:39,435 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-08 05:00:39,435 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-08 05:00:39,435 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-08 05:00:39,436 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-08 05:00:39,436 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-03-08 05:00:39,436 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-03-08 05:00:39,436 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-08 05:00:39,436 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-08 05:00:39,436 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-03-08 05:00:39,436 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-03-08 05:00:39,436 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-03-08 05:00:39,436 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-08 05:00:39,436 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-03-08 05:00:39,436 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-03-08 05:00:39,437 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-03-08 05:00:39,437 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-03-08 05:00:39,437 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-03-08 05:00:39,437 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-08 05:00:39,709 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-08 05:00:39,715 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-08 05:00:39,716 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-08 05:00:39,717 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-08 05:00:39,717 INFO L274 PluginConnector]: CDTParser initialized [2025-03-08 05:00:39,718 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-08 05:00:40,965 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/ce2fcb5ae/939ce7271a4544a28fc80f14d46ba3e9/FLAGac2998d37 [2025-03-08 05:00:41,191 INFO L384 CDTParser]: Found 1 translation units. [2025-03-08 05:00:41,193 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound5.c [2025-03-08 05:00:41,201 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/ce2fcb5ae/939ce7271a4544a28fc80f14d46ba3e9/FLAGac2998d37 [2025-03-08 05:00:41,217 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/ce2fcb5ae/939ce7271a4544a28fc80f14d46ba3e9 [2025-03-08 05:00:41,220 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-08 05:00:41,221 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-08 05:00:41,222 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-08 05:00:41,222 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-08 05:00:41,225 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-08 05:00:41,226 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.03 05:00:41" (1/1) ... [2025-03-08 05:00:41,227 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@5570a193 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:00:41, skipping insertion in model container [2025-03-08 05:00:41,227 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.03 05:00:41" (1/1) ... [2025-03-08 05:00:41,240 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-08 05:00:41,350 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-08 05:00:41,366 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-08 05:00:41,373 INFO L200 MainTranslator]: Completed pre-run [2025-03-08 05:00:41,383 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-08 05:00:41,391 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-08 05:00:41,408 INFO L204 MainTranslator]: Completed translation [2025-03-08 05:00:41,409 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:00:41 WrapperNode [2025-03-08 05:00:41,409 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-08 05:00:41,410 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-08 05:00:41,410 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-08 05:00:41,410 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-08 05:00:41,415 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:00:41" (1/1) ... [2025-03-08 05:00:41,418 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:00:41" (1/1) ... [2025-03-08 05:00:41,431 INFO L138 Inliner]: procedures = 14, calls = 17, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 84 [2025-03-08 05:00:41,432 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-08 05:00:41,432 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-08 05:00:41,432 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-08 05:00:41,432 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-08 05:00:41,438 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:00:41" (1/1) ... [2025-03-08 05:00:41,438 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:00:41" (1/1) ... [2025-03-08 05:00:41,439 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:00:41" (1/1) ... [2025-03-08 05:00:41,449 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-08 05:00:41,450 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:00:41" (1/1) ... [2025-03-08 05:00:41,450 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:00:41" (1/1) ... [2025-03-08 05:00:41,452 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:00:41" (1/1) ... [2025-03-08 05:00:41,453 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:00:41" (1/1) ... [2025-03-08 05:00:41,454 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:00:41" (1/1) ... [2025-03-08 05:00:41,454 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:00:41" (1/1) ... [2025-03-08 05:00:41,455 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-08 05:00:41,458 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-08 05:00:41,458 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-08 05:00:41,458 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-08 05:00:41,459 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:00:41" (1/1) ... [2025-03-08 05:00:41,466 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-08 05:00:41,477 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:00:41,491 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-08 05:00:41,496 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-08 05:00:41,520 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-08 05:00:41,521 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2025-03-08 05:00:41,521 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2025-03-08 05:00:41,521 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-03-08 05:00:41,521 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-08 05:00:41,521 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-08 05:00:41,521 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2025-03-08 05:00:41,521 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2025-03-08 05:00:41,570 INFO L256 CfgBuilder]: Building ICFG [2025-03-08 05:00:41,572 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-08 05:00:41,729 INFO L? ?]: Removed 11 outVars from TransFormulas that were not future-live. [2025-03-08 05:00:41,729 INFO L307 CfgBuilder]: Performing block encoding [2025-03-08 05:00:41,739 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-08 05:00:41,739 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-08 05:00:41,743 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 08.03 05:00:41 BoogieIcfgContainer [2025-03-08 05:00:41,743 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-08 05:00:41,745 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-03-08 05:00:41,745 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-03-08 05:00:41,748 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-03-08 05:00:41,749 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 08.03 05:00:41" (1/3) ... [2025-03-08 05:00:41,750 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@bc4589d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.03 05:00:41, skipping insertion in model container [2025-03-08 05:00:41,750 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:00:41" (2/3) ... [2025-03-08 05:00:41,750 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@bc4589d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.03 05:00:41, skipping insertion in model container [2025-03-08 05:00:41,750 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 08.03 05:00:41" (3/3) ... [2025-03-08 05:00:41,751 INFO L128 eAbstractionObserver]: Analyzing ICFG egcd2-ll_unwindbound5.c [2025-03-08 05:00:41,763 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-03-08 05:00:41,765 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG egcd2-ll_unwindbound5.c that has 3 procedures, 34 locations, 1 initial locations, 2 loop locations, and 1 error locations. [2025-03-08 05:00:41,811 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-03-08 05:00:41,821 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;@6f77d78, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-03-08 05:00:41,822 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-03-08 05:00:41,826 INFO L276 IsEmpty]: Start isEmpty. Operand has 34 states, 20 states have (on average 1.45) internal successors, (29), 22 states have internal predecessors, (29), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2025-03-08 05:00:41,830 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2025-03-08 05:00:41,831 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:41,831 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-08 05:00:41,831 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:41,835 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:41,836 INFO L85 PathProgramCache]: Analyzing trace with hash 100709880, now seen corresponding path program 1 times [2025-03-08 05:00:41,841 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:41,842 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [32361275] [2025-03-08 05:00:41,842 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:41,843 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:41,898 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 28 statements into 1 equivalence classes. [2025-03-08 05:00:41,907 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 28 of 28 statements. [2025-03-08 05:00:41,907 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:41,907 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:41,953 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2025-03-08 05:00:41,953 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:00:41,953 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [32361275] [2025-03-08 05:00:41,954 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [32361275] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:00:41,954 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1056605056] [2025-03-08 05:00:41,954 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:41,954 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:41,954 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:00:41,957 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-08 05:00:41,959 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2025-03-08 05:00:41,989 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 28 statements into 1 equivalence classes. [2025-03-08 05:00:42,015 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 28 of 28 statements. [2025-03-08 05:00:42,016 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:42,016 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:42,019 INFO L256 TraceCheckSpWp]: Trace formula consists of 93 conjuncts, 1 conjuncts are in the unsatisfiable core [2025-03-08 05:00:42,022 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:00:42,032 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2025-03-08 05:00:42,032 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-08 05:00:42,032 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1056605056] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:00:42,032 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-08 05:00:42,033 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [2] total 2 [2025-03-08 05:00:42,034 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [631335596] [2025-03-08 05:00:42,034 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:00:42,037 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2025-03-08 05:00:42,037 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:00:42,048 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2025-03-08 05:00:42,049 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-03-08 05:00:42,050 INFO L87 Difference]: Start difference. First operand has 34 states, 20 states have (on average 1.45) internal successors, (29), 22 states have internal predecessors, (29), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2025-03-08 05:00:42,061 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:00:42,061 INFO L93 Difference]: Finished difference Result 65 states and 104 transitions. [2025-03-08 05:00:42,062 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2025-03-08 05:00:42,063 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) Word has length 28 [2025-03-08 05:00:42,063 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:00:42,066 INFO L225 Difference]: With dead ends: 65 [2025-03-08 05:00:42,067 INFO L226 Difference]: Without dead ends: 30 [2025-03-08 05:00:42,069 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 29 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-03-08 05:00:42,070 INFO L435 NwaCegarLoop]: 45 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 45 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-08 05:00:42,071 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 45 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-08 05:00:42,081 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 30 states. [2025-03-08 05:00:42,090 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 30 to 30. [2025-03-08 05:00:42,091 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 17 states have (on average 1.2941176470588236) internal successors, (22), 19 states have internal predecessors, (22), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2025-03-08 05:00:42,094 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 41 transitions. [2025-03-08 05:00:42,096 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 41 transitions. Word has length 28 [2025-03-08 05:00:42,096 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:00:42,096 INFO L471 AbstractCegarLoop]: Abstraction has 30 states and 41 transitions. [2025-03-08 05:00:42,096 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2025-03-08 05:00:42,096 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 41 transitions. [2025-03-08 05:00:42,097 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2025-03-08 05:00:42,097 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:42,097 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-08 05:00:42,103 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-08 05:00:42,298 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable0 [2025-03-08 05:00:42,298 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:42,299 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:42,299 INFO L85 PathProgramCache]: Analyzing trace with hash -1726789354, now seen corresponding path program 1 times [2025-03-08 05:00:42,299 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:42,299 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2088792394] [2025-03-08 05:00:42,299 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:42,299 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:42,305 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 29 statements into 1 equivalence classes. [2025-03-08 05:00:42,315 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 29 of 29 statements. [2025-03-08 05:00:42,315 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:42,316 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:42,421 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-08 05:00:42,421 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:00:42,421 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2088792394] [2025-03-08 05:00:42,421 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2088792394] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:00:42,421 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-08 05:00:42,421 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2025-03-08 05:00:42,421 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1296751469] [2025-03-08 05:00:42,422 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:00:42,422 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2025-03-08 05:00:42,422 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:00:42,422 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2025-03-08 05:00:42,423 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2025-03-08 05:00:42,423 INFO L87 Difference]: Start difference. First operand 30 states and 41 transitions. Second operand has 4 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2025-03-08 05:00:42,443 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:00:42,444 INFO L93 Difference]: Finished difference Result 40 states and 52 transitions. [2025-03-08 05:00:42,444 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2025-03-08 05:00:42,445 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 29 [2025-03-08 05:00:42,445 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:00:42,445 INFO L225 Difference]: With dead ends: 40 [2025-03-08 05:00:42,445 INFO L226 Difference]: Without dead ends: 32 [2025-03-08 05:00:42,446 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-08 05:00:42,447 INFO L435 NwaCegarLoop]: 39 mSDtfsCounter, 7 mSDsluCounter, 61 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 100 SdHoareTripleChecker+Invalid, 9 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-08 05:00:42,447 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 100 Invalid, 9 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-08 05:00:42,447 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2025-03-08 05:00:42,451 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2025-03-08 05:00:42,451 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 19 states have (on average 1.263157894736842) internal successors, (24), 20 states have internal predecessors, (24), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2025-03-08 05:00:42,454 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 43 transitions. [2025-03-08 05:00:42,455 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 43 transitions. Word has length 29 [2025-03-08 05:00:42,455 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:00:42,456 INFO L471 AbstractCegarLoop]: Abstraction has 32 states and 43 transitions. [2025-03-08 05:00:42,456 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2025-03-08 05:00:42,456 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 43 transitions. [2025-03-08 05:00:42,456 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2025-03-08 05:00:42,456 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:42,456 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:00:42,457 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2025-03-08 05:00:42,457 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:42,457 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:42,457 INFO L85 PathProgramCache]: Analyzing trace with hash -2044305484, now seen corresponding path program 1 times [2025-03-08 05:00:42,457 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:42,457 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [150462108] [2025-03-08 05:00:42,458 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:42,458 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:42,465 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 30 statements into 1 equivalence classes. [2025-03-08 05:00:42,484 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 30 of 30 statements. [2025-03-08 05:00:42,484 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:42,484 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:42,626 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-08 05:00:42,627 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:00:42,627 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [150462108] [2025-03-08 05:00:42,627 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [150462108] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:00:42,627 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [945251070] [2025-03-08 05:00:42,627 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:42,627 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:42,627 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:00:42,629 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-08 05:00:42,630 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-08 05:00:42,659 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 30 statements into 1 equivalence classes. [2025-03-08 05:00:42,671 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 30 of 30 statements. [2025-03-08 05:00:42,671 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:42,671 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:42,672 INFO L256 TraceCheckSpWp]: Trace formula consists of 99 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-03-08 05:00:42,674 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:00:42,820 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-08 05:00:42,822 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-08 05:00:42,822 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [945251070] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:00:42,822 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-08 05:00:42,822 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 10 [2025-03-08 05:00:42,822 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1508594076] [2025-03-08 05:00:42,823 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:00:42,823 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2025-03-08 05:00:42,823 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:00:42,823 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-03-08 05:00:42,823 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=72, Unknown=0, NotChecked=0, Total=90 [2025-03-08 05:00:42,824 INFO L87 Difference]: Start difference. First operand 32 states and 43 transitions. Second operand has 6 states, 5 states have (on average 2.4) internal successors, (12), 5 states have internal predecessors, (12), 3 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2025-03-08 05:00:42,914 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:00:42,914 INFO L93 Difference]: Finished difference Result 49 states and 67 transitions. [2025-03-08 05:00:42,914 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-08 05:00:42,914 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 2.4) internal successors, (12), 5 states have internal predecessors, (12), 3 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 30 [2025-03-08 05:00:42,914 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:00:42,915 INFO L225 Difference]: With dead ends: 49 [2025-03-08 05:00:42,915 INFO L226 Difference]: Without dead ends: 47 [2025-03-08 05:00:42,915 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 36 GetRequests, 27 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=22, Invalid=88, Unknown=0, NotChecked=0, Total=110 [2025-03-08 05:00:42,916 INFO L435 NwaCegarLoop]: 32 mSDtfsCounter, 9 mSDsluCounter, 114 mSDsCounter, 0 mSdLazyCounter, 56 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 146 SdHoareTripleChecker+Invalid, 57 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 56 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 05:00:42,916 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 146 Invalid, 57 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 56 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 05:00:42,919 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2025-03-08 05:00:42,924 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 45. [2025-03-08 05:00:42,927 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 26 states have (on average 1.3076923076923077) internal successors, (34), 28 states have internal predecessors, (34), 15 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (14), 13 states have call predecessors, (14), 14 states have call successors, (14) [2025-03-08 05:00:42,927 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 63 transitions. [2025-03-08 05:00:42,930 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 63 transitions. Word has length 30 [2025-03-08 05:00:42,930 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:00:42,930 INFO L471 AbstractCegarLoop]: Abstraction has 45 states and 63 transitions. [2025-03-08 05:00:42,930 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 2.4) internal successors, (12), 5 states have internal predecessors, (12), 3 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2025-03-08 05:00:42,930 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 63 transitions. [2025-03-08 05:00:42,930 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2025-03-08 05:00:42,930 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:42,931 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:00:42,936 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-08 05:00:43,132 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2025-03-08 05:00:43,132 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:43,133 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:43,133 INFO L85 PathProgramCache]: Analyzing trace with hash -886820372, now seen corresponding path program 1 times [2025-03-08 05:00:43,133 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:43,133 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1197741842] [2025-03-08 05:00:43,133 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:43,133 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:43,140 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 32 statements into 1 equivalence classes. [2025-03-08 05:00:43,154 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 32 of 32 statements. [2025-03-08 05:00:43,155 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:43,155 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:00:43,160 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [443773579] [2025-03-08 05:00:43,162 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:43,162 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:43,162 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:00:43,164 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-08 05:00:43,165 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-08 05:00:43,195 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 32 statements into 1 equivalence classes. [2025-03-08 05:00:43,207 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 32 of 32 statements. [2025-03-08 05:00:43,207 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:43,207 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:43,208 INFO L256 TraceCheckSpWp]: Trace formula consists of 107 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-08 05:00:43,209 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:00:43,246 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-08 05:00:43,246 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-08 05:00:43,246 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:00:43,246 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1197741842] [2025-03-08 05:00:43,247 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:00:43,247 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [443773579] [2025-03-08 05:00:43,247 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [443773579] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:00:43,247 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-08 05:00:43,247 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-08 05:00:43,247 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1335535724] [2025-03-08 05:00:43,247 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:00:43,247 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-08 05:00:43,247 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:00:43,247 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-08 05:00:43,247 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-08 05:00:43,248 INFO L87 Difference]: Start difference. First operand 45 states and 63 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2025-03-08 05:00:43,292 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:00:43,292 INFO L93 Difference]: Finished difference Result 66 states and 95 transitions. [2025-03-08 05:00:43,292 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-08 05:00:43,293 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 32 [2025-03-08 05:00:43,293 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:00:43,296 INFO L225 Difference]: With dead ends: 66 [2025-03-08 05:00:43,296 INFO L226 Difference]: Without dead ends: 64 [2025-03-08 05:00:43,296 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 32 GetRequests, 28 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2025-03-08 05:00:43,297 INFO L435 NwaCegarLoop]: 38 mSDtfsCounter, 5 mSDsluCounter, 101 mSDsCounter, 0 mSdLazyCounter, 32 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 139 SdHoareTripleChecker+Invalid, 32 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 32 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-08 05:00:43,297 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 139 Invalid, 32 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-08 05:00:43,297 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2025-03-08 05:00:43,304 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 55. [2025-03-08 05:00:43,304 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 55 states, 33 states have (on average 1.303030303030303) internal successors, (43), 37 states have internal predecessors, (43), 17 states have call successors, (17), 4 states have call predecessors, (17), 4 states have return successors, (16), 13 states have call predecessors, (16), 16 states have call successors, (16) [2025-03-08 05:00:43,305 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 76 transitions. [2025-03-08 05:00:43,305 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 76 transitions. Word has length 32 [2025-03-08 05:00:43,305 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:00:43,305 INFO L471 AbstractCegarLoop]: Abstraction has 55 states and 76 transitions. [2025-03-08 05:00:43,306 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2025-03-08 05:00:43,306 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 76 transitions. [2025-03-08 05:00:43,306 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2025-03-08 05:00:43,306 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:43,306 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:00:43,313 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2025-03-08 05:00:43,507 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:43,507 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:43,508 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:43,508 INFO L85 PathProgramCache]: Analyzing trace with hash -276176331, now seen corresponding path program 1 times [2025-03-08 05:00:43,508 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:43,508 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1358041320] [2025-03-08 05:00:43,508 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:43,509 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:43,515 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 35 statements into 1 equivalence classes. [2025-03-08 05:00:43,525 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 35 of 35 statements. [2025-03-08 05:00:43,525 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:43,525 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:43,614 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-08 05:00:43,614 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:00:43,615 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1358041320] [2025-03-08 05:00:43,617 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1358041320] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:00:43,617 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [528910435] [2025-03-08 05:00:43,617 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:43,617 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:43,617 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:00:43,619 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-08 05:00:43,621 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-08 05:00:43,641 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 35 statements into 1 equivalence classes. [2025-03-08 05:00:43,651 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 35 of 35 statements. [2025-03-08 05:00:43,651 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:43,651 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:43,652 INFO L256 TraceCheckSpWp]: Trace formula consists of 108 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-03-08 05:00:43,653 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:00:43,741 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-08 05:00:43,741 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-08 05:00:43,741 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [528910435] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:00:43,741 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-08 05:00:43,741 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 9 [2025-03-08 05:00:43,742 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1426633797] [2025-03-08 05:00:43,742 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:00:43,742 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-08 05:00:43,742 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:00:43,742 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-08 05:00:43,742 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=56, Unknown=0, NotChecked=0, Total=72 [2025-03-08 05:00:43,742 INFO L87 Difference]: Start difference. First operand 55 states and 76 transitions. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2025-03-08 05:00:43,788 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:00:43,788 INFO L93 Difference]: Finished difference Result 63 states and 83 transitions. [2025-03-08 05:00:43,789 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-08 05:00:43,789 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 35 [2025-03-08 05:00:43,789 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:00:43,789 INFO L225 Difference]: With dead ends: 63 [2025-03-08 05:00:43,789 INFO L226 Difference]: Without dead ends: 59 [2025-03-08 05:00:43,790 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 41 GetRequests, 33 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=20, Invalid=70, Unknown=0, NotChecked=0, Total=90 [2025-03-08 05:00:43,790 INFO L435 NwaCegarLoop]: 39 mSDtfsCounter, 9 mSDsluCounter, 103 mSDsCounter, 0 mSdLazyCounter, 27 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 142 SdHoareTripleChecker+Invalid, 28 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 27 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-08 05:00:43,790 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 142 Invalid, 28 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 27 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-08 05:00:43,791 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 59 states. [2025-03-08 05:00:43,801 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 59 to 58. [2025-03-08 05:00:43,802 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 58 states, 36 states have (on average 1.25) internal successors, (45), 39 states have internal predecessors, (45), 16 states have call successors, (16), 5 states have call predecessors, (16), 5 states have return successors, (15), 13 states have call predecessors, (15), 15 states have call successors, (15) [2025-03-08 05:00:43,802 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 76 transitions. [2025-03-08 05:00:43,804 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 76 transitions. Word has length 35 [2025-03-08 05:00:43,804 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:00:43,804 INFO L471 AbstractCegarLoop]: Abstraction has 58 states and 76 transitions. [2025-03-08 05:00:43,804 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2025-03-08 05:00:43,804 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 76 transitions. [2025-03-08 05:00:43,805 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2025-03-08 05:00:43,805 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:43,805 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:00:43,811 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2025-03-08 05:00:44,005 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:44,006 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:44,006 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:44,006 INFO L85 PathProgramCache]: Analyzing trace with hash -247836027, now seen corresponding path program 1 times [2025-03-08 05:00:44,006 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:44,006 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [561246741] [2025-03-08 05:00:44,006 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:44,006 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:44,011 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 35 statements into 1 equivalence classes. [2025-03-08 05:00:44,018 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 35 of 35 statements. [2025-03-08 05:00:44,019 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:44,019 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:44,065 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-08 05:00:44,066 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:00:44,066 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [561246741] [2025-03-08 05:00:44,066 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [561246741] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:00:44,066 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-08 05:00:44,066 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-08 05:00:44,066 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1535232386] [2025-03-08 05:00:44,066 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:00:44,066 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-08 05:00:44,066 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:00:44,067 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-08 05:00:44,067 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2025-03-08 05:00:44,067 INFO L87 Difference]: Start difference. First operand 58 states and 76 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2025-03-08 05:00:44,089 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:00:44,090 INFO L93 Difference]: Finished difference Result 84 states and 111 transitions. [2025-03-08 05:00:44,090 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-08 05:00:44,090 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 35 [2025-03-08 05:00:44,090 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:00:44,091 INFO L225 Difference]: With dead ends: 84 [2025-03-08 05:00:44,091 INFO L226 Difference]: Without dead ends: 58 [2025-03-08 05:00:44,091 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-08 05:00:44,092 INFO L435 NwaCegarLoop]: 38 mSDtfsCounter, 10 mSDsluCounter, 62 mSDsCounter, 0 mSdLazyCounter, 12 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 100 SdHoareTripleChecker+Invalid, 16 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 12 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-08 05:00:44,092 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 100 Invalid, 16 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 12 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-08 05:00:44,092 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states. [2025-03-08 05:00:44,097 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 58. [2025-03-08 05:00:44,097 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 58 states, 36 states have (on average 1.2222222222222223) internal successors, (44), 39 states have internal predecessors, (44), 16 states have call successors, (16), 5 states have call predecessors, (16), 5 states have return successors, (15), 13 states have call predecessors, (15), 15 states have call successors, (15) [2025-03-08 05:00:44,098 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 75 transitions. [2025-03-08 05:00:44,098 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 75 transitions. Word has length 35 [2025-03-08 05:00:44,098 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:00:44,098 INFO L471 AbstractCegarLoop]: Abstraction has 58 states and 75 transitions. [2025-03-08 05:00:44,098 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2025-03-08 05:00:44,098 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 75 transitions. [2025-03-08 05:00:44,099 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2025-03-08 05:00:44,099 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:44,099 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:00:44,099 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5 [2025-03-08 05:00:44,099 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:44,100 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:44,100 INFO L85 PathProgramCache]: Analyzing trace with hash -1535941731, now seen corresponding path program 1 times [2025-03-08 05:00:44,100 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:44,100 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1261947727] [2025-03-08 05:00:44,100 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:44,100 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:44,104 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 47 statements into 1 equivalence classes. [2025-03-08 05:00:44,112 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 47 of 47 statements. [2025-03-08 05:00:44,112 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:44,112 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:00:44,115 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [538024177] [2025-03-08 05:00:44,115 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:44,115 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:44,115 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:00:44,117 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-08 05:00:44,119 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-08 05:00:44,146 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 47 statements into 1 equivalence classes. [2025-03-08 05:00:44,161 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 47 of 47 statements. [2025-03-08 05:00:44,161 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:44,161 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:44,162 INFO L256 TraceCheckSpWp]: Trace formula consists of 134 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-03-08 05:00:44,164 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:00:44,303 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-08 05:00:44,303 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-08 05:00:44,303 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:00:44,303 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1261947727] [2025-03-08 05:00:44,303 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:00:44,303 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [538024177] [2025-03-08 05:00:44,303 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [538024177] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:00:44,303 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-08 05:00:44,303 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-08 05:00:44,303 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1251643076] [2025-03-08 05:00:44,303 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:00:44,304 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-08 05:00:44,304 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:00:44,304 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-08 05:00:44,304 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-08 05:00:44,304 INFO L87 Difference]: Start difference. First operand 58 states and 75 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2025-03-08 05:00:44,355 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:00:44,355 INFO L93 Difference]: Finished difference Result 65 states and 81 transitions. [2025-03-08 05:00:44,356 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-08 05:00:44,356 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 47 [2025-03-08 05:00:44,356 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:00:44,357 INFO L225 Difference]: With dead ends: 65 [2025-03-08 05:00:44,357 INFO L226 Difference]: Without dead ends: 63 [2025-03-08 05:00:44,357 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 47 GetRequests, 43 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2025-03-08 05:00:44,358 INFO L435 NwaCegarLoop]: 36 mSDtfsCounter, 6 mSDsluCounter, 94 mSDsCounter, 0 mSdLazyCounter, 39 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 130 SdHoareTripleChecker+Invalid, 40 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 39 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-08 05:00:44,358 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 130 Invalid, 40 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-08 05:00:44,358 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2025-03-08 05:00:44,374 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 62. [2025-03-08 05:00:44,375 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 62 states, 39 states have (on average 1.205128205128205) internal successors, (47), 42 states have internal predecessors, (47), 16 states have call successors, (16), 6 states have call predecessors, (16), 6 states have return successors, (15), 13 states have call predecessors, (15), 15 states have call successors, (15) [2025-03-08 05:00:44,376 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 78 transitions. [2025-03-08 05:00:44,376 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 78 transitions. Word has length 47 [2025-03-08 05:00:44,377 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:00:44,377 INFO L471 AbstractCegarLoop]: Abstraction has 62 states and 78 transitions. [2025-03-08 05:00:44,377 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2025-03-08 05:00:44,378 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 78 transitions. [2025-03-08 05:00:44,378 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2025-03-08 05:00:44,378 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:44,378 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:00:44,388 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-08 05:00:44,579 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:44,579 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:44,580 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:44,580 INFO L85 PathProgramCache]: Analyzing trace with hash 101798249, now seen corresponding path program 1 times [2025-03-08 05:00:44,580 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:44,580 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1525841843] [2025-03-08 05:00:44,580 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:44,580 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:44,584 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 55 statements into 1 equivalence classes. [2025-03-08 05:00:44,592 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 55 of 55 statements. [2025-03-08 05:00:44,592 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:44,592 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:00:44,593 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [72536615] [2025-03-08 05:00:44,593 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:44,593 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:44,593 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:00:44,595 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-08 05:00:44,597 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-08 05:00:44,623 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 55 statements into 1 equivalence classes. [2025-03-08 05:00:44,648 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 55 of 55 statements. [2025-03-08 05:00:44,649 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:44,649 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:44,651 INFO L256 TraceCheckSpWp]: Trace formula consists of 153 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-03-08 05:00:44,654 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:00:44,731 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-08 05:00:44,731 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:00:44,847 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-08 05:00:44,848 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:00:44,848 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1525841843] [2025-03-08 05:00:44,848 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:00:44,848 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [72536615] [2025-03-08 05:00:44,848 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [72536615] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 05:00:44,848 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-08 05:00:44,848 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 7 [2025-03-08 05:00:44,848 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1946324486] [2025-03-08 05:00:44,848 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-08 05:00:44,848 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2025-03-08 05:00:44,848 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:00:44,849 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2025-03-08 05:00:44,849 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2025-03-08 05:00:44,849 INFO L87 Difference]: Start difference. First operand 62 states and 78 transitions. Second operand has 7 states, 7 states have (on average 3.2857142857142856) internal successors, (23), 6 states have internal predecessors, (23), 4 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2025-03-08 05:00:44,933 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:00:44,933 INFO L93 Difference]: Finished difference Result 92 states and 127 transitions. [2025-03-08 05:00:44,934 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2025-03-08 05:00:44,934 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 3.2857142857142856) internal successors, (23), 6 states have internal predecessors, (23), 4 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) Word has length 55 [2025-03-08 05:00:44,934 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:00:44,935 INFO L225 Difference]: With dead ends: 92 [2025-03-08 05:00:44,935 INFO L226 Difference]: Without dead ends: 90 [2025-03-08 05:00:44,935 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 109 GetRequests, 100 SyntacticMatches, 3 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2025-03-08 05:00:44,935 INFO L435 NwaCegarLoop]: 45 mSDtfsCounter, 9 mSDsluCounter, 174 mSDsCounter, 0 mSdLazyCounter, 72 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 219 SdHoareTripleChecker+Invalid, 74 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 72 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 05:00:44,935 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 219 Invalid, 74 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 72 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 05:00:44,936 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 90 states. [2025-03-08 05:00:44,946 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 90 to 58. [2025-03-08 05:00:44,947 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 58 states, 37 states have (on average 1.1891891891891893) internal successors, (44), 38 states have internal predecessors, (44), 14 states have call successors, (14), 6 states have call predecessors, (14), 6 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2025-03-08 05:00:44,947 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 71 transitions. [2025-03-08 05:00:44,947 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 71 transitions. Word has length 55 [2025-03-08 05:00:44,948 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:00:44,948 INFO L471 AbstractCegarLoop]: Abstraction has 58 states and 71 transitions. [2025-03-08 05:00:44,948 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 3.2857142857142856) internal successors, (23), 6 states have internal predecessors, (23), 4 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2025-03-08 05:00:44,948 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 71 transitions. [2025-03-08 05:00:44,948 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2025-03-08 05:00:44,949 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:44,950 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:00:44,956 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-08 05:00:45,151 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:45,151 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:45,151 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:45,151 INFO L85 PathProgramCache]: Analyzing trace with hash -1244697335, now seen corresponding path program 1 times [2025-03-08 05:00:45,151 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:45,151 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1246126885] [2025-03-08 05:00:45,154 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:45,154 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:45,158 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 56 statements into 1 equivalence classes. [2025-03-08 05:00:45,164 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 56 of 56 statements. [2025-03-08 05:00:45,166 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:45,167 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:45,234 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-08 05:00:45,234 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:00:45,234 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1246126885] [2025-03-08 05:00:45,234 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1246126885] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:00:45,234 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [149219740] [2025-03-08 05:00:45,234 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:45,234 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:45,234 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:00:45,236 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-08 05:00:45,238 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-08 05:00:45,260 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 56 statements into 1 equivalence classes. [2025-03-08 05:00:45,274 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 56 of 56 statements. [2025-03-08 05:00:45,275 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:45,275 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:45,276 INFO L256 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-08 05:00:45,277 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:00:45,334 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-08 05:00:45,334 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:00:45,427 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-08 05:00:45,427 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [149219740] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 05:00:45,427 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-08 05:00:45,427 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 5, 6] total 9 [2025-03-08 05:00:45,427 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [814768769] [2025-03-08 05:00:45,427 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-08 05:00:45,428 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2025-03-08 05:00:45,428 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:00:45,428 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2025-03-08 05:00:45,428 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=46, Unknown=0, NotChecked=0, Total=72 [2025-03-08 05:00:45,428 INFO L87 Difference]: Start difference. First operand 58 states and 71 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-08 05:00:45,544 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:00:45,544 INFO L93 Difference]: Finished difference Result 169 states and 198 transitions. [2025-03-08 05:00:45,544 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2025-03-08 05:00:45,545 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 56 [2025-03-08 05:00:45,545 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:00:45,546 INFO L225 Difference]: With dead ends: 169 [2025-03-08 05:00:45,546 INFO L226 Difference]: Without dead ends: 161 [2025-03-08 05:00:45,546 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 119 GetRequests, 108 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-08 05:00:45,546 INFO L435 NwaCegarLoop]: 38 mSDtfsCounter, 49 mSDsluCounter, 144 mSDsCounter, 0 mSdLazyCounter, 72 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 49 SdHoareTripleChecker+Valid, 182 SdHoareTripleChecker+Invalid, 81 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 72 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 05:00:45,547 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [49 Valid, 182 Invalid, 81 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 72 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 05:00:45,547 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 161 states. [2025-03-08 05:00:45,565 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 161 to 155. [2025-03-08 05:00:45,565 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 155 states, 100 states have (on average 1.18) internal successors, (118), 103 states have internal predecessors, (118), 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-08 05:00:45,567 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 155 states to 155 states and 183 transitions. [2025-03-08 05:00:45,568 INFO L78 Accepts]: Start accepts. Automaton has 155 states and 183 transitions. Word has length 56 [2025-03-08 05:00:45,569 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:00:45,569 INFO L471 AbstractCegarLoop]: Abstraction has 155 states and 183 transitions. [2025-03-08 05:00:45,569 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-08 05:00:45,569 INFO L276 IsEmpty]: Start isEmpty. Operand 155 states and 183 transitions. [2025-03-08 05:00:45,569 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 58 [2025-03-08 05:00:45,570 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:45,570 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:00:45,577 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2025-03-08 05:00:45,771 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:45,771 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:45,772 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:45,772 INFO L85 PathProgramCache]: Analyzing trace with hash 15645217, now seen corresponding path program 1 times [2025-03-08 05:00:45,772 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:45,772 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1804356190] [2025-03-08 05:00:45,772 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:45,772 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:45,776 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 57 statements into 1 equivalence classes. [2025-03-08 05:00:45,782 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 57 of 57 statements. [2025-03-08 05:00:45,782 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:45,782 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:45,853 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-08 05:00:45,853 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:00:45,853 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1804356190] [2025-03-08 05:00:45,854 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1804356190] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:00:45,854 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [269811722] [2025-03-08 05:00:45,854 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:45,854 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:45,854 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:00:45,858 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-08 05:00:45,860 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-08 05:00:45,883 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 57 statements into 1 equivalence classes. [2025-03-08 05:00:45,899 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 57 of 57 statements. [2025-03-08 05:00:45,899 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:45,899 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:45,900 INFO L256 TraceCheckSpWp]: Trace formula consists of 163 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-03-08 05:00:45,901 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:00:45,932 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-08 05:00:45,933 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:00:46,007 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-08 05:00:46,008 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [269811722] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 05:00:46,008 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-08 05:00:46,008 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 9 [2025-03-08 05:00:46,008 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2010463547] [2025-03-08 05:00:46,008 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-08 05:00:46,008 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2025-03-08 05:00:46,008 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:00:46,009 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2025-03-08 05:00:46,009 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2025-03-08 05:00:46,009 INFO L87 Difference]: Start difference. First operand 155 states and 183 transitions. Second operand has 9 states, 9 states have (on average 3.0) internal successors, (27), 8 states have internal predecessors, (27), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2025-03-08 05:00:46,174 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:00:46,174 INFO L93 Difference]: Finished difference Result 221 states and 288 transitions. [2025-03-08 05:00:46,174 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-03-08 05:00:46,174 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 3.0) internal successors, (27), 8 states have internal predecessors, (27), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) Word has length 57 [2025-03-08 05:00:46,175 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:00:46,176 INFO L225 Difference]: With dead ends: 221 [2025-03-08 05:00:46,177 INFO L226 Difference]: Without dead ends: 207 [2025-03-08 05:00:46,177 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 125 GetRequests, 109 SyntacticMatches, 4 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=48, Invalid=134, Unknown=0, NotChecked=0, Total=182 [2025-03-08 05:00:46,177 INFO L435 NwaCegarLoop]: 49 mSDtfsCounter, 57 mSDsluCounter, 249 mSDsCounter, 0 mSdLazyCounter, 88 mSolverCounterSat, 35 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 62 SdHoareTripleChecker+Valid, 298 SdHoareTripleChecker+Invalid, 123 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 35 IncrementalHoareTripleChecker+Valid, 88 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 05:00:46,177 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [62 Valid, 298 Invalid, 123 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [35 Valid, 88 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 05:00:46,178 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 207 states. [2025-03-08 05:00:46,205 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 207 to 185. [2025-03-08 05:00:46,206 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 185 states, 121 states have (on average 1.2148760330578512) internal successors, (147), 123 states have internal predecessors, (147), 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-08 05:00:46,207 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 185 states to 185 states and 233 transitions. [2025-03-08 05:00:46,208 INFO L78 Accepts]: Start accepts. Automaton has 185 states and 233 transitions. Word has length 57 [2025-03-08 05:00:46,208 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:00:46,208 INFO L471 AbstractCegarLoop]: Abstraction has 185 states and 233 transitions. [2025-03-08 05:00:46,208 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 3.0) internal successors, (27), 8 states have internal predecessors, (27), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2025-03-08 05:00:46,208 INFO L276 IsEmpty]: Start isEmpty. Operand 185 states and 233 transitions. [2025-03-08 05:00:46,209 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2025-03-08 05:00:46,209 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:46,209 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:00:46,215 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-08 05:00:46,413 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2025-03-08 05:00:46,413 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:46,416 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:46,416 INFO L85 PathProgramCache]: Analyzing trace with hash -351822558, now seen corresponding path program 1 times [2025-03-08 05:00:46,416 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:46,416 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1298482899] [2025-03-08 05:00:46,416 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:46,416 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:46,423 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 59 statements into 1 equivalence classes. [2025-03-08 05:00:46,434 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 59 of 59 statements. [2025-03-08 05:00:46,434 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:46,434 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:46,501 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-08 05:00:46,501 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:00:46,501 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1298482899] [2025-03-08 05:00:46,501 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1298482899] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:00:46,501 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [984309723] [2025-03-08 05:00:46,501 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:46,502 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:46,502 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:00:46,504 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-08 05:00:46,505 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-08 05:00:46,534 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 59 statements into 1 equivalence classes. [2025-03-08 05:00:46,552 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 59 of 59 statements. [2025-03-08 05:00:46,552 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:46,552 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:46,553 INFO L256 TraceCheckSpWp]: Trace formula consists of 172 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-08 05:00:46,556 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:00:46,620 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-08 05:00:46,620 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:00:46,698 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-08 05:00:46,698 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [984309723] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 05:00:46,698 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-08 05:00:46,698 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 5, 6] total 9 [2025-03-08 05:00:46,699 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [917328576] [2025-03-08 05:00:46,699 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-08 05:00:46,699 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2025-03-08 05:00:46,699 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:00:46,700 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2025-03-08 05:00:46,701 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=46, Unknown=0, NotChecked=0, Total=72 [2025-03-08 05:00:46,701 INFO L87 Difference]: Start difference. First operand 185 states and 233 transitions. Second operand has 9 states, 9 states have (on average 4.555555555555555) internal successors, (41), 9 states have internal predecessors, (41), 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-08 05:00:46,834 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:00:46,834 INFO L93 Difference]: Finished difference Result 265 states and 346 transitions. [2025-03-08 05:00:46,834 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2025-03-08 05:00:46,835 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 4.555555555555555) internal successors, (41), 9 states have internal predecessors, (41), 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 59 [2025-03-08 05:00:46,836 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:00:46,837 INFO L225 Difference]: With dead ends: 265 [2025-03-08 05:00:46,838 INFO L226 Difference]: Without dead ends: 193 [2025-03-08 05:00:46,839 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 125 GetRequests, 114 SyntacticMatches, 1 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=46, Invalid=86, Unknown=0, NotChecked=0, Total=132 [2025-03-08 05:00:46,839 INFO L435 NwaCegarLoop]: 38 mSDtfsCounter, 43 mSDsluCounter, 134 mSDsCounter, 0 mSdLazyCounter, 66 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 43 SdHoareTripleChecker+Valid, 172 SdHoareTripleChecker+Invalid, 72 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 66 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 05:00:46,839 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [43 Valid, 172 Invalid, 72 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 66 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 05:00:46,841 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 193 states. [2025-03-08 05:00:46,869 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 193 to 191. [2025-03-08 05:00:46,869 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 191 states, 127 states have (on average 1.1811023622047243) internal successors, (150), 129 states have internal predecessors, (150), 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-08 05:00:46,870 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 191 states to 191 states and 236 transitions. [2025-03-08 05:00:46,870 INFO L78 Accepts]: Start accepts. Automaton has 191 states and 236 transitions. Word has length 59 [2025-03-08 05:00:46,871 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:00:46,871 INFO L471 AbstractCegarLoop]: Abstraction has 191 states and 236 transitions. [2025-03-08 05:00:46,871 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 4.555555555555555) internal successors, (41), 9 states have internal predecessors, (41), 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-08 05:00:46,871 INFO L276 IsEmpty]: Start isEmpty. Operand 191 states and 236 transitions. [2025-03-08 05:00:46,871 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2025-03-08 05:00:46,872 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:46,872 INFO L218 NwaCegarLoop]: trace histogram [6, 5, 5, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:00:46,878 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-08 05:00:47,072 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:47,072 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:47,073 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:47,073 INFO L85 PathProgramCache]: Analyzing trace with hash -1287548176, now seen corresponding path program 1 times [2025-03-08 05:00:47,073 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:47,073 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [377310570] [2025-03-08 05:00:47,073 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:47,073 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:47,078 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 64 statements into 1 equivalence classes. [2025-03-08 05:00:47,087 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 64 of 64 statements. [2025-03-08 05:00:47,087 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:47,087 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:00:47,088 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1252026818] [2025-03-08 05:00:47,088 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:47,088 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:47,088 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:00:47,090 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-08 05:00:47,092 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-08 05:00:47,118 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 64 statements into 1 equivalence classes. [2025-03-08 05:00:47,136 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 64 of 64 statements. [2025-03-08 05:00:47,137 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:47,137 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:47,138 INFO L256 TraceCheckSpWp]: Trace formula consists of 180 conjuncts, 17 conjuncts are in the unsatisfiable core [2025-03-08 05:00:47,139 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:00:47,251 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-08 05:00:47,251 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:00:47,280 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:00:47,281 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [377310570] [2025-03-08 05:00:47,281 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:00:47,281 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1252026818] [2025-03-08 05:00:47,281 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1252026818] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:00:47,281 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-08 05:00:47,281 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6] total 6 [2025-03-08 05:00:47,281 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [587649121] [2025-03-08 05:00:47,281 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-08 05:00:47,281 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2025-03-08 05:00:47,281 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:00:47,282 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-03-08 05:00:47,282 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2025-03-08 05:00:47,282 INFO L87 Difference]: Start difference. First operand 191 states and 236 transitions. Second operand has 6 states, 6 states have (on average 4.0) internal successors, (24), 5 states have internal predecessors, (24), 3 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2025-03-08 05:00:47,372 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:00:47,372 INFO L93 Difference]: Finished difference Result 223 states and 282 transitions. [2025-03-08 05:00:47,372 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-08 05:00:47,372 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 4.0) internal successors, (24), 5 states have internal predecessors, (24), 3 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) Word has length 64 [2025-03-08 05:00:47,373 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:00:47,374 INFO L225 Difference]: With dead ends: 223 [2025-03-08 05:00:47,374 INFO L226 Difference]: Without dead ends: 219 [2025-03-08 05:00:47,374 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 69 GetRequests, 61 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=16, Invalid=40, Unknown=0, NotChecked=0, Total=56 [2025-03-08 05:00:47,375 INFO L435 NwaCegarLoop]: 53 mSDtfsCounter, 10 mSDsluCounter, 160 mSDsCounter, 0 mSdLazyCounter, 67 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 213 SdHoareTripleChecker+Invalid, 69 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 67 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 05:00:47,375 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 213 Invalid, 69 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 67 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 05:00:47,375 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 219 states. [2025-03-08 05:00:47,406 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 219 to 217. [2025-03-08 05:00:47,407 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 217 states, 143 states have (on average 1.2027972027972027) internal successors, (172), 146 states have internal predecessors, (172), 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-08 05:00:47,409 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 217 states to 217 states and 273 transitions. [2025-03-08 05:00:47,409 INFO L78 Accepts]: Start accepts. Automaton has 217 states and 273 transitions. Word has length 64 [2025-03-08 05:00:47,409 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:00:47,409 INFO L471 AbstractCegarLoop]: Abstraction has 217 states and 273 transitions. [2025-03-08 05:00:47,409 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 4.0) internal successors, (24), 5 states have internal predecessors, (24), 3 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2025-03-08 05:00:47,409 INFO L276 IsEmpty]: Start isEmpty. Operand 217 states and 273 transitions. [2025-03-08 05:00:47,411 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 70 [2025-03-08 05:00:47,411 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:47,411 INFO L218 NwaCegarLoop]: trace histogram [7, 6, 6, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:00:47,417 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2025-03-08 05:00:47,611 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2025-03-08 05:00:47,611 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:47,612 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:47,612 INFO L85 PathProgramCache]: Analyzing trace with hash 691051449, now seen corresponding path program 2 times [2025-03-08 05:00:47,612 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:47,612 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2011724893] [2025-03-08 05:00:47,612 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-08 05:00:47,612 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:47,620 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 69 statements into 2 equivalence classes. [2025-03-08 05:00:47,633 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 69 of 69 statements. [2025-03-08 05:00:47,634 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-08 05:00:47,634 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:00:47,634 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1585620826] [2025-03-08 05:00:47,634 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-08 05:00:47,634 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:47,634 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:00:47,637 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-08 05:00:47,638 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-08 05:00:47,665 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 69 statements into 2 equivalence classes. [2025-03-08 05:00:47,685 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 69 of 69 statements. [2025-03-08 05:00:47,685 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-08 05:00:47,685 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:47,686 INFO L256 TraceCheckSpWp]: Trace formula consists of 189 conjuncts, 23 conjuncts are in the unsatisfiable core [2025-03-08 05:00:47,688 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:00:47,873 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-08 05:00:47,873 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:00:47,938 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:00:47,938 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2011724893] [2025-03-08 05:00:47,938 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:00:47,939 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1585620826] [2025-03-08 05:00:47,939 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1585620826] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:00:47,939 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-08 05:00:47,939 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2025-03-08 05:00:47,939 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [781604622] [2025-03-08 05:00:47,939 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-08 05:00:47,939 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2025-03-08 05:00:47,939 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:00:47,940 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2025-03-08 05:00:47,940 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2025-03-08 05:00:47,940 INFO L87 Difference]: Start difference. First operand 217 states and 273 transitions. Second operand has 7 states, 7 states have (on average 3.4285714285714284) internal successors, (24), 6 states have internal predecessors, (24), 4 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) [2025-03-08 05:00:48,043 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:00:48,044 INFO L93 Difference]: Finished difference Result 228 states and 283 transitions. [2025-03-08 05:00:48,044 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2025-03-08 05:00:48,044 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 3.4285714285714284) internal successors, (24), 6 states have internal predecessors, (24), 4 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) Word has length 69 [2025-03-08 05:00:48,045 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:00:48,046 INFO L225 Difference]: With dead ends: 228 [2025-03-08 05:00:48,046 INFO L226 Difference]: Without dead ends: 226 [2025-03-08 05:00:48,046 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 92 GetRequests, 81 SyntacticMatches, 2 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=26, Invalid=84, Unknown=0, NotChecked=0, Total=110 [2025-03-08 05:00:48,047 INFO L435 NwaCegarLoop]: 46 mSDtfsCounter, 16 mSDsluCounter, 182 mSDsCounter, 0 mSdLazyCounter, 96 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 228 SdHoareTripleChecker+Invalid, 103 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 96 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 05:00:48,047 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 228 Invalid, 103 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 96 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 05:00:48,048 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 226 states. [2025-03-08 05:00:48,065 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 226 to 225. [2025-03-08 05:00:48,066 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 225 states, 149 states have (on average 1.1946308724832215) internal successors, (178), 152 states have internal predecessors, (178), 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-08 05:00:48,067 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 225 states to 225 states and 279 transitions. [2025-03-08 05:00:48,067 INFO L78 Accepts]: Start accepts. Automaton has 225 states and 279 transitions. Word has length 69 [2025-03-08 05:00:48,067 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:00:48,068 INFO L471 AbstractCegarLoop]: Abstraction has 225 states and 279 transitions. [2025-03-08 05:00:48,068 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 3.4285714285714284) internal successors, (24), 6 states have internal predecessors, (24), 4 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) [2025-03-08 05:00:48,068 INFO L276 IsEmpty]: Start isEmpty. Operand 225 states and 279 transitions. [2025-03-08 05:00:48,069 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2025-03-08 05:00:48,069 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:48,069 INFO L218 NwaCegarLoop]: trace histogram [8, 7, 7, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:00:48,075 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2025-03-08 05:00:48,273 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2025-03-08 05:00:48,273 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:48,273 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:48,273 INFO L85 PathProgramCache]: Analyzing trace with hash 239571152, now seen corresponding path program 3 times [2025-03-08 05:00:48,273 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:48,273 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1134878722] [2025-03-08 05:00:48,273 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-08 05:00:48,273 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:48,282 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 74 statements into 5 equivalence classes. [2025-03-08 05:00:48,297 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) and asserted 74 of 74 statements. [2025-03-08 05:00:48,297 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2025-03-08 05:00:48,297 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:00:48,297 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [633550930] [2025-03-08 05:00:48,299 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-08 05:00:48,299 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:48,299 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:00:48,301 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-08 05:00:48,303 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-08 05:00:48,327 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 74 statements into 5 equivalence classes. [2025-03-08 05:00:48,344 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) and asserted 54 of 74 statements. [2025-03-08 05:00:48,345 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2025-03-08 05:00:48,345 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:48,346 INFO L256 TraceCheckSpWp]: Trace formula consists of 162 conjuncts, 42 conjuncts are in the unsatisfiable core [2025-03-08 05:00:48,347 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:00:48,666 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-08 05:00:48,666 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:00:48,876 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:00:48,877 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1134878722] [2025-03-08 05:00:48,877 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:00:48,877 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [633550930] [2025-03-08 05:00:48,877 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [633550930] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:00:48,877 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-08 05:00:48,877 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2025-03-08 05:00:48,877 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1181346384] [2025-03-08 05:00:48,877 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-08 05:00:48,877 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2025-03-08 05:00:48,877 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:00:48,877 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2025-03-08 05:00:48,877 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=41, Invalid=231, Unknown=0, NotChecked=0, Total=272 [2025-03-08 05:00:48,878 INFO L87 Difference]: Start difference. First operand 225 states and 279 transitions. Second operand has 12 states, 11 states have (on average 2.727272727272727) internal successors, (30), 11 states have internal predecessors, (30), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 5 states have call predecessors, (11), 4 states have call successors, (11) [2025-03-08 05:00:49,084 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:00:49,084 INFO L93 Difference]: Finished difference Result 236 states and 289 transitions. [2025-03-08 05:00:49,084 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2025-03-08 05:00:49,085 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 2.727272727272727) internal successors, (30), 11 states have internal predecessors, (30), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 5 states have call predecessors, (11), 4 states have call successors, (11) Word has length 74 [2025-03-08 05:00:49,085 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:00:49,086 INFO L225 Difference]: With dead ends: 236 [2025-03-08 05:00:49,086 INFO L226 Difference]: Without dead ends: 232 [2025-03-08 05:00:49,086 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 102 GetRequests, 85 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 30 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=55, Invalid=287, Unknown=0, NotChecked=0, Total=342 [2025-03-08 05:00:49,086 INFO L435 NwaCegarLoop]: 34 mSDtfsCounter, 17 mSDsluCounter, 251 mSDsCounter, 0 mSdLazyCounter, 257 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 285 SdHoareTripleChecker+Invalid, 269 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 257 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 05:00:49,087 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 285 Invalid, 269 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 257 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 05:00:49,087 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 232 states. [2025-03-08 05:00:49,102 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 232 to 231. [2025-03-08 05:00:49,102 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 231 states, 154 states have (on average 1.1818181818181819) internal successors, (182), 156 states have internal predecessors, (182), 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-08 05:00:49,103 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 231 states to 231 states and 283 transitions. [2025-03-08 05:00:49,103 INFO L78 Accepts]: Start accepts. Automaton has 231 states and 283 transitions. Word has length 74 [2025-03-08 05:00:49,103 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:00:49,103 INFO L471 AbstractCegarLoop]: Abstraction has 231 states and 283 transitions. [2025-03-08 05:00:49,104 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 2.727272727272727) internal successors, (30), 11 states have internal predecessors, (30), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 5 states have call predecessors, (11), 4 states have call successors, (11) [2025-03-08 05:00:49,104 INFO L276 IsEmpty]: Start isEmpty. Operand 231 states and 283 transitions. [2025-03-08 05:00:49,104 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 81 [2025-03-08 05:00:49,104 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:49,104 INFO L218 NwaCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:00:49,113 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-08 05:00:49,308 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2025-03-08 05:00:49,308 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:49,308 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:49,308 INFO L85 PathProgramCache]: Analyzing trace with hash 852496708, now seen corresponding path program 1 times [2025-03-08 05:00:49,308 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:49,308 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [82871958] [2025-03-08 05:00:49,308 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:49,309 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:49,312 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 80 statements into 1 equivalence classes. [2025-03-08 05:00:49,319 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 80 of 80 statements. [2025-03-08 05:00:49,319 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:49,319 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:00:49,320 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2043413628] [2025-03-08 05:00:49,320 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:49,320 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:49,320 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:00:49,322 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-08 05:00:49,323 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-08 05:00:49,347 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 80 statements into 1 equivalence classes. [2025-03-08 05:00:49,367 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 80 of 80 statements. [2025-03-08 05:00:49,367 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:49,367 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:49,368 INFO L256 TraceCheckSpWp]: Trace formula consists of 209 conjuncts, 41 conjuncts are in the unsatisfiable core [2025-03-08 05:00:49,369 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:00:49,773 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-08 05:00:49,773 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:00:50,085 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-08 05:00:50,085 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:00:50,085 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [82871958] [2025-03-08 05:00:50,085 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:00:50,085 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2043413628] [2025-03-08 05:00:50,085 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2043413628] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 05:00:50,085 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-08 05:00:50,085 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 10] total 21 [2025-03-08 05:00:50,086 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1803537428] [2025-03-08 05:00:50,086 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-08 05:00:50,086 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2025-03-08 05:00:50,086 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:00:50,087 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2025-03-08 05:00:50,087 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=64, Invalid=356, Unknown=0, NotChecked=0, Total=420 [2025-03-08 05:00:50,087 INFO L87 Difference]: Start difference. First operand 231 states and 283 transitions. Second operand has 21 states, 19 states have (on average 2.3157894736842106) internal successors, (44), 18 states have internal predecessors, (44), 10 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2025-03-08 05:00:51,786 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:00:51,787 INFO L93 Difference]: Finished difference Result 384 states and 538 transitions. [2025-03-08 05:00:51,787 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2025-03-08 05:00:51,787 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 19 states have (on average 2.3157894736842106) internal successors, (44), 18 states have internal predecessors, (44), 10 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) Word has length 80 [2025-03-08 05:00:51,788 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:00:51,790 INFO L225 Difference]: With dead ends: 384 [2025-03-08 05:00:51,790 INFO L226 Difference]: Without dead ends: 378 [2025-03-08 05:00:51,791 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 177 GetRequests, 139 SyntacticMatches, 0 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 259 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=296, Invalid=1264, Unknown=0, NotChecked=0, Total=1560 [2025-03-08 05:00:51,791 INFO L435 NwaCegarLoop]: 60 mSDtfsCounter, 123 mSDsluCounter, 511 mSDsCounter, 0 mSdLazyCounter, 477 mSolverCounterSat, 114 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 128 SdHoareTripleChecker+Valid, 571 SdHoareTripleChecker+Invalid, 591 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 114 IncrementalHoareTripleChecker+Valid, 477 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.0s IncrementalHoareTripleChecker+Time [2025-03-08 05:00:51,791 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [128 Valid, 571 Invalid, 591 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [114 Valid, 477 Invalid, 0 Unknown, 0 Unchecked, 1.0s Time] [2025-03-08 05:00:51,792 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 378 states. [2025-03-08 05:00:51,842 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 378 to 339. [2025-03-08 05:00:51,843 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 339 states, 213 states have (on average 1.2816901408450705) internal successors, (273), 216 states have internal predecessors, (273), 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-08 05:00:51,845 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 339 states to 339 states and 471 transitions. [2025-03-08 05:00:51,847 INFO L78 Accepts]: Start accepts. Automaton has 339 states and 471 transitions. Word has length 80 [2025-03-08 05:00:51,848 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:00:51,848 INFO L471 AbstractCegarLoop]: Abstraction has 339 states and 471 transitions. [2025-03-08 05:00:51,848 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 19 states have (on average 2.3157894736842106) internal successors, (44), 18 states have internal predecessors, (44), 10 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2025-03-08 05:00:51,848 INFO L276 IsEmpty]: Start isEmpty. Operand 339 states and 471 transitions. [2025-03-08 05:00:51,849 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 90 [2025-03-08 05:00:51,849 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:51,849 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, 1] [2025-03-08 05:00:51,857 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2025-03-08 05:00:52,049 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2025-03-08 05:00:52,050 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:52,050 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:52,050 INFO L85 PathProgramCache]: Analyzing trace with hash 156621477, now seen corresponding path program 1 times [2025-03-08 05:00:52,050 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:52,050 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2090113444] [2025-03-08 05:00:52,050 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:52,050 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:52,055 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 89 statements into 1 equivalence classes. [2025-03-08 05:00:52,068 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 89 of 89 statements. [2025-03-08 05:00:52,068 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:52,069 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:52,163 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-08 05:00:52,163 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:00:52,163 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2090113444] [2025-03-08 05:00:52,163 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2090113444] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:00:52,163 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-08 05:00:52,163 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-08 05:00:52,163 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1871872128] [2025-03-08 05:00:52,163 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:00:52,164 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-08 05:00:52,164 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:00:52,164 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-08 05:00:52,164 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-08 05:00:52,164 INFO L87 Difference]: Start difference. First operand 339 states and 471 transitions. Second operand has 5 states, 5 states have (on average 6.4) internal successors, (32), 5 states have internal predecessors, (32), 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-08 05:00:52,271 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:00:52,271 INFO L93 Difference]: Finished difference Result 535 states and 789 transitions. [2025-03-08 05:00:52,271 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-08 05:00:52,272 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 6.4) internal successors, (32), 5 states have internal predecessors, (32), 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 89 [2025-03-08 05:00:52,272 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:00:52,274 INFO L225 Difference]: With dead ends: 535 [2025-03-08 05:00:52,274 INFO L226 Difference]: Without dead ends: 416 [2025-03-08 05:00:52,275 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-08 05:00:52,275 INFO L435 NwaCegarLoop]: 54 mSDtfsCounter, 11 mSDsluCounter, 126 mSDsCounter, 0 mSdLazyCounter, 46 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 180 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-08 05:00:52,275 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 180 Invalid, 50 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 46 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-08 05:00:52,276 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 416 states. [2025-03-08 05:00:52,333 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 416 to 364. [2025-03-08 05:00:52,334 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 364 states, 230 states have (on average 1.2826086956521738) internal successors, (295), 233 states have internal predecessors, (295), 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-08 05:00:52,336 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 364 states to 364 states and 509 transitions. [2025-03-08 05:00:52,337 INFO L78 Accepts]: Start accepts. Automaton has 364 states and 509 transitions. Word has length 89 [2025-03-08 05:00:52,337 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:00:52,337 INFO L471 AbstractCegarLoop]: Abstraction has 364 states and 509 transitions. [2025-03-08 05:00:52,337 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 6.4) internal successors, (32), 5 states have internal predecessors, (32), 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-08 05:00:52,337 INFO L276 IsEmpty]: Start isEmpty. Operand 364 states and 509 transitions. [2025-03-08 05:00:52,338 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 98 [2025-03-08 05:00:52,339 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:52,339 INFO L218 NwaCegarLoop]: trace histogram [12, 11, 11, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:00:52,339 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable15 [2025-03-08 05:00:52,339 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:52,339 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:52,339 INFO L85 PathProgramCache]: Analyzing trace with hash 777061389, now seen corresponding path program 1 times [2025-03-08 05:00:52,339 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:52,339 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1811716792] [2025-03-08 05:00:52,340 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:52,340 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:52,344 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 97 statements into 1 equivalence classes. [2025-03-08 05:00:52,362 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 97 of 97 statements. [2025-03-08 05:00:52,363 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:52,363 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:00:52,364 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1876161842] [2025-03-08 05:00:52,364 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:52,364 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:52,364 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:00:52,366 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-08 05:00:52,368 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2025-03-08 05:00:52,398 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 97 statements into 1 equivalence classes. [2025-03-08 05:00:52,423 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 97 of 97 statements. [2025-03-08 05:00:52,423 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:52,423 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:52,425 INFO L256 TraceCheckSpWp]: Trace formula consists of 244 conjuncts, 53 conjuncts are in the unsatisfiable core [2025-03-08 05:00:52,427 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:00:53,266 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-08 05:00:53,266 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:01:08,686 WARN L286 SmtUtils]: Spent 6.35s on a formula simplification that was a NOOP. DAG size: 51 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2025-03-08 05:01:38,780 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-08 05:01:38,780 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:01:38,780 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1811716792] [2025-03-08 05:01:38,780 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:01:38,780 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1876161842] [2025-03-08 05:01:38,780 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1876161842] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 05:01:38,780 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-08 05:01:38,781 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 13] total 26 [2025-03-08 05:01:38,781 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1630849434] [2025-03-08 05:01:38,781 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-08 05:01:38,781 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2025-03-08 05:01:38,781 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:01:38,781 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2025-03-08 05:01:38,782 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=111, Invalid=539, Unknown=0, NotChecked=0, Total=650 [2025-03-08 05:01:38,782 INFO L87 Difference]: Start difference. First operand 364 states and 509 transitions. Second operand has 26 states, 25 states have (on average 2.12) internal successors, (53), 21 states have internal predecessors, (53), 11 states have call successors, (31), 3 states have call predecessors, (31), 3 states have return successors, (30), 13 states have call predecessors, (30), 10 states have call successors, (30) [2025-03-08 05:01:54,803 WARN L286 SmtUtils]: Spent 14.37s on a formula simplification. DAG size of input: 76 DAG size of output: 75 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2025-03-08 05:02:13,700 WARN L286 SmtUtils]: Spent 16.31s on a formula simplification. DAG size of input: 67 DAG size of output: 66 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2025-03-08 05:02:15,643 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.87s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2025-03-08 05:02:19,916 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 []